Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 40 ยท Public-Key Cryptography

Digital Signatures

Learn how digital signatures prove who wrote a message. Build toy RSA and DSA-style signatures, see why we hash first, and recover a key from a reused nonce.

A MAC proves that a message came from someone who knows a shared key. That is not enough when there is no shared key, or when you need a third party to be convinced. If a bank says "you signed this transfer" and you say "I never did", a MAC cannot settle the argument, because the bank holds the same key and could have made the tag itself.

A digital signature fixes this with a key pair. Only the holder of the private key can produce a signature; anyone with the public key can check it. This gives you authentication (who wrote it), integrity (it has not changed) and non-repudiation (the signer cannot plausibly deny it). Software updates, TLS certificates, Git tags, passports and cryptocurrency transactions all rest on signatures.

In this lesson you build two toy signature schemes, an RSA one and a DSA-style one, and then break the second one with a mistake that has sunk real products.

The shape of every signature scheme

Every scheme has three algorithms:

  1. KeyGen makes a private key and a matching public key.
  2. Sign(private key, message) returns a signature.
  3. Verify(public key, message, signature) returns true or false.

Signatures do not sign the message directly. They sign a fixed-size hash of it. That is called hash-then-sign, and it matters for three reasons: it handles messages of any length, it is fast, and it prevents algebraic tricks on the raw signing function (you will see one below).

flowchart LR
    M["Message"] --> H1["Hash"]
    H1 --> S["Sign with<br/>private key"]
    S --> SIG["Signature"]
    M2["Message received"] --> H2["Hash"]
    SIG --> V["Verify with<br/>public key"]
    H2 --> V
    V --> R["Accept or reject"]

The signer hashes then signs; the verifier hashes the received message and checks it against the signature.

RSA signatures: sign with d, verify with e

If you have not built RSA yet, the only fact you need is this: a key pair has a modulus n, a public exponent e and a private exponent d, and pow(pow(m, d, n), e, n) == m. Encryption uses e first. A signature reverses the roles: raise the hash to the power d (only the owner can) and let everyone undo it with e.

The code below generates a small key (256 bits, far too short for real use) and implements hash-then-sign. It then shows what goes wrong if you skip the hash. Raw RSA is multiplicative: the signature of a * b is the product of the signatures of a and b. An attacker who has seen signatures on two messages can manufacture a valid signature on a third, without the private key.

Python Toy RSA signatures and the no-hash forgery

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 forgery works because (a^d) * (b^d) = (a*b)^d. Hashing first breaks that structure: nobody can find a message whose hash is 77, or the product of two other hashes, because the hash is one-way. Real RSA signatures use a padding scheme called PSS on top of the hash; see RSA padding and pitfalls.

A DSA-style signature

RSA signatures are easy to explain, but many modern schemes (DSA, ECDSA, Schnorr, EdDSA) work differently. They live in a group where the discrete logarithm problem is hard, as in Diffie-Hellman. The private key is a number x. The public key is y = g^x mod p. Parameters are a prime p, a smaller prime q that divides p - 1, and a generator g of the subgroup of size q.

To sign a message with hash h, pick a fresh random number k (the nonce) and compute:

  • r = (g^k mod p) mod q
  • s = k^-1 * (h + x*r) mod q

The signature is the pair (r, s). To verify, compute w = s^-1, then u1 = h*w and u2 = r*w (all mod q), and accept if (g^u1 * y^u2 mod p) mod q == r. Substituting y = g^x shows why that works: the exponent u1 + x*u2 equals k, so the verifier recomputes exactly the same g^k.

The next example builds its own parameters. It starts from the Mersenne prime q = 2^127 - 1, then searches for a multiple k*q + 1 that is also prime, which is how DSA parameter sets are made. Again, these sizes are for learning only.

Python A DSA-style signature scheme

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.

Notice the last line: signing the same message twice gives two different valid signatures, because each one uses a fresh nonce. That randomness is the scheme's most dangerous ingredient.

Nonce reuse: one mistake reveals the private key

Look at the equation for s again: s = k^-1 * (h + x*r) mod q. If an attacker sees two signatures made with the same k, then r is identical in both, and they have two equations with two unknowns, k and x.

Subtract them: s1 - s2 = k^-1 * (h1 - h2), so k = (h1 - h2) / (s1 - s2) mod q. With k known, solve either equation for the private key: x = (s1*k - h1) / r mod q. No hard problem is solved at any point; it is plain algebra.

This is not a hypothetical. In 2010 a console maker's firmware signatures were broken because the ECDSA nonce was a constant, which exposed the private signing key. In 2013 Android's weak random number generator produced repeated nonces for Bitcoin wallets, and funds were stolen from them. Even a biased or partially predictable nonce can leak the key to an attacker with enough signatures and some lattice mathematics.

Python Recovering a private key from a reused nonce

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.

Two defenses are standard. First, generate nonces from a cryptographically secure source. Second, and better, make the nonce deterministic: derive it from the private key and the message with a hash or HMAC, as RFC 6979 does for ECDSA and as Ed25519 does by design. A deterministic nonce never repeats for different messages and needs no random number generator at signing time.

Choosing a scheme in practice

  • Ed25519 is the usual modern default: small keys (32 bytes), 64-byte signatures, fast, deterministic nonces and few ways to misuse it.
  • ECDSA over P-256 is everywhere (TLS, hardware tokens, JWT's ES256). It is sound but unforgiving about nonces.
  • RSA-PSS (not the older PKCS#1 v1.5 padding where avoidable) remains common because of legacy support; keys are at least 2048 bits.
  • Never invent your own padding, skip the hash, or verify only part of the signed data.

Also remember what a signature does not tell you: that the public key really belongs to who you think. Binding keys to identities is the job of certificates.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What property can a digital signature give that a MAC cannot?

    A MAC key is shared, so either party could have produced the tag. A signing key is private, so a valid signature points to one signer.
  2. 2. Why do signature schemes hash the message before signing?

    The hash gives a fixed-size input and removes structure such as RSA's multiplicative property, which would otherwise let attackers combine existing signatures.
  3. 3. Two DSA-style signatures were made with the same nonce k. What can an attacker do?

    Because r is the same, subtracting the two s equations gives k, and then either equation gives the private key x. After that the attacker can sign anything.
  4. 4. How does Ed25519 avoid nonce-reuse failures?

    A deterministic nonce is a hash of secret and message, so it is unique per message and never depends on the quality of a random number generator.
  5. 5. Signature verification succeeds. What is still unproven?

    Verification links the message to a key. Linking a key to a real-world identity needs certificates or another trusted way to distribute public keys.

Summary

  • A signature scheme has KeyGen, Sign (private key) and Verify (public key); it provides authentication, integrity and non-repudiation.
  • Always hash-then-sign. Raw RSA signatures are multiplicative and can be forged by combining old ones.
  • DSA, ECDSA, Schnorr and EdDSA signatures use a per-message nonce k; the same algebra works in integers modulo a prime and on elliptic curves.
  • Reusing or leaking a nonce, even partially, reveals the private key. Use deterministic nonces (RFC 6979, Ed25519) or a secure random source.
  • A valid signature only proves possession of a private key; mapping keys to identities needs certificates.

Next: Certificates and Public-Key Infrastructure, where signatures are used to vouch for other people's keys.