Cryptography Explorer

Part 1 — The problem

Two strangers on a wiretapped line

Suppose someone needs to send you a secret, and the only channel is one everybody can hear. You have never met, so you cannot agree on a password first — it would travel down the same wire the eavesdropper is on.

For most of cryptography's history nobody solved this. Scrambling the message was the easy half; getting the key to the far end was the expensive, fragile half — the key distribution problem.

RSA breaks it by giving you two matching keys instead of one shared password. Picture a crate of open padlocks with your name on them, handed to anyone who asks: that crate is your public key. You keep back the one key that opens them — your private key.

Anyone can click a padlock shut on a box; that is encrypting. Only your key opens it; that is decrypting. Handing out an open padlock gives nothing away — you cannot work backwards from shackle to key.

Part 2 — Where it came from

1976, 1977, and a puzzle in a magazine

In November 1976, Whitfield Diffie and Martin Hellman published New Directions in Cryptography. It proposed public-key cryptography and a way for two parties to agree on a shared secret over an open line — but not the padlock itself.

At MIT, Ron Rivest, Adi Shamir, and Leonard Adleman went after that gap, Adleman breaking each candidate the other two proposed. In April 1977 one held up, published in February 1978 in Communications of the ACM. The name is their three initials.

Martin Gardner had already described the scheme in the August 1977 Scientific American, with a challenge attached: a ciphertext under a 129-digit modulus. RSA-129 stood for seventeen years, falling in April 1994 to hundreds of volunteers pooling thousands of machines. The message read The Magic Words are Squeamish Ossifrage.

Rivest, Shamir, and Adleman received the Turing Award in 2002.

Part 3 — Why primes

The lopsided fact at the center

A prime is a whole number divisible only by 1 and itself, and everything RSA does rests on one lopsided fact: multiplying two primes is easy, splitting the answer apart is hard. Multiply 61 by 53 and you get 3233 in a blink. Handed only 3233, recovering 61 and 53 means hunting for factors — feasible on paper, infeasible once the primes run to hundreds of digits.

That shape is a one-way function: cheap forwards, brutal backwards. RSA needs a trapdoor one-way function — hard to reverse unless you hold one extra piece of information. Multiplying the primes is the one-way part; knowing which primes is the trapdoor. Your private key is that trapdoor in usable form.

Part 4 — Building the modulus

Two primes, one public number

The lab finds p and q by trial division: divide a random odd candidate by every odd number up to its square root, and if nothing divides evenly it is prime. Honest, visible, hopeless at real scale. Production keys use Miller–Rabin, a probabilistic test whose every round either proves the candidate composite or raises confidence that it is prime.

Watch the primality search in the lab

With your primes: … × … = …. That n sets the size of the world: every result from here on is taken mod n, the remainder after dividing by n, so numbers wrap instead of growing. It goes into both keys and is published openly.

Nothing about n is secret. What is secret is that it came from two particular primes — and we now throw away the multiplication that made it.

See n assembled in the lab

Part 5 — The gear ratio

The totient, and choosing the locking power

Next comes a secret helper: Euler's totient, φ(n). It counts how many numbers from 1 up to n share no common factor with n — fiddly in general, but for a product of two primes there is a shortcut.

On your numbers: (… − 1) × (… − 1) = … × … = …. Think of φ(n) as the hidden gear ratio linking the two keys — what lets us build an unlocking exponent that exactly undoes the locking one. The shortcut needs p and q, which makes φ(n) as sensitive as the private key itself.

Watch φ(n) computed in the lab

Now the public exponent e — the locking power, the number a message is raised to in order to encrypt it. It must sit between 1 and φ(n) and be coprime to φ(n), which guarantees the locking step can be undone by exactly one unlocking number.

For your φ(n) the search settles on e = …. In practice almost every real RSA key uses e = 65537: it is 2¹⁶ + 1, it is prime, and in binary it is a 1, fifteen zeros, then another 1 — so raising a number to it costs sixteen squarings and one multiply. It also stays clear of tiny exponents like 3, which have caused real trouble in careless implementations.

Test candidate exponents in the lab

Part 6 — The unlocking number

Deriving d, then burning the scaffolding

The private exponent d is the unlocking power, and the one number that never leaves your possession. It is the partner that exactly undoes e.

We find it with the extended Euclidean algorithm, which hunts for whole numbers x and y satisfying e·x + φ·y = 1. That x, reduced mod φ(n), is our d.

Follow the extended Euclid table in the lab

On your numbers it lands on d = … — check: … × … mod … = 1. The pair is complete: the public key (…, …) goes out to the world, the private key (…, …) into the safe. Both share the same modulus — only the exponent differs.

And now we delete p, q, and φ(n). They were scaffolding, and anyone who recovers one rebuilds d in seconds.

Assemble the key pair in the lab

Part 7 — The round trip

Snapping the padlock shut, and opening it

To encrypt, turn the message into a number m, raise it to the public exponent, and take the remainder mod n — computed by square-and-multiply. Only the public key is involved — a stranger can lock something that only you can open.

Your message's first character, …, is byte … — and …^… mod … = …. Character by character, … becomes ….

Watch a message encrypt in the lab

To decrypt, do the same with the private exponent: …^… mod … = …, and the whole ciphertext walks back to ….

Recover the plaintext in the lab

Why does the original come back out? Because e and d were built as inverses mod φ(n), and a result of Euler's guarantees that raising to the e-th power and then the d-th returns you where you began — a theorem, not a coincidence anyone tuned by hand.

Part 8 — Why it holds

The wall behind the private key

An eavesdropper has your public key, (n, e) — most of what you had when you computed d. Why can they not repeat your work? Because every route to d runs back through the primes. To get d, they need φ(n). To get φ(n), they need p and q. To get those, they have to factor n.

Factoring is the wall. For the lab's toy modulus — four digits, from two primes under 250 — the wall is knee-high, and a laptop steps over it instantly. A 2048-bit modulus runs to roughly 617 decimal digits, and the best published general-purpose method, the number field sieve, gets nowhere near it.

That is why 2048 bits is the working minimum today, with 3072 and 4096 for keys that must hold for decades. The lab's arithmetic is identical to your bank session's; only the size differs, and the size is the whole security argument.

Part 9 — RSA in the wild

Where you actually meet it

RSA's dominant job today is signatures. A TLS certificate is a statement signed with a private key and checked with the matching public key. The same mechanism signs software releases and authenticates SSH logins.

What has moved away from RSA is key exchange. Session secrets are now agreed with elliptic-curve Diffie–Hellman, which is faster and gives forward secrecy: a stolen long-term key cannot unlock recorded traffic. TLS 1.3 removed RSA key transport entirely.

And when public-key crypto does encrypt, it almost never encrypts the data. Asymmetric math is far slower than a symmetric cipher like AES, and a message longer than the modulus does not fit. So real systems use hybrid encryption: encrypt the payload with a random symmetric key, then use the recipient's public key to wrap that short key. The padlock guards a small envelope, and the envelope holds the key to the warehouse.

Part 10 — Further reading

Go to the sources

The original paper is A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, shorter and more readable than you would expect.

The paper that set the problem is Diffie and Hellman's New Directions in Cryptography. Read the opening page even if you skip the rest.

The terminal animations behind this site owe their approach to the SHA-256 Animation project — keep the real math in one small library, and let everything else animate it.