Secrets from Primes

Chapter 3 RSA and Diffie–Hellman

Public-key cryptography

Two strangers can agree on a secret, or send one, in full view of an eavesdropper. RSA and Diffie–Hellman do it with clock arithmetic and primes too large to find.

10 min read · 4 interactive figures · 3 questions

RSA on a clock of n = 5 × 11 = 55 hours with public exponent e = 7. Every faint chord sends an hour x to x⁷ mod 55 (small loops mark hours that encrypt to themselves); the red arrow is the encryption of the message under the hand, the dashed green arrow its decryption with d = 23. Drag the hand or type a message; change the primes to build other clocks.

Public-key cryptography lets anyone lock a message with a key that is published openly, while only the holder of a matching private key can open it. RSA does this by raising numbers to a power on a clock of n = p × q hours: the power e is public, and the power d that undoes it can be worked out only by someone who knows the primes p and q. Diffie–Hellman lets two people who have never met agree on a shared secret while an eavesdropper hears every word. Both rest on the clock arithmetic of chapter 2 and on the fact from chapter 1 that multiplying primes is easy and unmultiplying them is not.

The dial above is RSA itself, with primes small enough to see. Every faint chord sends an hour to its seventh power mod 55. The chords never collide (each hour is hit exactly once), so the scramble can be reversed; the dashed green arrow is the reversal, done by raising to the power 23. The rest of this chapter explains where 23 comes from, why nobody else can find it when the primes have 300 digits, and how big the real numbers are.

The problem: agreeing on a key in public

For most of history, encryption meant a shared secret key: the same key locks and opens, so both sides must have it before they can talk privately. That is fine for two spies who meet in advance and useless for a web browser that has never met the bank's server. In 1976 Whitfield Diffie and Martin Hellman published “New directions in cryptography”, which proposed two ideas: a way for two parties to agree on a key over a public channel, and the notion of a public-key cryptosystem in which the locking key can be published[1] documented. A year later Ron Rivest, Adi Shamir and Leonard Adleman found a practical public-key system, published in 1978 and named RSA after their initials[2].

Both systems need a one-way operation: easy to do, believed infeasible to undo. RSA uses multiplication of two large primes, undone only by factoring. Diffie–Hellman uses raising to a power modulo a prime, undone only by a discrete logarithm. In each case the owner of a secret has a shortcut back through the door.

RSA on a clock

Question 1 Prediction: what protects the private key?#

Here is the whole of textbook RSA, using the numbers on the dial[2][3] established:

  1. Choose two different primes, p = 5 and q = 11. Their product n = 55 is the number of hours on the clock.
  2. Compute φ(n) = (p − 1)(q − 1) = 4 × 10 = 40. This is the step that needs the primes.
  3. Choose a public exponent e with no factor in common with 40; here e = 7.
  4. Compute the private exponent d, the inverse of e modulo φ(n): 7 × 23 = 161 = 4 × 40 + 1, so d = 23. The extended Euclidean algorithm of chapter 2 finds it in a few steps.
  5. Publish (n, e) = (55, 7). Keep d, p and q secret.

To send the message m (a number from 0 to n − 1), anyone computes the ciphertext c = me mod n. The owner decrypts by computing cd mod n, which gives back m:

c = me mod n and m = cd mod n(1)

Why does decryption undo encryption? Because ed = 1 + kφ(n) for some whole number k (that is what “inverse modulo φ(n)” means), so

cd ≡ med = m · (mφ(n))k ≡ m · 1k = m (mod n)(2)

by Euler's theorem from chapter 2, whenever m shares no factor with n. (It also works for the rare messages that are multiples of p or q, by applying Fermat's theorem separately modulo p and modulo q[2].) On the dial you can check every case at once: with the chords on, every hour leaves along exactly one chord and arrives along exactly one, so the map is a permutation, and the green arrow always lands back on the hand.

Figure 1 The full calculation for p = 61, q = 53, e = 17 and the message 65: the key, then encryption to 2790 and decryption back to 65. Change any number; an unusable choice (a p that is not prime, an e that shares a factor with φ(n), a message ≥ n) is refused with the reason. Random primes picks new ones; Text encrypts a word one character at a time.#

Rivest, Shamir and Adleman's own paper works a small example with p = 47, q = 59, n = 2773 and d = 157, from which e = 17. They encode the message ITS ALL GREEK TO ME two letters to a block (blank = 00, A = 01, …), so the first block is 0920, and its ciphertext is 92017 mod 2773 = 948[2]. Type those numbers into the calculator to repeat a computation first printed in 1978; the engine's tests check all ten blocks of their ciphertext.

Switch the calculator to Text and encrypt HELLO. The two L's encrypt to the same number. An eavesdropper can count repeated ciphertexts and match them with common letters without ever learning d. Textbook RSA is deterministic, which is why real systems never encrypt a bare message: they first mix in fresh random bits in a carefully specified way, and in practice they use RSA mostly to protect a short random key for a fast symmetric cipher.

Why the private key stays private

An attacker knows n and e. To find d they need φ(n), and knowing φ(n) is as good as knowing the factors: from n = pq and φ(n) = n − (p + q) + 1 you get p + q, and two numbers with a known sum and product are the roots of a quadratic[3] established. So the obvious attack on RSA is to factor n. For the dial's 55, or the calculator's 3233, that is instant; this site's own checker splits a 24-digit product of two 12-digit primes in about a second. But the effort grows explosively with size.

No proof says factoring is hard. What exists is a long public record of failure to find a fast method, plus a few precise data points. The largest RSA challenge number factored so far, RSA-250 (829 bits), took a team of six researchers about 2700 core-years in 2020, using the number field sieve[4] documented. The moduli recommended today are more than twice as long, and every extra digit makes the job harder.

Diffie–Hellman: a shared secret in public

RSA lets you send a secret to the owner of a key. Diffie–Hellman lets two people make a secret together. Alice and Bob agree in public on a prime p and a base g. Alice picks a secret number a and sends A = ga mod p; Bob picks b and sends B = gb mod p. Then each raises what they received to their own secret[1][3] established:

Ba = (gb)a = gab = (ga)b = Ab (mod p)(3)
Question 2 Prediction: does the secret travel?#
Figure 2 A Diffie–Hellman exchange with p = 23, g = 5 and secrets a = 6 and b = 15. The column headed On the public wire is everything an eavesdropper sees; Alice’s and Bob’s columns both arrive at the shared secret 2. Change any number, or try the larger examples. Let Eve search tries exponents one at a time to recover a: instant for 23, hopeless for the 19-digit prime.#

The eavesdropper, traditionally called Eve, sees p, g, A and B. To get the secret she would need a or b, which means solving gx ≡ A (mod p) for x: the discrete logarithm from chapter 2. On the 23-hour clock her search ends almost at once. Press the 1018 + 3 example and let her search: two million tries cover a vanishing fraction of the possible exponents. Smarter algorithms than trying every exponent exist, but for well-chosen primes of 2048 bits none is known that finishes[5] active.

The base matters too. If g generates the whole clock (its powers visit all p − 1 nonzero hours, as 5 does modulo 23), the secret can be any of p − 1 values. If its powers repeat sooner, Eve's search space shrinks; the calculator reports the order of g for this reason. Real deployments use standardized groups chosen to avoid such weaknesses.

How big is big enough?

The dial has 55 hours and the calculator's key a 4-digit modulus. Real keys are much larger. Before you look, a question about the current factoring record.

Question 3 Prediction: the cost of factoring RSA-250#
Figure 3 Sizes of RSA moduli in bits: the calculator’s toy key, RSA-768 (factored 2009), RSA-250 (factored 2020) and RSA-2048 (never factored). The bars measure size, not effort: the cost of factoring grows far faster than the number of bits. The digits of the chosen number are printed in full below the bars. Multiply computes RSA-250 from its two published 125-digit factors in your browser and times it.#

The U.S. National Institute of Standards and Technology publishes the sizes it considers comparable in strength[5] documented. A “security strength” of 128 bits means an attack should cost about as much as trying 2128 keys of a good symmetric cipher.

Security strength (bits)Symmetric cipherRSA modulus (bits)Diffie–Hellman prime (bits)Elliptic curve (bits)
≤ 802TDEA10241024160–223
1123TDEA20482048224–255
128AES-12830723072256–383
192AES-19276807680384–511
256AES-25615 36015 360512+

NIST no longer approves sizes below 112-bit strength for protecting federal data, so 2048 bits (617 decimal digits) is the smallest RSA modulus it accepts for new use, and 3072 bits matches AES-128[5]. Each of the two primes in a 2048-bit key has about 309 digits. By the prime number theorem of chapter 1, about one number in 710 near that size is prime, so a computer finds such primes by testing random odd numbers with the strong test, a few hundred tries each. The last column shows why elliptic curves are attractive: on NIST's estimates a 256-bit elliptic-curve key matches a 3072-bit RSA modulus.

What the toy versions leave out

Everything on this page is real RSA and real Diffie–Hellman, with the arithmetic done exactly. What makes them toys is size and the absence of the engineering that real protocols add. The calculators state their limits: primes below 1012 for RSA, primes below 1024 for Diffie–Hellman, every prime checked exactly, every bad choice refused with a reason. None of them offers any security.