What a digital signature gives

A digital signature is a number computed from a message and a private key that anyone holding the matching public key can check. If the check passes, the verifier knows two things:

  • Integrity: the message was not changed after it was signed, not even by one character.
  • Authenticity: it was signed by whoever holds the private key.

Because only the signer holds the private key, the signer cannot later deny having signed (non-repudiation). A MAC (such as HMAC) also gives integrity, but both sides share one secret key, so either of them could have made it and a third party cannot check it. A signature is also not encryption: the message travels in clear next to its signature. Encryption uses the recipient's public key so only the recipient can read; signing uses the sender's private key so everyone can check.

The animation uses textbook RSA with tiny numbers, so every value on the canvas can be checked with a calculator. Alice signs on the left, Bob verifies on the right, and Mallory sits on the channel in between: he sees every packet, can change it, and can write to the public-key directory.

RSA key generation

  1. Pick two secret primes: p = 61, q = 53.
  2. The modulus n = p·q = 3233 is public.
  3. φ(n) = (p−1)(q−1) = 3120 is secret: computing it requires the factors of n.
  4. Pick a public exponent e = 17 with gcd(e, φ(n)) = 1 (real keys use 65537).
  5. Compute the private exponent d = e−1 mod φ(n) = 2753 with the extended Euclidean algorithm: 17 · 2753 = 46801 = 15 · 3120 + 1.

The public key is (n, e) = (3233, 17), the private key is d = 2753. By Euler's theorem, (xd)e = xe·d = x mod n for every x: the public exponent undoes the private one. Anyone who could factor n could compute φ(n) and then d, so real moduli have 2048 bits or more. Mallory has his own key pair (n = 2773, e = 17, d = 157), and the CA has one too (n = 8633, e = 5, d = 5069).

Signing and verifying

Alice (private key d)                         Bob (public key n, e)
  h  = H(m) mod n                               h'  = H(m') mod n
  s  = h^d mod n        ──── (m, s) ────▶        h'' = s'^e mod n
                                                valid  ⇔  h' = h''

With the demo's message pay Bob $10: the toy hash is FNV-1a, 0xf6f5f047 = 4143312967, and 4143312967 mod 3233 = 390. Alice signs: s = 3902753 mod 3233 = 2585. Bob hashes what he received (390 again) and computes 258517 mod 3233 = 390: equal, so the signature is valid. Exponentiation uses square-and-multiply, one squaring per bit of the exponent and one multiplication per 1-bit, so even 2048-bit exponents need only a few thousand multiplications. Verification is much cheaper than signing because e is small.

Change the message to pay Mallory $1000 and its hash becomes 2686: Bob's two numbers no longer match. Change the signature by one and s'e is a completely different number (RSA is a permutation of the numbers below n, so no other s gives 390). Mallory can sign anything he likes, but with his d; Alice's e does not undo it. Run Demo: tampering is detected and Demo: Mallory signs with his own key.

Alice hashes pay Bob $10 to 390 and signs it with d = 2753, giving s = 2585; the message and signature cross the channel in clear; Bob hashes the message to 390 and computes 2585^17 mod 3233 = 390, equal so valid; if Mallory changes the message to pay Mallory $1000 the hash becomes 2686 and the check fails
Alice signs the hash with her private key; Bob recomputes the hash and undoes the signature with her public key: the two numbers match only if nothing changed.

Whose public key? Certificates

The check proves only that the message was signed with the private key matching the public key Bob used. If Mallory can replace Alice's entry in an unauthenticated key directory with his own public key, he signs his message with his own key and Bob's check passes: the arithmetic is correct, but Bob was checking against the wrong key (Demo: why public keys need certificates, first run).

A certificate solves this with another signature: a certificate authority checks that the key belongs to Alice and signs the pair {Alice, 3233, 17} with its own private key. Bob already has the CA's public key in his trust store, so he verifies the certificate first, exactly like a message signature, and only then uses the key inside. Mallory can make a certificate for his key that says "Alice", but he cannot sign it as the CA: his fake certificate {Alice, 2773, 17} hashes to 7875, but its signature gives 21555 mod 8633 = 7773, so Bob rejects it. On the web, the chain is longer (leaf, intermediate, root), and the server proves it holds the certificate's private key by signing the handshake: see How an HTTPS connection is established.

Two panels: with a plain key directory Mallory replaces Alice's key with his own (2773, 17), signs with d = 157 and Bob's check passes against the wrong key; with a CA certificate {Alice, 3233, 17} Bob verifies the certificate with the CA key (8633, 5), and Mallory's fake certificate fails because its hash is 7875 but its signature gives 7773
A correct signature only means "made with the key matching this public key"; the CA's signature on the certificate tells Bob the key is really Alice's.

Why hash first, and why the hash must be long

Textbook RSA without a hash is malleable: (m1d)·(m2d) = (m1·m2)d mod n. After seeing Alice sign 7 (s = 2667) and 11 (s = 804), Mallory computes 2667 · 804 mod 3233 = 789, a valid signature of 77 that Alice never made (Demo: why hash before signing). With a hash, the product signs the number h1·h2, and Mallory would need a message whose hash is that number: a preimage, which a good hash makes infeasible. Hashing also lets a signature cover a message of any length with one RSA operation.

The hash must be collision resistant, because a signature signs the hash and therefore every message with that hash. The toy hash has only 3233 values, so Mallory tries pay Mallory $1, $2, ... and after 6171 tries finds one with the same hash as pay Bob $10: Alice's signature is valid for it too (Demo: why the hash must be long). For SHA-256 a collision takes about 2128 hash computations. Real attacks of this kind happened with MD5: in 2008 researchers used an MD5 collision to obtain a rogue CA certificate, and in 2012 the Flame malware forged a Microsoft code-signing certificate the same way.

Padding: what real RSA signatures add

Real RSA never signs a bare hash. PKCS#1 v1.5 signs 00 01 FF FF … FF 00 || DigestInfo || SHA-256(m), filling the whole modulus; RSA-PSS adds a random salt and a mask, and has a security proof. Padding removes the multiplicative structure and makes each signature a full-size number. Implementations must also check the padding strictly: lenient parsers have accepted forged signatures (the Bleichenbacher e = 3 attack of 2006).

ECDSA and Ed25519

Most new systems sign with elliptic curves: a 256-bit key gives about the security of 3072-bit RSA, and signatures are 64 bytes. ECDSA needs a fresh secret random number k for every signature; signing two messages with the same k reveals the private key, which is how the PlayStation 3 signing key was recovered in 2010. Ed25519 derives k deterministically from the key and the message, which removes that failure mode. The structure stays the same as in the animation: hash, private-key operation, public-key check.

Where signatures are used

  • TLS: certificates are signed by CAs, and the server signs the handshake transcript (CertificateVerify).
  • Software: code signing on Windows and macOS, signed packages in apt, rpm and app stores, signed firmware and secure boot.
  • Tokens and documents: JWTs signed with RS256 or ES256, signed PDFs, DNSSEC records.
  • Version control: signed git commits and tags (GPG or SSH keys).