Here SHA256 denotes the NIST standard hash function [FIPS180]. SHA256-16 denotes the SHA256 hash function with its final output truncated to return the leftmost 16 bytes.

4.4. Private Key

The LM-OTS private key consists of an array of size p containing n-byte strings. Let x denote the private key. This private key must be used to sign one and only one message. It must therefore be unique from all other private keys. The following algorithm shows pseudocode for generating x.

Algorithm 0: Generating a Private Key

  for ( i = 0; i < p; i = i + 1 ) {
    set x[i] to a uniformly random n-byte string 
  }
  return x

An implementation MAY use a pseudorandom method to compute x[i], as suggested in [Merkle79], page 46. The details of the pseudorandom method do not affect interoperability, but the cryptographic strength MUST match that of the LM-OTS algorithm.

4.5. Public Key

The LM-OTS public key is generated from the private key by iteratively applying the function H to each individual element of x, for 2^w - 1 iterations, then hashing all of the resulting values.

Each public/private key pair is associated with a single identifier I. This string MUST be 31 bytes long, and be generated as described in Section 3.2.

The diversification parameter q is an input to the algorithm, as described in Section 3.2.

The following algorithm shows pseudocode for generating the public key, where the array x is the private key.

Algorithm 1: Generating a Public Key From a Private Key

  for ( i = 0; i < p; i = i + 1 ) {
    tmp = x[i] 
    for ( j = 0; j < 2^w - 1; j = j + 1 ) {
       tmp = H(tmp || I || q || uint16str(i) || uint8str(j) || D_ITER)
    }
    y[i] = tmp
  }
  return H(I || q || y[0] || y[1] || ... || y[p-1] || D_PBLC)

The public key is the string consisting of a four-byte enumeration that identifies the parameters in use, followed by the value returned by Algorithm 1. Section 4.10 specifies the enumeration and more formally defines the format.

4.6. Checksum

A checksum is used to ensure that any forgery attempt that manipulates the elements of an existing signature will be detected. The security property that it provides is detailed in Section 10. The checksum function Cksm is defined as follows, where S denotes the byte string that is input to that function, and the value sum is a 16-bit unsigned integer:

Algorithm 2: Checksum Calculation

  sum = 0
  for ( i = 0; i < u; i = i + 1 ) {
    sum = sum + (2^w - 1) - coef(S, i, w)
  }
  return (sum << ls)

Because of the left-shift operation, the rightmost bits of the result of Cksm will often be zeros. Due to the value of p, these bits will not be used during signature generation or verification.

4.7. Signature Generation

The LM-OTS signature of a message is generated by first appending the randomizer C, the identifier string I, and the diversification string q to the message, then using H to compute the hash of the resulting string, concatenating the checksum of the hash to the hash itself, then considering the resulting value as a sequence of w-bit values, and using each of the the w-bit values to determine the number of times to apply the function H to the corresponding element of the private key. The outputs of the function H are concatenated together and returned as the signature. The pseudocode for this procedure is shown below.

The identifier string I and diversification string q are the same as in Section 4.5.

Algorithm 3: Generating a Signature From a Private Key and a Message

  set C to a uniformly random n-byte string 
  set type to the appropriate ots_algorithm_type
  Q = H(message || C || I || q || D_MESG)
  for ( i = 0; i < p; i = i + 1 ) {
    a = coef(Q || Cksm(Q), i, w)
    tmp = x[i] 
    for ( j = 0; j < a; j = j + 1 ) {
       tmp = H(tmp || I || q || uint16str(i) || uint8str(j) || D_ITER)
    }
    y[i] = tmp
  }
  return type || C || I || 0x00 || q || (y[0] || y[1] || ... || y[p-1])

Note that this algorithm results in a signature whose elements are intermediate values of the elements computed by the public key algorithm in Section 4.5.

The signature is the string consisting of a four-byte enumeration that identifies the parameters in use, followed by the value returned by Algorithm 3. Section 4.10 specifies the enumeration and more formally defines the format.

4.8. Signature Verification

In order to verify a message with its signature (an array of n-byte strings, denoted as y), the receiver must "complete" the series of applications of H using the w-bit values of the message hash and its checksum. This computation should result in a value that matches the provided public key.

Algorithm 4: Verifying a Signature and Message Using a Public Key

  parse C, I, q, and y from the signature as follows:
     type = first 4 bytes
     C = next n bytes 
     I = next 31 bytes
     NULL = next byte; this padding value is discarded 
     q = next four bytes 
     y[0] = next n bytes
     y[1] = next n bytes
     ...
     y[p-1] = next n bytes
  Q = H(message || C || I || q || D_MESG)
  for ( i = 0; i < p; i = i + 1 ) {
    a = (2^w - 1) - coef(Q || Cksm(Q), i, w)
    tmp = y[i] 
    for ( j = a+1; j < 2^w - 1; j = j + 1 ) {
       tmp = H(tmp || I || q || uint16str(i) || uint8str(j) || D_ITER)
    }
    z[i] = tmp
  }
  candidate = H(z[0] || z[1] || ... || z[p-1] || I || q || D_PBLC) 
  if (candidate = public_key)
    return 1  // message/signature pair is valid
  else
    return 0  // message/signature pair is invalid

4.9. Notes

A future version of this specification may define a method for computing the signature of a very short message in which the hash is not applied to the message during the signature computation. That would allow the signatures to have reduced size.

4.10. Formats

The signature and public key formats are formally defined using the External Data Representation (XDR) [RFC4506] in order to provide an unambiguous, machine readable definition. For clarity, we also include a private key format as well, though consistency is not needed for interoperability and an implementation MAY use any private key format. Though XDR is used, these formats are simple and easy to parse without any special tools. The definitions are as follows:

/*
 * ots_algorithm_type identifies a particular signature algorithm
 */
enum ots_algorithm_type {
  ots_reserved        = 0,
  lmots_sha256_m16_w1  = 0x00000001,
  lmots_sha256_m16_w2  = 0x00000002,
  lmots_sha256_m16_w4  = 0x00000003,
  lmots_sha256_m16_w8  = 0x00000004,
  lmots_sha256_n32_w1  = 0x00000005,
  lmots_sha256_n32_w2  = 0x00000006,
  lmots_sha256_n32_w4  = 0x00000007,
  lmots_sha256_n32_w8  = 0x00000008
};

/* 
 * byte strings (for n=16 and n=32)
 */
typedef opaque bytestring16[16];
typedef opaque bytestring32[32];

union ots_signature switch (ots_algorithm_type type) {
 case lmots_sha256_n16_w1:
      bytestring16 y_n16_p265[265];
 case lmots_sha256_n16_w2:
      bytestring16 y_n16_p133[133];
 case lmots_sha256_n16_w4:
      bytestring16 y_n16_p67[67];
 case lmots_sha256_n16_w8:
      bytestring16 y_n16_p34[34];
 case lmots_sha256_n32_w1:
      bytestring32 y_n32_p265[265];
 case lmots_sha256_n32_w2:
      bytestring32 y_m3_p133[133];
 case lmots_sha256_n32_w4:
      bytestring32 y_n32_y_p67[67];
 case lmots_sha256_n32_w8:
      bytestring32 y_n32_p34[34];
 default:
   void;   /* error condition */
}; 

union ots_public_key switch (ots_algorithm_type type) {
 case lmots_sha256_n16_w1:
 case lmots_sha256_n16_w2:
 case lmots_sha256_n16_w4:
 case lmots_sha256_n16_w8:
 case lmots_sha256_n32_w1:
 case lmots_sha256_n32_w2:
 case lmots_sha256_n32_w4:
 case lmots_sha256_n32_w8:
      bytestring32 y32;
 default:
   void;   /* error condition */
 };

union ots_private_key switch (ots_algorithm_type type) {
 case lmots_sha256_m16_w1:
 case lmots_sha256_m16_w2:
 case lmots_sha256_m16_w4:
 case lmots_sha256_m16_w8:
      bytestring20 x20;
 case lmots_sha256_n32_w1:
 case lmots_sha256_n32_w2:
 case lmots_sha256_n32_w4:
 case lmots_sha256_n32_w8:
      bytestring32 x32;
 default:
   void;   /* error condition */
 };

Though the data formats are formally defined by XDR, we include diagrams as well as a convenience to the reader. An example of the format of an lmots_signature is illustrated below, for lmots_sha256_n32_w1. An ots_signature consists of a 32-bit unsigned integer that indicates the ots_algorithm_type, followed by other data, whose format depends only on the ots_algorithm_type. For LM-OTS, that data is an array of equal-length byte strings. The number of bytes in each byte string, and the number of elements in the array, are determined by the ots_algorithm_type field. In the case of lmots_sha256_n32_w1, the array has 265 elements, each of which is a 32-byte string. The XDR array y_n32_p265 denotes the array y as used in the algorithm descriptions above, using the parameters of n=32 and p=265 for lmots_sha256_n32_w1.

A verifier MUST check the ots_algorithm_type field, and a verification operation on a signature with an unknown lmots_algorithm_type MUST return FAIL.

         +---------------------------------+
         |       ots_algorithm_type        |
         +---------------------------------+
         |                                 |
         |         y_n32_p265[0]           |
         |                                 |
         +---------------------------------+
         |                                 |
         |         y_n32_p265[1]           |
         |                                 |
         +---------------------------------+
         |                                 |
         ~             ....                ~
         |                                 |
         +---------------------------------+
         |                                 |
         |        y_n32_p265[264]          |
         |                                 |
         +---------------------------------+

5. Leighton Micali Signatures

The Leighton Micali Signature (LMS) method can sign a potentially large but fixed number of messages. An LMS system uses two cryptographic components: a one-time signature method and a hash function. Each LMS public/private key pair is associated with a perfect binary tree, each node of which contains an n-byte value. Each leaf of the tree contains the value of the public key of an LM-OTS public/private key pair. The value contained by the root of the tree is the LMS public key. Each interior node is computed by applying the hash function to the concatenation of the values of its children nodes.

An LMS system has the following parameters:

• h : the height (number of levels - 1) in the tree, and
• n : the number of bytes associated with each node.

There are 2^h leaves in the tree.

5.1. LMS Private Key

An LMS private key consists of 2^h one-time signature private keys and the leaf number of the next LM-OTS private key that has not yet been used. The leaf number is initialized to zero when the LMS private key is created.

An LMS private key MAY be generated pseudorandomly from a secret value, in which case the secret value MUST be at least n bytes long, be uniformly random, and MUST NOT be used for any other purpose than the generation of the LMS private key. The details of how this process is done do not affect interoperability; that is, the public key verification operation is independent of these details.

5.2. LMS Public Key

An LMS public key is defined as follows, where we denote the public key associated with the i^th LM-OTS private key as OTS_PUBKEY[i], with i ranging from 0 to (2^h)-1. Each instance of an LMS public/private key pair is associated with a perfect binary tree, and the nodes of that tree are indexed from 1 to 2^(h+1)-1. Each node is associated with an n-byte string, and the string for the rth node is denoted as T[r] and is defined as

 T[r] = / H(OTS_PUBKEY[r-2^h]  || I || uint32str(r) || D_LEAF) if r >= 2^h
        \ H(T[2*r] || T[2*r+1] || I || uint32str(r) || D_INTR) otherwise.        

The LMS public key is the string consisting of a four-byte enumeration that identifies the parameters in use, followed by the string T[1]. Section 5.5 specifies the enumeration and more formally defines the format. The value T[1] can be computed via recursive application of the above equation, or by any equivalent method. An iterative procedure is outlined in Appendix B.

5.3. LMS Signature

An LMS signature consists of

• a typecode indicating the particular LMS algorithm,
• an LM-OTS signature, and
• an array of values that is associated with the path through the tree from the leaf associated with the LM-OTS signature to the root.

The array of values contains the siblings of the nodes on the path from the leaf to the root but does not contain the nodes on the path itself. The array for a tree with height h will have h values. The first value is the sibling of the leaf, the next value is the sibling of the parent of the leaf, and so on up the path to the root.

5.3.1. LMS Signature Generation

To compute the LMS signature of a message with an LMS private key, the signer first computes the LM-OTS signature of the message using the leaf number of the next unused LM-OTS private key. Before releasing the signature, the leaf number in the LMS private key MUST be incremented to prevent the LM-OTS private key from being used again. The node number in the signature is set to the leaf number of the LMS private key that was used in the signature. Then the signature and the LMS private key are returned.

The array of node values in the signature MAY be computed in any way. There are many potential time/storage tradeoffs that can be applied. The fastest alternative is to store all of the nodes of the tree and set the array in the signature by copying them. The least storage intensive alternative is to recompute all of the nodes for each signature. Note that the details of this procedure are not important for interoperability; it is not necessary to know any of these details in order to perform the signature verification operation. The internal nodes of the tree need not be kept secret, and thus a node-caching scheme that stores only internal nodes can sidestep the need for strong protections.

One useful time/storage tradeoff is described in Column 19 of [USPTO5432852].

5.4. LMS Signature Verification

An LMS signature is verified by first using the LM-OTS signature verification algorithm to compute the LM-OTS public key from the LM-OTS signature and the message. The value of that public key is then assigned to the associated leaf of the LMS tree, then the root of the tree is computed from the leaf value and the node array (path[]) as described below. If the root value matches the public key, then the signature is valid; otherwise, the signature fails.

Algorithm 6: LMS Signature Verification

  identify the height h of the tree from the algorithm type
  determine the leaf number the LM-OTS q value to an integer
  n = node number = 2^h + leaf_number
  tmp = candidate public key computed from LM-OTS signature and message
  tmp = H(tmp || I || uint32str(node_num) || D_LEAF)
  i = 0
  while (node_num > 1) {
      if (node_num is odd):
          tmp = H(path[i] || tmp || I || uint32str(node_num/2) || D_INTR)
      else:
          tmp = H(tmp || path[i] || I || uint32str(node_num/2) || D_INTR)
      node_num = node_num/2
      i = i + 1
  if (tmp == lms_public_key) 
    return 1  // message/signature pair is valid
  else
    return 0  // message/signature pair is invalid

Upon completion, v contains the value of the root of the LMS tree for comparison.

The verifier MAY cache interior node values that have been computed during a successful signature verification for use in subsequent signature verifications. However, any implementation that does so MUST make sure any nodes that are cached during a signature verification process are deleted if that process does not result in a successful match between the root of the tree and the LMS public key.

5.5. LMS Formats

LMS signatures and public keys are defined using XDR syntax as follows:

enum lms_algorithm_type {
  lms_reserved       = 0x00000000,
  lms_sha256_n32_h20 = 0x00000001,
  lms_sha256_n32_h10 = 0x00000002,
  lms_sha256_n32_h5  = 0x00000003
  lms_sha256_n16_h20 = 0x00000004,
  lms_sha256_n16_h10 = 0x00000005,
  lms_sha256_n16_h5  = 0x00000006
};

union lms_path switch (lms_algorithm_type type) {
 case lms_sha256_n32_h20:
   bytestring32 path_n32_h20[20]; 
 case lms_sha256_n32_h10:
   bytestring32 path_n32_h10[10];
 case lms_sha256_n32_h5:
   bytestring32 path_n32_h5[5];
 case lms_sha256_n16_h20:
   bytestring32 path_n16_h20[20]; 
 case lms_sha256_n16_h10:
   bytestring32 path_n16_h10[10];
 case lms_sha256_n16_h5:
   bytestring32 path_n16_h5[5];
 default:
   void;     /* error condition */
};

struct lms_signature {
  ots_signature ots_sig;               
  lms_path nodes;
};

struct lms_public_key_n16 {
  ots_algorithm_type ots_alg_type;
  opaque value[16];                    /* public key */
};    

struct lms_public_key_n64 {
  ots_algorithm_type ots_alg_type;
  opaque value[64];                    /* public key */
  opaque I[31];                        /* identity   */
};    

union lms_public_key switch (lms_algorithm_type type) {
 case lms_sha256_n32_h20:
 case lms_sha256_n32_h10:
 case lms_sha256_n32_h5:
      lms_public_key_n32 z_n32;
 case lms_sha256_n16_h20:
 case lms_sha256_n16_h10:
 case lms_sha256_n16_h5:
      lms_public_key_n16 z_n16;
  default:
   void;     /* error condition */
};

6. Hierarchical signatures

In scenarios where it is necessary to minimize the time taken by the public key generation process, a hierarchical N-time signature scheme can be used. Leighton and Micali describe a scheme in which an LMS public key is used to sign a second LMS public key, which is then distributed along with the signatures generated with the second public key [USPTO5432852]. This hierarchical scheme, which we describe in this section, uses an LMS scheme as a component, and it has two levels. Each level is associated with an LMS public key, private key, and signature. The following notation is used, where i is an integer between 1 and 2 inclusive:

• prv[i] is the private key of the ith level,
• pub[i] is the public key of the ith level, and
• sig[i] is the signature of the ith level.

In this section, we say that an N-time private key is exhausted when it has signed all N messages, and thus it can no longer be used for signing.

6.1. Key Generation

To generate an HLMS private and public key pair, new LMS private and public keys are generated for prv[i] and pub[i] for i=1,2. These key pairs MUST be generated independently.

The public key of the HLMS scheme is pub[1], the public key of the first level. The HLMS private key consists of prv[1] and prv[2]. The values pub[1] and prv[1] do not change, though the values of pub[2] and prv[2] are dynamic, and are changed by the signature generation algorithm.

6.2. Signature Generation

To sign a message using the private key prv, the following steps are performed:

• The message is signed with prv[2], and the value sig[2] is set to that result.
• The value of the HLMS signature is set to type || pub[2] || sig[1] || sig[2], where type is the typecode for the particular HLMS algorithm.
• If prv[2] is exhausted, then a new LMS public and private key pair is generated, and pub[2] and prv[2] are set to those values. pub[2] is signed with prv[1], and sig[1] is set to the resulting value.

6.3. Signature Verification

To verify a signature sig and message using the public key pub, the following steps are performed:

• The signature sig is parsed into its components type, pub[2], sig[1] and sig[2].
• The signature sig[2] and message is verified using the public key pub[2]. If verification fails, then an indication of failure is returned. Otherwise, processing continues as follows.
• The signature sig[1] of the "message" pub[2] is verified using the public key pub. If verification fails, then an indication of failure is returned. Otherwise, an indication of success is returned.

7. Rationale

The goal of this note is to describe the LM-OTS and LMS algorithms following the original references and present the modern security analysis of those algorithms. Other signature methods are out of scope and may be interesting follow-on work.

We adopt the techniques described by Leighton and Micali to mitigate attacks that amortize their work over multiple invocations of the hash function.

The values taken by the identifier I across different LMS public/private key pairs are required to be distinct in order to improve security. That distinctness ensures the uniqueness of the inputs to H across all of those public/private key pair instances, which is important for provable security in the random oracle model. The length of I is set at 31 bytes so that randomly chosen values of I will be distinct with probability at least 1 - 1/2^128 as long as there are 2^60 or fewer instances of LMS public/private key pairs.

The sizes of the parameters in the security string are such that, for n=16, the LM-OTS iterates a 55-byte value (that is, the string that is input to H() during the iteration over j during signature generation and verification is 55 bytes long). Thus, when SHA-256 is used as the function H, only a single invocation of its compression function is needed.

The signature and public key formats are designed so that they are easy to parse. Each format starts with a 32-bit enumeration value that indicates all of the details of the signature algorithm and hence defines all of the information that is needed in order to parse the format.

The Checksum Section 4.6 is calculated using a non-negative integer "sum", whose width was chosen to be an integer number of w-bit fields such that it is capable of holding the difference of the total possible number of applications of the function H as defined in the signing algorithm of Section 4.7 and the total actual number. In the worst case (i.e. the actual number of times H is iteratively applied is 0), the sum is (2^w - 1) * ceil(8*n/w). Thus for the purposes of this document, which describes signature methods based on H = SHA256 (n = 32 bytes) and w = { 1, 2, 4, 8 }, the sum variable is a 16-bit non-negative integer for all combinations of n and w. The calculation uses the parameter ls defined in Section 4.1 and calculated in Appendix A, which indicates the number of bits used in the left-shift operation.

8. History

This is the third version version of this draft. It has the following changes:

• It adopts the "security string" approach of Leighton and Micali [USPTO5432852] in order to improve security.
• It adopts Leighton and Micali's idea of hashing a randomizer string (C, as defined in Section 3.2) with the message, so that finding an arbitrary collision in H will not lead to a forgery.
• It defines a multi-level signature scheme, again following that described by Leighton and Micali.
• It eliminates the function F and its iterates; the function H is used in its stead. The adoption of the security string makes this simplification possible.
• It fixes the branching number at two for simplicity.

This section is to be removed by the RFC editor upon publication.

9. IANA Considerations

The Internet Assigned Numbers Authority (IANA) is requested to create two registries: one for OTS signatures, which includes all of the LM-OTS signatures as defined in Section 3, and one for Leighton-Micali Signatures, as defined in Section 4. Additions to these registries require that a specification be documented in an RFC or another permanent and readily available reference in sufficient detail that interoperability between independent implementations is possible. Each entry in the registry contains the following elements:

• a short name, such as "LMS_SHA256_n32_h10",
• a positive number, and
• a reference to a specification that completely defines the signature method test cases that can be used to verify the correctness of an implementation.

Requests to add an entry to the registry MUST include the name and the reference. The number is assigned by IANA. These number assignments SHOULD use the smallest available palindromic number. Submitters SHOULD have their requests reviewed by the IRTF Crypto Forum Research Group (CFRG) at cfrg@ietf.org. Interested applicants that are unfamiliar with IANA processes should visit http://www.iana.org.

The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF (decimal 4,294,967,295) inclusive, will not be assigned by IANA, and are reserved for private use; no attempt will be made to prevent multiple sites from using the same value in different (and incompatible) ways [RFC2434].

The LM-OTS registry is as follows.

  u = ceil(8*n/w)
  v = ceil((floor(lg((2^w - 1) * u)) + 1) / w)
  ls = (number of bits in sum) - (v * w)
  p = u + v

  for ( i = 0; i < num_lmots_keys; i = i + 2 ) {
    level = 0;
    for ( j = 0; j < 2; j = j + 1 ) {
      r = node number 
      push H(OTS_PUBKEY[i+j] || I || uint32str(r) || D_LEAF) onto data stack
      push level onto the integer stack
    }
    while ( height of the integer stack >= 2 ) {
      if level of the top 2 elements on the integer stack are equal {
        hash_init()
        siblings = ""
        repeat ( 2 ) {
          siblings = (pop(data stack) || siblings)
          level = pop(integer stack)
        }
        hash_update(siblings)
        r = node number 
        hash_update(I || uint32str(r) || D_INTR)
        push hash_final() onto the data stack
        push (level + 1) onto the integer stack
      }
    }
  }
  public_key = pop(data stack)

# example implementation for Leighton-Micali hash based signatures
# Internet draft
#
# Notes:
#
#     * only a limted set of parameters are supported; in particular,
#     * w=8 and n=32
#
#     * HLMS, LMS, and LM-OTS are all implemented
#
#     * uncommenting print statements may be useful for debugging, or
#       for understanding the mechanics of
#
#
# LMOTS constants
#
D_ITER = chr(0x00) # in the iterations of the LM-OTS algorithms
D_PBLC = chr(0x01) # when computing the hash of all of the iterates in the LM-OTS algorithm 
D_MESG = chr(0x02) # when computing the hash of the message in the LMOTS algorithms
D_LEAF = chr(0x03) # when computing the hash of the leaf of an LMS tree
D_INTR = chr(0x04) # when computing the hash of an interior node of an LMS tree

NULL   = chr(0)    # used as padding for encoding 

lmots_sha256_n32_w8 = 0x08000008 # typecode for LM-OTS with n=32, w=8
lms_sha256_n32_h10  = 0x02000002 # typecode for LMS with n=32, h=10
hlms_sha256_n32_l2  = 0x01000001 # typecode for two-level HLMS with n=32


# LMOTS parameters
#
n = 32; p = 34; w = 8; ls = 0

def bytes_in_lmots_sig():
    return n*(p+1)+40 # 4 + n + 31 + 1 + 4 + n*p

from Crypto.Hash import SHA256
from Crypto import Random

# SHA256 hash function
#
def H(x):
#    print "hash input: " + stringToHex(x)
    h = SHA256.new()
    h.update(x)
    return h.digest()[0:n]

def sha256_iter(x, num):
    tmp = x
    for j in range(0, num):
        tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER)

# entropy source
#
entropySource = Random.new()

# integer to string conversion
#
def uint32ToString(x):
    c4 = chr(x & 0xff)
    x = x >> 8
    c3 = chr(x & 0xff)
    x = x >> 8
    c2 = chr(x & 0xff)
    x = x >> 8
    c1 = chr(x & 0xff)
    return c1 + c2 + c3 + c4

def uint16ToString(x):
    c2 = chr(x & 0xff)
    x = x >> 8
    c1 = chr(x & 0xff)
    return c1 + c2

def uint8ToString(x):
    return chr(x)

def stringToUint(x):
    sum = 0
    for c in x:
        sum = sum * 256 + ord(c)
    return sum

# string-to-hex function needed for debugging
#
def stringToHex(x):
    return "".join("{:02x}".format(ord(c)) for c in x)

# LM-OTS functions
#
def encode_lmots_sig(C, I, q, y):
    result = uint32ToString(lmots_sha256_n32_w8) + C + I + NULL + q
    for i, e in enumerate(y):
        result = result + y[i]
    return result

def decode_lmots_sig(sig):
    if (len(sig) != bytes_in_lmots_sig()):
        print "error decoding signature; incorrect length (" + str(len(sig)) + " bytes)"
    typecode = sig[0:4]
    if (typecode != uint32ToString(lmots_sha256_n32_w8)):
        print "error decoding signature; got typecode " + stringToHex(typecode) + ", expected: " + stringToHex(uint32ToString(lmots_sha256_n32_w8))
        return ""
    C = sig[4:n+4]
    I = sig[n+4:n+35]
    q = sig[n+36:n+40] # note: skip over NULL
    y = list()
    pos = n+40
    for i in range(0, p):
        y.append(sig[pos:pos+n])
        pos = pos + n
    return C, I, q, y

def print_lmots_sig(sig):
    C, I, q, y = decode_lmots_sig(sig)
    print "C:\t" + stringToHex(C)
    print "I:\t" + stringToHex(I)
    print "q:\t" + stringToHex(q)
    for i, e in enumerate(y):
        print "y[" + str(i) + "]:\t" + stringToHex(e)    

# Algorithm 0: Generating a Private Key
#
def lmots_gen_priv():
    priv = list()
    for i in range(0, p):
        priv.append(entropySource.read(n))
    return priv

# Algorithm 1: Generating a Public Key From a Private Key
#
def lmots_gen_pub(private_key, I, q):
    hash = SHA256.new()
    hash.update(I + q)
    for i, x in enumerate(private_key):
        tmp = x
        # print "i:" + str(i) + " range: " + str(range(0, 256))
        for j in range(0, 256):
            tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER)
        hash.update(tmp)
    hash.update(D_PBLC)
    return hash.digest()

# Algorithm 2: Merkle Checksum Calculation
#
def checksum(x):
    sum = 0
    for c in x:
        sum = sum + ord(c)
    # print format(sum, '04x')
    c1 = chr(sum >> 8)
    c2 = chr(sum & 0xff)
    return c1 + c2

# Algorithm 3: Generating a Signature From a Private Key and a Message
#
def lmots_gen_sig(private_key, I, q, message):
    C = entropySource.read(n) 
    hashQ = H(message + C + I + q + D_MESG)
    V = hashQ + checksum(hashQ)
    # print "V: " + stringToHex(V)
    y = list()
    for i, x in enumerate(private_key):
        tmp = x
        # print "i:" + str(i) + " range: " + str(range(0, ord(V[i])))
        for j in range(0, ord(V[i])):
            tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER)
        y.append(tmp)
    return encode_lmots_sig(C, I, q, y)
       
def lmots_sig_to_pub(sig, message):
    C, I, q, y = decode_lmots_sig(sig)
    hashQ = H(message + C + I + q + D_MESG)
    V = hashQ + checksum(hashQ)
    # print "V: " + stringToHex(V)
    hash = SHA256.new()
    hash.update(I + q)
    for i, y in enumerate(y):
        tmp = y
        # print "i:" + str(i) + " range: " + str(range(ord(V[i]), 256))
        for j in range(ord(V[i]), 256):
            tmp = H(tmp + I + q + uint16ToString(i) + uint8ToString(j) + D_ITER)
        hash.update(tmp)
    hash.update(D_PBLC)
    return hash.digest()
 
# Algorithm 4: Verifying a Signature and Message Using a Public Key
#
def lmots_verify_sig(public_key, sig, message):
    z = lmots_sig_to_pub(sig, message)
    # print "z: " + stringToHex(z)
    if z == public_key:
        return 1
    else:
        return 0

# LM-OTS test functions
#
I = entropySource.read(31) 
q = uint32ToString(0)
private_key = lmots_gen_priv()

print "LMOTS private key: "
for i, x in enumerate(private_key):
    print "x[" + str(i) + "]:\t" + stringToHex(x)

public_key = lmots_gen_pub(private_key, I, q)

print "LMOTS public key: "
print stringToHex(public_key)

message = "The right of the people to be secure in their persons, houses, papers, and effects, against unreasonable searches and seizures, shall not be violated, and no warrants shall issue, but upon probable cause, supported by oath or affirmation, and particularly describing the place to be searched, and the persons or things to be seized."

print "message: " + message

sig = lmots_gen_sig(private_key, I, q, message)

print "LMOTS signature byte length: " + str(len(sig))

print "LMOTS signature: "
print_lmots_sig(sig)

print "verification: " 
print "true positive test: " 
if (lmots_verify_sig(public_key, sig, message) == 1):
    print "passed: message/signature pair is valid as expected"
else:
    print "failed: message/signature pair is invalid"

print "false positive test: " 
if (lmots_verify_sig(public_key, sig, "some other message") == 1):
    print "failed: message/signature pair is valid (expected failure)"
else:
    print "passed: message/signature pair is invalid as expected"



# LMS N-time signatures functions
#
h = 10 # height (number of levels -1) of tree

def encode_lms_sig(lmots_sig, path):
    result = uint32ToString(lms_sha256_n32_h10) + lmots_sig
    for i, e in enumerate(path):
        result = result + path[i]
    return result

def decode_lms_sig(sig):
    typecode = sig[0:4]
    if (typecode != uint32ToString(lms_sha256_n32_h10)):
        print "error decoding signature; got typecode " + stringToHex(typecode) + ", expected: " + stringToHex(uint32ToString(lms_sha256_h10))
        return ""   
    pos = 4 + bytes_in_lmots_sig()
    lmots_sig = sig[4:pos]
    path = list()
    for i in range(0,h):
        # print "sig[" + str(i) + "]:\t" + stringToHex(sig[pos:pos+n])
        path.append(sig[pos:pos+n])
        pos = pos + n
    return lmots_sig, path

def print_lms_sig(sig):
    lmots_sig, path = decode_lms_sig(sig)
    print_lmots_sig(lmots_sig)
    for i, e in enumerate(path):
        print "path[" + str(i) + "]:\t" + str(stringToHex(e))

def bytes_in_lms_sig():
    return bytes_in_lmots_sig() + h*n + 4

class lms_private_key(object):

    # Algorithm for computing root and other nodes (alternative to Algorithm 6)
    #
    def T(self, j):
        # print "T(" + str(j) + ")"
        if (j >= 2**h):
            self.nodes[j] = H(self.pub[j - 2**h] + self.I + uint32ToString(j) + D_LEAF)
            return self.nodes[j]
        else:
            self.nodes[j] = H(self.T(2*j) + self.T(2*j+1) + self.I + uint32ToString(j) + D_INTR)
            return self.nodes[j] 
    
    def __init__(self):
        self.I = entropySource.read(31) 
        self.priv = list()
        self.pub = list()
        for q in range(0, 2**h):
            # print "generating " + str(q) + "th OTS key"
            ots_priv = lmots_gen_priv()
            ots_pub = lmots_gen_pub(ots_priv, self.I, uint32ToString(q))
            self.priv.append(ots_priv)
            self.pub.append(ots_pub)
        self.leaf_num = 0
        self.nodes = {}
        self.lms_public_key = self.T(1)

    def num_sigs_remaining():
        return 2**h - self.leaf_num

    def printHex(self):
        for i, p in enumerate(self.priv):
            print "priv[" + str(i) + "]:" 
            for j, x in enumerate(p):
                print "x[" + str(j) + "]:\t" + stringToHex(x)
            print "pub[" + str(i) + "]:\t" + stringToHex(self.pub[i])
        for t, T in self.nodes.items():
            print "T(" + str(t) + "):\t" + stringToHex(T)
        print "pub: \t" + stringToHex(self.lms_public_key)

    def get_public_key(self):
        return self.lms_public_key

    def get_path(self, leaf_num):
        node_num = leaf_num + 2**h
        # print "signing node " + str(node_num)
        path = list()
        while node_num > 1:
            if (node_num % 2):
                # print "path" + str(node_num - 1) + ": " + stringToHex(self.nodes[node_num - 1])
                path.append(self.nodes[node_num - 1])
            else:
                # print "path " + str(node_num + 1) + ": " + stringToHex(self.nodes[node_num + 1])
                path.append(self.nodes[node_num + 1])
            node_num = node_num/2
        return path

    def sign(self, message):
        if (self.leaf_num >= 2**h):
            return ""
        sig = lmots_gen_sig(self.priv[self.leaf_num], self.I, uint32ToString(self.leaf_num), message)
        # C, I, q, y = decode_lmots_sig(sig) 
        path = self.get_path(self.leaf_num)
        leaf_num = self.leaf_num
        self.leaf_num = self.leaf_num + 1
        return encode_lms_sig(sig, path)


class lms_public_key(object):

    def __init__(self, value):
        self.value = value

    def verify(self, message, sig):
        lmots_sig, path = decode_lms_sig(sig)
        C, I, q, y = decode_lmots_sig(lmots_sig)       # note: only q is actually needed here
        node_num = stringToUint(q) + 2**h
        # print "verifying node " + str(node_num)
        pathvalue = iter(path)
        tmp = lmots_sig_to_pub(lmots_sig, message)
        tmp = H(tmp + I + uint32ToString(node_num) + D_LEAF)
        while node_num > 1:
            # print "S(" + str(node_num) + "):\t" + stringToHex(tmp)
            if (node_num % 2):
                # print "adding node " + str(node_num - 1)
                tmp = H(pathvalue.next() + tmp + I + uint32ToString(node_num/2) + D_INTR)
            else:
                # print "adding node " + str(node_num + 1)
                tmp = H(tmp + pathvalue.next() + I + uint32ToString(node_num/2) + D_INTR)
            node_num = node_num/2
        # print "pubkey: " + stringToHex(tmp)
        if (tmp == self.value):
            return 1
        else:
            return 0




# test LMS signatures
#

print "LMS test" 

lms_priv = lms_private_key()
lms_pub = lms_public_key(lms_priv.get_public_key())

# lms_priv.printHex()

for i in range(0, 2**h):
    sig = lms_priv.sign(message)

    print "LMS signature byte length: " + str(len(sig))

    # print_lms_sig(sig)
    
    print "true positive test"
    if (lms_pub.verify(message, sig) == 1):
        print "passed: LMS message/signature pair is valid"
    else:
        print "failed: LMS message/signature pair is invalid"
        
    print "false positive test"
    if (lms_pub.verify("other message", sig) == 1):
        print "failed: LMS message/signature pair is valid (expected failure)"
    else:
        print "passed: LMS message/signature pair is invalid as expected"



# Hierarchical LMS signatures (HLMS)

def encode_hlms_sig(pub2, sig1, lms_sig):
    result = uint32ToString(hlms_sha256_n32_l2)
    result = result + pub2
    result = result + sig1
    result = result + lms_sig
    return result

def decode_hlms_sig(sig):
    typecode = sig[0:4]
    if (typecode != uint32ToString(hlms_sha256_n32_l2)):
        print "error decoding signature; got typecode " + stringToHex(typecode) + ", expected: " + stringToHex(uint32ToString(hlms_sha256_n32_l2))
        return ""      
    pub2 = sig[4:36]
    lms_sig_len = bytes_in_lms_sig()
    sig1 = sig[36:36+lms_sig_len]
    lms_sig = sig[36+lms_sig_len:36+2*lms_sig_len]
    return pub2, sig1, lms_sig

def print_hlms_sig(sig):
    pub2, sig1, lms_sig = decode_hlms_sig(sig)
    print "pub2:\t" + stringToHex(pub2)
    print "sig1: " 
    print_lms_sig(sig1)
    print "sig2: " 
    print_lms_sig(lms_sig)

class hlms_private_key(object):
    def __init__(self):
        self.prv1 = lms_private_key()
        self.init_level_2()

    def init_level_2(self):
        self.prv2 = lms_private_key()
        self.sig1 = self.prv1.sign(self.prv2.get_public_key())

    def get_public_key(self):
        return self.prv1.get_public_key()

    def sign(self, message):
        lms_sig = self.prv2.sign(message)
        if (lms_sig == ""):
            print "refreshing level 2 public/private key pair"
            self.init_level_2()
            lms_sig = self.prv2.sign(message)
        return encode_hlms_sig(self.prv2.get_public_key(), self.sig1, lms_sig)
    
class hlms_public_key(object):
    def __init__(self, value):
        self.pub1 = lms_public_key(value)

    def verify(self, message, sig):
        pub2, sig1, lms_sig = decode_hlms_sig(sig)
        if (self.pub1.verify(pub2, sig1) == 1):
            if (lms_public_key(pub2).verify(message, lms_sig) == 1):
                return 1
            else:
                print "pub2 verification of lms_sig did not pass"
        else:
            print "pub1 verification of sig1 did not pass"
        return 0



print "HLMS testing"

hlms_prv = hlms_private_key()

hlms_pub = hlms_public_key(hlms_prv.get_public_key())

for i in range(0, 4096):

    sig = hlms_prv.sign(message)

    # print_hlms_sig(sig)

    print "HLMS signature byte length: " + str(len(sig))
    
    print "testing verification (" + str(i) + "th iteration)"
    print "true positive test"
    if (hlms_pub.verify(message, sig) == 1):
        print "passed; HLMS message/signature pair is valid"
    else:
        print "failed; HLMS message/signature pair is invalid"
        
        print "false positive test"
        if (hlms_pub.verify("other message", sig) == 1):
            print "failed; HLMS message/signature pair is valid (expected failure)"
        else:
            print "passed; HLMS message/signature pair is invalid as expected"