Signature
Diffie and Hellman described what a signature would have to do and had no way to do it. Two years later Rivest, Shamir and Adleman had one, and it is the same pair of keys either way round: which half you keep decides whether you are encrypting or signing. Everything below is computed with primes small enough to read.
A key pair, a signature, a check anyone can run, and the one way to break it
1 A key pair, and which half you give away
Two primes make a modulus. The public exponent is chosen, the private one is derived from the primes, and that derivation is the only thing anybody has to keep.
- the modulus, public
- 52,961 (211 × 251)
- the public exponent
- 17
- the private exponent, kept
- 12,353
- e times d, modulo phi
- 1 — which is what makes it undo
2 Signing: the hash of the message, under the half you keep
The message is hashed to a number, and that number is raised to the private exponent. Only somebody with that exponent can produce this.
Signed: the meeting is at noon. Editing the box above does not re-sign it, because that is not something an attacker can do.
- the message, hashed
- 33,913
- the signature
- 9,372
3 Verifying, with the half everybody has
Verifying raises the signature to the PUBLIC exponent, which undoes the private one, and compares the result with the hash of the message in front of you.
- what the public exponent recovers
- 33,913
- the hash of the message shown
- 33,913
- do they match
- yes
4 Change one byte of the message and watch it stop verifying
Now change the message. The signature was made for a different number, so it recovers that different number, and the check fails without anybody needing to know what was changed.
| message | hashes to | recovers | verdict |
|---|---|---|---|
| "the meeting is at noon" | 33,913 | 33,913 | verifies |
| "the meeting is at one" | 12,409 | 33,913 | does not verify |
| "the meeting is at noon " | 34,825 | 33,913 | does not verify |
| "THE MEETING IS AT NOON" | 36,423 | 33,913 | does not verify |
- attempts to factor the modulus
- 210
- and the private exponent it recovers
- 12,353 — the private exponent exactly
The modulus factored in 210 attempts, and its factors give back the private exponent, which is the whole key. A real modulus is two thousand bits and the same loop does not finish. Nothing else about the scheme changes: only the size.
What is real here, and what is not
These primes are toys and the padding is absent
Three-digit primes, so a browser can factor the modulus while you watch. A real key is two thousand bits or more and the same loop would not finish. Nor is there any padding: textbook RSA without a padding scheme is broken in several ways that have nothing to do with the size of the primes, and every real implementation uses one.
The hash is not a cryptographic hash either
FNV-1a again, reduced modulo n. A signature scheme whose hash can be collided is forgeable no matter how large the primes are, so this is a second reason nothing here is usable. What the page is showing is the shape: sign the digest, not the message, and verify by undoing it with the public half.
Factoring is the only attack shown, and it is not the only attack
The page recovers the private exponent by factoring the modulus, because that is the attack the security argument is actually about. Real systems fall to timing, to bad randomness when the primes were generated, to reused moduli, and to implementation errors far more often than to factoring.
Sources
- R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, CACM 21(2), February 1978.
- W. Diffie and M. Hellman, New Directions in Cryptography, 1976, which set out what a signature would have to do before there was a way to do it.
- Logical Art, the studio this belongs to.