# Implementing the Lamport one-time signature scheme in Python

** Published:**

Armed with a cryptographically secure one-way hash function and a secure source of randomness, we can build a digital signature scheme that is believed to be secure even with the advent of quantum computers. Created by Leslie Lamport at SRI International, the Lamport signature scheme is useful for many things.

In this post, I use SHA-256 as my cryptographically
secure hash function. My implementation in Python uses the *secrets* library for generating random
numbers (which defaults to using the most secure source of randomness provided by your operating
system).

## Digital signatures

Suppose **Alice** wishes to broadcast messages to her many friends. She creates a message
$m_{A} = \text{“Lamport signatures are cool! (from Alice)”}$ and broadcasts it. Her friend **Bob**
receives this message and reads it. But how can Bob be sure that this message came
from Alice, and is un-altered? For example, what if an evil person **Eve** writes a message $m_{E} =
\text{“Lamport signatures are NOT cool! (from Alice)”}$ and broadcasts it? Bob will receive this message
and think that Alice does not like Lamport signatures! Luckily for Alice, this is one of the many
problems solved by digital signatures!

## Lamport Signatures

Lamport signatures are a one-time signature scheme that allows Alice to sign her messages. This signature allows Bob and others to verify that messages which say “(from Alice)” were indeed constructed by Alice.

### Key generation

Suppose Alice wishes to broadcast messages to her many friends. For every message, a new public key / secret key pair $(pk, sk)$ must be generated. The secret key $sk$ takes the form of a $256 \times 2$ matrix of random numbers $r_x$.

From the secret key, another $256 \times 2$ matrix is created by hashing the secret key values: $y_{x}^{b} = SHA256(r_{x}^{b})$. This matrix is Alice’s public key $pk$.

This public key $pk$ must then be distributed to message recipients who wish to
verify the authenticity of Alice’s messages. For this post, we assume this is easy enough
(*spoiler alert*: this is not easy).

All of Alice’s friends (and also Eve) have access to this public key $pk$ made available by Alice. However, only Alice has access to her secret key $sk$.

### Message signing

To sign the message $m_A = \text{“Lamport signatures are cool! (from Alice)”}$,
Alice first hashes the message using a cryptographically secure hash function:
$h_{m_A} = SHA256(m_A)$ and observes
the binary representation of $h_{m_A}$. For each bit $b = \{0, 1\}$,
**Alice** appends $sk_i^b$
to the message signature. For example, if $h_{m_A} = 1011…01$:

The resulting message signature $s_{m_A}$ is therefore:

Alice can then broadcast the message/signature pair $(m_A, s_{m_A})$ to all of her friends.

### Message verification

When Bob receives $(m_A, s_{m_A})$ over the air, he wants first to verify that it did indeed come from Alice. To do this, he uses his access to Alice’s public key $pk$. First, the message $m_A$ is hashed using the same cryptographically secure hash function that Alice used: $h_{m_A} = SHA256(m_A)$. For each bit $b$ in the binary representation of $h_{m_A}$, Bob appends the corresponding public key value $pk_i^b$ to a string of bytes.

Finally, Bob can verify the signature $s_{m_A}$ by hashing each $256$-bit chunk of the signature, and verifying that it equals the corresponding string of bytes constructed from Alice’s public key:

When Bob sees that these two values are equal, he can be sure that this message came from Alice.
Furthermore, it is *hard* for some adversary (Eve) to forge signatures that Bob accepts.

## The hardness of forging a Lamport signature

Lamport signatures are secure due to the hardness of inverting a cryptographic hash function. Imagine Eve has the message $m_E = \text{“Lamport signatures are NOT cool! (from Alice)”}$, which she wishes to forge Alice’s signature for. For each bit $b$ in $h_{m_E} = SHA256(m_E)$, Eve must find a value $x_i$ such that $y_i^b = SHA256(x_i)$. This is difficult to do for many cryptographic hash functions (such as SHA-256), and is what is known as pre-image resistance. Furthermore, to forge signatures for arbitrary messages, Eve must do this for every $y^b_i$ i.e., find pre-images for $512$ different hashes provided by Alice’s public key. On the average case, a SHA-256 hash takes $2^{256}$ tries to find a pre-image. This is infeasbile and is what makes this signature scheme secure (as long as you only use each key once).

What happens if Alice uses a key to sign two different messages $m_1$ and $m_2$? Observe that $h_{m_1} = SHA256(m_1)$ and $h_{m_2} = SHA256(m_2)$, will differ in approximately half of their bits on average. For each bit $b_i$ where $h_{m_1}$ and $h_{m_2}$ differ, the adversary learns the secret key values $r_{i}^0$ and $r_{i}^1$ that are used to produce the corresponding values in the public key. For these bits, Eve is able to assign values arbitrarily.

As a toy example, consider the case where:

$h_{m_1} = 0100110…011$

$h_{m_2} = 1101011…010$

Eve will be able to construct messages of the form:

$h_{m_3} = SHA256(m_3) = b10bb1b…01b$

where each $b$ value can be either a $0$ or $1$. This implies that Alice loses
about *half* of her security each time she re-uses her keypair to sign a message. Therefore,
after re-using the same key to sign just $5$ messages, Alice reduces her security from a
problem that would take over the age of the universe for Eve to solve in order to sign a single
message, to allowing Eve to sign almost any message without having to solve anything.

## Key and signature size

Note that these digital signatures are not very succinct. The signature itself
is $(256\cdot 256)$ bits $= 8$ kilobytes. Even worse, the public and private keys are each
$2\cdot(256\cdot 256)$ bits $= 16$ kilobytes. This is not to say
that signing, verification, and key generation are not *fast* or even that they are
inferior to other digital signature schemes. However, in many settings this overhead in signature size
can be an unacceptable cost e.g., power-constrained devices running on mobile ad hoc networks.

## Implementation in Python

Below is an implementation of the Lamport one-time signature scheme in Python3. I usually try to provide an interface for readers to try out the code from the browser (see my posts on Miller-Rabin primality test, solving discrete log in Bash, etc.); however, I’m not providing one for this post. The primary reason being that signatures are 8KB in size, and I don’t think that will display nicely on the page. Feel free to copy and paste the code and try it out on your own!

```
#!/usr/bin/python3
# Author: Zachary Ratliff
# Simple Python implementation of Lamport signature scheme
import hashlib
import math
import secrets
import sys
CHAR_ENC = 'utf-8'
BYTE_ORDER = sys.byteorder
SK = 0
PK = 1
# Generate a keypair for a one-time signature
def keygen():
sk = [[0 for x in range(256)] for y in range(2)]
pk = [[0 for x in range(256)] for y in range(2)]
for i in range(0,256):
#secret key
sk[0][i] = secrets.token_bytes(32)
sk[1][i] = secrets.token_bytes(32)
#public key
pk[0][i] = hashlib.sha256(sk[0][i]).digest()
pk[1][i] = hashlib.sha256(sk[1][i]).digest()
keypair = [sk,pk]
return keypair
# Sign messages using Lamport one-time signatures
def sign(m, sk):
sig = [0 for x in range(256)]
h = int.from_bytes(hashlib.sha256(m.encode(CHAR_ENC)).digest(), BYTE_ORDER)
for i in range(0,256):
b = h >> i & 1
sig[i] = sk[b][i]
return sig
# Verify Lamport message signatures
def verify(m, sig, pk):
h = int.from_bytes(hashlib.sha256(m.encode(CHAR_ENC)).digest(), BYTE_ORDER)
for i in range(0,256):
b = h >> i & 1
check = hashlib.sha256(sig[i]).digest()
if pk[b][i] != check:
return False
return True
keypair = keygen()
message = "Lamport signatures are cool!"
sig = sign(message, keypair[SK])
verify(message, sig, keypair[PK])
```