Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 41 ยท Cryptography Foundations

Digital Signatures with a Toy Scheme

Build a Lamport one-time signature from SHA-256 in Python, see why signatures prove authorization, why a key must not sign twice, and how replay attacks work.

A hash function can show that data has not changed, but it cannot show who approved it. A digital signature closes that gap. It is a small piece of data, computed from a message and a private key, that anyone can check with the matching public key. If the check passes, two things are true: the message is exactly the one that was signed, and the signer held the private key.

Real blockchains use elliptic-curve signatures, which need some number theory (that comes in the next lesson). To understand what a signature scheme is before the algebra gets in the way, this lesson builds one from nothing but SHA-256: the Lamport one-time signature. It is real, it is secure if the hash is secure, and it is simple enough to read in one sitting. It also teaches an important lesson through its flaw: a key that signs twice leaks itself.

The three operations

Every signature scheme has the same three functions:

Function Input Output
keygen randomness a private key and a public key
sign private key, message a signature
verify public key, message, signature true or false

Notice that verify needs no secret. That is what lets thousands of nodes check the same transaction independently. A transaction on a chain is essentially a message ("move these coins to that address") plus a signature, and every node runs verify before accepting it. The background on keys is in Public-Key Cryptography Basics.

How a Lamport signature works

The scheme signs a 256-bit hash of the message, one bit at a time.

  1. Private key: for each of the 256 bit positions, generate two random 32-byte secrets, one to use if the bit is 0 and one if it is 1. That is 512 secrets in total.
  2. Public key: hash every secret. The public key is the 512 hashes. Because hashing is one-way, publishing them does not reveal the secrets.
  3. Sign: hash the message to get 256 bits. For each position, reveal the secret that matches the bit (the "0" secret if the bit is 0, the "1" secret if it is 1). The 256 revealed secrets are the signature.
  4. Verify: hash the message the same way. For each bit, hash the revealed secret and compare it with the matching public hash.
flowchart LR
    M["Message"] --> D["SHA-256<br/>(256 bits)"]
    D --> B["For each bit i:<br/>pick secret 0 or 1"]
    SK["Private key<br/>(512 secrets)"] --> B
    B --> SIG["Signature<br/>(256 secrets)"]
    SIG --> V["Verifier hashes each secret<br/>and compares to public key"]
    PK["Public key<br/>(512 hashes)"] --> V

Signing reveals one secret per bit of the message hash; verifying hashes each secret and compares it with the public key.

To forge a signature for a different message, an attacker would need secrets they have never seen, which means inverting SHA-256. That is why the scheme is secure as long as the hash function is.

Building it in Python

The code below uses only hashlib and a seeded generator (for repeatable output; real keys need secrets, see the previous lesson). It signs a message, verifies it, and then shows that changing the message or the signature makes verification fail.

Python A Lamport signature from SHA-256

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A signature of 8,192 bytes is huge next to the 64 bytes of a typical elliptic-curve signature. Size is the price Lamport pays for needing nothing but a hash. Variants such as Merkle signature schemes shrink the public key by combining many one-time keys under a single Merkle root, and hash-based schemes of this family are studied as defenses against future quantum computers.

Why a signature proves authorization

Look at what the verifier learns. The signature contains secrets that hash to the published public key, and the chosen secrets depend on the message. Only the holder of the private key could have known them. So:

  • Integrity: change one bit of the message and the message hash changes in about half of its bits (the avalanche effect). Most positions then need the other secret, which the signer never revealed, so verification fails.
  • Authenticity: nobody without the private key can produce valid secrets.
  • Non-repudiation (practically): the signer cannot easily claim "that was not me", because only the key holder could have produced it. On a blockchain this is the entire basis of "I own these coins".

A signature does not say when it was made, and it does not say how many times it may be used. Both gaps matter, as the next two sections show.

The "one-time" in one-time signature

Each signature reveals one of the two secrets at every position. After one signature, an attacker knows 256 of the 512 secrets. After a second signature on a different message, the two hashes agree in about half of their positions and differ in the rest, so the attacker now knows about 384 secrets (386 in the run below), and so on. With enough signatures, the attacker holds nearly every secret and can assemble a valid signature for a message the owner never signed: search for a message whose hash bits all fall on secrets already revealed.

The next example signs eight different messages with the same key, tracks how much of the private key leaks, and then forges a signature.

Python Reusing a one-time key leaks it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The attacker needed no break of SHA-256 at all, only the owner's mistake of reusing a key. A related failure destroys real elliptic-curve signatures too: reusing the per-signature random number (see Elliptic Curves in Plain Language). Blockchains also avoid address reuse for a similar cultural reason: fewer signatures per key means less exposure.

Warning: the toy scheme above signs at most once per key pair. Never use it for anything real. It is here to teach the shape of signatures, not to protect value.

Replay: a valid signature is valid forever

Even a perfectly secure signature has a limit: it proves a message was approved, not that it was approved just now. Suppose Alice signs "pay Bob 5 coins". Bob (or anyone watching the network) can copy the message and signature and submit them again. Both are still valid, so the payment happens twice. This is a replay attack.

The fix is to put something unique inside the signed message so each copy is different, and make the verifier remember what it has already accepted. Blockchains use a per-account nonce (a counter, as in Ethereum) or consume specific coins that can only be spent once (as in Bitcoin; see UTXO vs Account Model). Many chains also include a chain ID in the signed data, so a signature for one network cannot be replayed on a fork or a test network.

Python Replay attack and a nonce defense

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because the nonce is part of the signed text, an attacker cannot change it without invalidating the signature, and cannot reuse an old one because the ledger already moved on. The keyed hash used in this demo is not a public-key signature: it is just a compact way to show the replay logic. In the real scheme, verify would use only the public key.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does verifying a signature require?

    Verification uses only public information, which is why every node can check every transaction on its own. Needing the private key would defeat the purpose.
  2. 2. In a Lamport signature, what do you reveal for each bit of the message hash?

    You reveal only the secret matching the bit (0 or 1). The other secret stays hidden, which is why a single signature does not expose the whole key.
  3. 3. Why must a Lamport key pair sign only once?

    Every signature exposes half of the secrets at the positions it covers. After several signatures, an attacker may hold enough of them to sign a new message.
  4. 4. What is a replay attack?

    A valid signature stays valid. Without a nonce, chain ID or spent-coin tracking, an old signed message can be submitted again.
  5. 5. Why is the nonce placed inside the signed message?

    Anything covered by the signature is protected from tampering. Editing the nonce changes the message, so the original signature no longer verifies.

Summary

  • A signature scheme has keygen, sign and verify; verification needs only the public key, so anyone can check it.
  • A Lamport signature reveals one of two secrets per bit of the message hash and is secure if the hash function is, but it is large (8,192 bytes here) and usable only once per key.
  • Reusing a one-time key leaks secrets until an attacker can forge a signature without breaking any hash.
  • A valid signature proves approval of one exact message, not freshness: replay protection needs a nonce, a chain ID or spent-coin tracking inside the signed data.
  • Real chains use elliptic-curve signatures, which are compact and reusable, with the same sign and verify roles.

Next: Elliptic Curves in Plain Language