1978

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 arithmetic either way round — though not the same freedom, because publishing the wrong exponent hands over the factorisation: which half you keep decides whether you are encrypting or signing. Everything below is computed with primes small enough to read.

New to public keys? Start here

Ordinary secrets need both parties to know the same thing, which does not work when the checker is a stranger. A keypair is two matched values: one you keep and never send, one you publish to anyone.

What makes a signature possible is that an operation done with the private half can be undone with the public half, and not the other way round. So anybody can check that whoever made this had the private key, and nobody who checks learns anything that lets them do it themselves. That asymmetry is the whole subject.

Hard, not impossible

Nothing in this topic is unbreakable, and that is a claim about these machines rather than about cryptography. Each of them rests on an operation that is cheap in one direction and expensive in the other, and expensive means a number of steps so large that doing them costs more than the secret is worth. The one-time pad is the standing exception: it is not hard to break, it is impossible, and it is impractical for almost everything, which is why the rest of this topic buys difficulty instead.

That makes every claim here a claim with a date on it. Secure means secure for this long, against someone with this much to spend, assuming nobody finds a shortcut. The machines in this topic each rest on one of those one-way operations, and each is worth asking the same question about: what exactly would an attacker have to do, and how much of it.

The machine for this idea on its own is Diffie-Hellman, if you would rather press it than read about it.

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.

First prime: 211

Second prime: 251

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. With a proper signature encoding and a cryptographic hash, only somebody with that exponent can produce this.

The message

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.

Each message, its hash, what the signature recovers, and whether they match
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

These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.

Each claim, whether it held, and the values behind it
claim	held	measured
a signature made with the private half checks out with the public half	yes	digest 2013 signed to 2013 and recovered with e = 17 alone
changing one byte of the message makes the check fail	yes	expected 2300 and recovered 2013
changing one number of the signature fails as well	yes	the two failures are different: one moves the digest, the other moves what the exponent recovers
the two exponents are inverses: 17 times 2753 is 1 mod 3120	yes	that identity is the reason signing and checking undo each other
factoring this modulus takes 52 attempts, which is why these primes are a demonstration and not a key	yes	n = 3233 = 53 x 61; a real modulus is 600 digits and this is three
and with the factors the private exponent falls out: 2753, the same one	yes	nothing else has to be guessed once n is factored

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. Size is not the only difference: a real signature hashes the message and wraps it in PSS or PKCS#1 encoding before the private operation, which is what closes the forgery this page shows rather than merely making it expensive.

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 what the security of the scheme rests on, and it is sufficient to break the scheme rather than proved to be necessary. 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

Logical Art builds interactive explanations of difficult machines.

The machines:

1933-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop nobody wrote. It cost a day.
1971-1995 Line ModeFor a while you could telnet to port 80 and be the browser.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

A few more, on the studio: Morse, Stored Program, Raster, Garbage, CPU Cache, Fifteen Planes, Checkout, RAID Parity. Or browse every Bit, every Nibble, or the whole chronology.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.