Quantum resistant lamport-diffie, winternitz and merkle tree hash based signature functions (in progress)..
Currently supports: LD-OTS, W-OTS and W-OTS+ keypair gen, signing and verification using sha256. Additionally supports: MSS and XMSS(with W-OTS+) signing and verification for many-sign capability..XMSS is far faster but with larger keysizes
Todo: Add hypertree support for chained XMSS tree signatures..
LD-OTS
Lamport one time signature scheme creates 256 pairs of 256 bit private keys (in pairs at position 0 and 1) and a one way hash is computed to create an array of a further 256 pairs of 256 bit public keys. The entire 512x256 bit array of public keys is the public key. Signature involves creating a 256 bit hash of the message and then bitwise inspecting the hash result, for each bit - if 0 the first private key is the signature, if 1 the second is chosen as the signature. Obviously this is a one time signature. Public key size can be reduced to 256 bits by including 2,4,8 etc LD-OTS signatures in a merkle tree.
Usage:
To create lamport-diffie key pairs:
priv, pub = random_lkey()
Returns lists of tuples containing 256 pairs of private keys and corresponding public keys.
To sign a message:
sig = sign_lkey(priv, message)
Returns the signature which is a list of 256 256bit strings (50% of the private key).
To verify a signature:
verify_lkey(sig, message, pub)
Returns true or false.
Winternitz one time signature scheme (W-OTS)
Based upon the initial scheme. Reduces key sizes and signatures significantly but increases computation time. Keypair generation creates 32 256 bit random private keys. When w=8 they are each hashed 255 times (2^w-1), then a further hash is performed, to create 32 256 bit public keys. Signature involves parsing the hash of the message 8 bits at a time (can be done 16 but this increases hash computation cycles significantly, from 0.01s to 3.7s), the 8 bit binary int (n) is subtracted from 256 and the private key is self hashed 256-n times. Thus the signature is 32 separate iterative hashes derived from the random private keys based up on the bitstream of the hash-message. To verify the message, the recipient knows the message and the public key and the signature, she simply parses the hash of the signature (8 bits at a time, extracting the 8 bit int, n) and then iteratively hashes the signature hashes n times. If the signature and message matches the public key then the public key is created from the signature. This is a one time signature which can be extended like the LD-OTS with a merkle tree to both reduce the public key size and increase the number of signs.
Usage:
To create W-OTS key pairs:
priv, pub = random_wkey()
Returns lists of 32 256 bit private keys and corresponding public keys.
To sign a message:
sig = sign_lkey(priv, message)
Returns the signature which is a list of 32 256bit hashes.
To verify a signature:
verify_lkey(sig, message, pub)
Evaluates whether message signature is valid by recreating the public key from the signature. Returns true or false.
Winternitz-OTS or LDOTS and Merkle Signature Scheme
Creating more than one set of W-OTS keypairs and hashing the concatenated 32 256 public keys fragments for each keypair allows a merkle tree to be created. The pubhashes are concatenated and hashed upwards in a tree to the root. The same is true of the larger Lamport-Diffie OTS signatures.
Usage:
To create a batch of W-OTS keypairs and link them to a merkle tree:
data = random_wmss(20)
To create n LD-OTS keypairs and link them to a merkle tree:
data = random_ldmss(n)
Returns confirmation of each n keypairs created and timings and details of the merkle tree. Data for each W-OTS/LD-OTS keypair are held in a list containing class objects with data accessible (e.g. data[0].pub (public key), data[0].priv (private key), data[0].concatpub (concatenated public key for pubhash), data[0].pubhash (hash of concatenated public key),data[0].type (type of key..LD or W-OTS), data[0].merkle_root (root hash of tree), data[0].merkle_path (hash authentication path from leaf to root).
The merkle tree class is returned entirely in data[0].merkle_obj allowing similar access to associated data (e.g. 'data[0].merkle_obj.root') for the following: .root, .base, .height, .num_leaves, .num_branches .tree, .auth_lists. But everything needed to perform a signature with proofs to the merkle root is found in the data[n] class object.
Expect some computation time with larger merkle trees auth proofs. On a macbook pro: 4 signatures 0.003s, 32 s, 64 1.3s, 128 10.3s, 256 84.7s etc..
To sign a message using data from above two functions:
sig = sign_mss(data, 'a message to sign', ots_key)
Creates a signature using the private key from specified ots_key number within the data list.
To verify a signature:
verify_mss(sig, data, 'a message to sign', ots_key)
Returns True or False.
To verify the merkle root can be computed using the public key and merkle path data:
verify_root(pub, merkle_root, merkle_path)
Returns True or False.
Example code
For example the following would create 64 W-OTS keypairs and build a merkle tree, print the merkle root, sign a message from keypair 32 (33rd), then verify that message and confirm the merkle authentication route is true.
d = random_wmss(64)
print d[0].merkle_root
sig = sign_mss(d, 'this is probably quantum secure', 32)
verify_mss(sig, d, 'this is probably quantum secure', 32)
verify_root(d[32].pub, d[32].merkle_root, d[32].merkle_path)