The Lamport-Diffie One Time Signature Scheme in Python

In this article we will find out how to implement the famous Lamport-Diffie One Time Signature Scheme (LDOTS) in Python. This crypographic system is the foundation for the Merkle signature scheme, an encryption system based on hashes and hash trees. Even more incredible about the Merkle signature scheme is the fact that it might be a quantum secure encryption system. So learning about the LDOTS helps us understand why the Merkle signature scheme is quantum proof and also why no one is using it.

So how will this article be structured? First we begin with a little warm up in cryptography. We are going to learn or re-learn the differences between symmetric, asymmetric and signature schemes. Once this is done we can jump over to the actual topic and study the ways of the LDOTS. And after understanding the principles of signing and verifying we will finally implement them in python. For a cool down we are going to find one reason, why the Merkle signature scheme is not yet a standard in the cryptographic world. So let’s go!

Cryptography Warm Up

As I have mentioned before, we can (in simple terms) differentiate between three types of cryptography systems:

• symmetric encryption
• asymmetric encryption
• signature schemes

The most simple type of encryption is the symmetric one. There is one key which can be used to encrypt a message and also to decrypt a message. A well known example for this is the Caesar encryption. To encrypt a message, we just substitute each letter with another letter from the alphabet. The key tells us how many steps we walk from the original letter. The key can also be used to walk back from the encrypted letter to the original one. This is why this cryptography system is called symmetric.

In a symmetric cryptography system the key can be used to encrypt and decrypt.

Now let’s go on to the asymmetric crytography system. Here in general we have to keys: a public key and a private key. To understand how encryption would work with those two keys, we have to meet Alice and Bob.

Alice owns a public key and a private key. Both are mathematically connected (either the private key has been calculated out of the public key or vice versa). The mathematical connection is such that it is basically impossible to calculate the private key knowing the public key. At least with today’s technology.
Now Bob wants to send an encrypted message to Alice that only Alice can decrypt. So he asks her to send him her public key. He can use that public key to encrypt the message and send it back to Alice. Alice can then decrypt the message, but only with the private key that corresponds to the public key used by Bob. In this process we can already see, why this is called an asymmetric encryption scheme. Bob can encrypt a message with the public key, but once he encrypted it he cannot decrypt it. This can only be done by Alice. In the case of a symmetric encryption Bob could have encrypted the message but also decrypted it right after.

In an asymmetric encryption there exist 2 keys: public and private key. The public key is used to encrypt and the private key is used to decrypt.

Famous asymmetric cryptography schemes are the RSA-algorithm and the Elliptic Curve Cryptography (ECC). What makes those asymmetric encryption schemes interesting is the fact that you can modify them into so called signature schemes.

Sometimes we don’t want to encrypt a message but only send a message and also verify that the message was indeed sent by us. We sign the message with our unique signature. How does that work in terms of cryptography? First we get a public key and a private key. Both are mathematically interconnected. We use the private key to create a signature and send our message together with the signature and the public key. To clarifiy the whole process we are going to look at Alice and Bob again.

Alice wants to send a message to Bob. She wants to prove to Bob that the message was indeed sent by her. Bob only knows her public key. Now Alice takes her message, uses her private key on this message and creates a signature. Then she sends the message together with the signature to Bob. (We can make her send the public key as well, just in case Bob has lost it.)

Now Bob can use the public key to verify that the signature was indeed created using the private key that belongs to that public key. And therefore the message must have come from Alice. When talking about signature schemes the public key is often also referred to as the verifying key since it is used to verify the signature. The private key on the other hand is often called the signing key since it is used to sign the message.

In a signature scheme there is two keys: the verifying key and the signing key. A signature is created based on the message and the signing key. The signature for a message gets verified with the verifying key.

Now that we have understood the basics of cryptography we can deepen our understanding of signature schemes by thoroughly studying the Lamport-Diffie One Time Signature. But before we do so, I would like to take a little detour into the quantum world, which will create a smooth transition back to the LDOTS. I promise.

The Quantum Problem

Asymmetric encryption and signature schemes are generally based on mathematical problems that are easy to solve in one direction but extremely hard to solve backwards. Extremely hard in this case means that with today’s knowledge and technology it is impossible to solve that problem. The easiest example for this is the RSA encryption, which is based on the prime factorization problem.

Every number has a prime factorization, meaning that every integer can be expressed as a unique product of prime numbers. If we choose 2 prime numbers randomly and multiply them we will get a new integer. This multiplication is rather easy to execute for both a human and a computer. But having a number and finding out which are the prime factors is an impossible to solve problem. This means that no mathematician or computer scientist or anyone ever came up with an algorithm ( a series of steps) to get from a number to the prime factors in an efficient and fast way. All algorithms take a literal eternity when you choose the number just high enough. And that is what modern cryptography is based on. The prime numbers are just chosen big enough such that no modern computer with the most modern algorithm can retrace the two prime numbers.

But now quantum comes. Quantum computers are not yet powerful enough, but the algorithms to run on them already exist. And they seem to beat modern computing by lightyears. The seemingly impossible problem of factorizing big numbers into their prime factors becomes a literal joke for a quantum computer running Shor’s algorithm. The one-way-problem of prime factorization became a two-way-highway. Shor’s algorithm can be modified and applied to Elliptic Curve Cryptography, making it obsolete in the future as well. So another way of creating cryptography has to be found.

As you might have noticed by now that cryptography schemes often are based on one-way-problems or one-way-functions. So to construct a quantum secure cryptography system we need a one-way-function that is immune against a quantum computer attack. Luckily there exist such a function, which is already heavily used in all branches of cryptography: hashes or hash functions.

A hash function simply is a function that maps any sequence of bits onto a sequence of bits of fixed length. So no matter how long the sequence of bits (in other words how big the chunk of data is), the hash value will always have a fixed amount of bits. This shows that in the process of hashing data, information is getting lost. Based on how the hash function is designed this information is nearly impossible to reconstruct. Impossible once again means that there is no modern algorithm that could do that. The crazy thing is that the current knowledge of quantum computing suggests that there is not even a quantum algorithm able to reconstruct the information that went missing in the process of hashing. So this makes hash functions an ideal candidate for a quantum secure signature scheme.

The Lamport Diffie One Time Signature Scheme

Now we have finally arrived at a point at which we can study the LDOTS. We jump right in by structuring the steps to take:

1. We need to create a signing key.
2. We need to use the signing key and create a verifying key.
3. We take a message and use the signing key to create a signature.
4. We get a message and a signature and use the verifying key to verify the signature.

1. The signing key

The message will be a sequence of k bits. The signing key will then be a matrix of dimensions k x 2k. This matrix will be randomly filled with 1’s and 0’s. So if for example our message consists of 2 bits

m = 0 1

Then the matrix will be of the dimension 2 x 4 and look like this (the 1’s and 0’s are chosen randomly):

2. The verifying key

To create the verifying key we take the signing key matrix and hash every single element.

That’s it! Now we can have a look on how to create a signature for a message.

3. The Signature

Now the signature creation becomes a bit tricky. Here we will recognize why we chose our signature key matrix to have twice as many columns as rows. For each bit of the message we will choose a column from the signing key matrix and construct with it the signature. The signature will be a matrix of dimension k x k, so a quadratic matrix. Which column of the signing key matrix gets chosen for the signature depends on the value of the bit in the message. To better understand this we return to our example with the message being

m = 0 1

and the signing key being

We start with the first bit. It has the value 0. So we choose the first column of the signing key matrix for our signature. If the first bit had been a 1 then we would have chosen the second column. Now for the second bit we do the exact same, just for the next pair of columns. Since the bit has the value 1, we choose the last column of the signing key matrix. So the signature in the end looks like this:

4. Verifying the signature

The last step will be to verify the signature. Therefore we need the the message and the verification key. The verification key is basically the signing key matrix, just with every element being hashed. So it is impossible to trace back the actual element of the signing key matrix by knowing the verifying key. First we hash every single element of the signature matrix. For each bit of the message we then choose the corresponding column out of the verification key matrix just like we did it with the signing key matrix. This column we have to compare with the corresponding column in the hashed signature matrix. If they are the same everything is good and we can go on to the next one. All of the columns of the hashed signature have to align with the corresponding columns in the verification matrix. This is — in my opinion — the trickiest part of the encryption system. And what better way is there to understand that than implementing it in Code yourself. Let’s go!

And now everything in Python

Finally we can implement all of our knowledge in Python. We start by importing some important libraries (numpy and hashes) and then we already define the function which will generate our signing key.

import numpy as np
import hashlib

def signing_key(message):
    message = str(message)
    message =  ''.join(format(ord(i), '08b') for i in message)    
    message = [int(i) for i in message]  
    k = len(message) # Security Parameter
    return np.random.randint(0,2,size=(2*k,k)).tolist()

As we have seen above in the description of the LDOTS the signing key is dependent on the message. If a message is 2 bits long then the signing key will be a matrix of dimensions 2x4. The signing key function takes a message (which should be preferably in the form of a string, but is converted to one just to make sure) and turns that into a sequence of bits. You could also just take the message directly and neglect the step where I turn it into a string and instantly turn it into binary. The most important part is just to have the message in binary form. In the next step the bit-string of the message is turned into a list of bits and eventually used to create the matrix as a numpy array. Here we have defined the security parameter k as the length of the bit sequence. Now that we have the signing key we can easily create the verifying key.

def verifying_key(key):
    
    verification_key = []
    
    for c in key:
        column = []
        for r in c:
            column.append(hashlib.sha256(str(r).encode()).hexdigest())
        
        verification_key.append(column)
        
    return verification_key

Here we just hash every single element of the signing key matrix. The signature is the first step where it is starting to become a bit more tricky.

def signature(message,key):
    
    message = str(message)
    message =  ''.join(format(ord(i), '08b') for i in message)    
    message = [int(i) for i in message] 
    
    signature = []
    for idx, bit in enumerate(message):
        signature.append(key[2*idx+bit])
    
    return signature

The first three lines of the signature-function are the same as in the signing key function. Our signature will be a matrix, but of dimension k x k, so a quadratic matrix. For each bit we choose one of the 2k columns of the signing key matrix. If the first bit of the message is a zero we choose the first column of the signing key matrix to be the first column of the signature. We do this for each bit of the message, hence the for-loop iterating over the bits and indices of the bits of the message. After we have now created a signature, we can construct a function to verify it.

As we have seen in the description of the LDOTS above, the verification-function has to get 3 parameters:

• the message
• the verification key
• the signature

def verification(message,verification_key,signature):
    
    message = str(message)
    message =  ''.join(format(ord(i), '08b') for i in message)    
    message = [int(i) for i in message] 
    
    hashed_signature = []
    
    if len(verification_key[0]) != len(message):
        return False
    
    else:
        for c in signature:
            column = []
            for r in c:
                column.append(hashlib.sha256(str(r).encode()).hexdigest())
        
            hashed_signature.append(column)

    
        for idx, bit in enumerate(message):
        
            if verification_key[2*idx+bit] != hashed_signature[idx]:
                return False
        
        return True

The first three lines once again are identical to the first three lines of the signature function. Since we want to compare the hashes of our signature with the hashes written in the verifying key matrix, we need to hash all the elements of our signature first. Once we have done that, we can go through each column in the signature and compare it with the corresponding column in the verification key. If all the columns for all the bits of the message are identical, the function returns TRUE, indicating that the verification process was succesfull.

The problem with practicality

The biggest issue of the LDOTS (apart from the fact that it can literally only be used once) is the dependence of the signing key on the length of the message. First of all messages are not always of the same size. Some messages might be only a couple of bits but some are sequences of millions of bits. So the the algorithm cannot be really standardized to one specific key size. The second problem is that the signing key grows in size when the message grows in size. We will deal with matrices that contain billions of entries and require millions of comparisons to verify. Therefore LDOTS has not really made it far in the world of practical cryptography applications. Nonetheless it remains interesting to find out, how we can use Merkle Trees to at least solve the problem of one-time use. But this is going to be part of the next article. Let me know in the comments if you would like to read that!