How RSA encryption works, with the numbers Image: Erik Tews (CC BY-SA 3.0)

How RSA encryption works, with the numbers

When your browser opens a secure connection, it checks a certificate, and the signature on that certificate is, more often than not, an RSA signature: a number raised to a large power modulo a 600-digit integer. The system was published by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977, and the same idea had been found in secret at GCHQ by Clifford Cocks in 1973. It rests on arithmetic that fits in Unit 5 of this masterclass. The numbers below are small enough to check with pencil and paper, and the mathematics is identical at 600 digits.

Making the keys

Choose two primes. We take p = 61 and q = 53. Multiply them: n = 61 × 53 = 3233. This n is the modulus, and it is public.

Compute φ(n) = (p - 1)(q - 1) = 60 × 52 = 3120. This is Euler's totient function, the number of integers from 1 to n that share no factor with n, and for a product of two distinct primes it is exactly (p - 1)(q - 1). It is the one number that must stay secret, because anyone who knows φ(n) and n can recover p and q by solving a quadratic.

Choose a public exponent e with no factor in common with 3120. We take e = 17. Then find the private exponent d, the inverse of e modulo 3120: a number with 17d ≡ 1 (mod 3120). The extended Euclidean algorithm of Unit 2 gives d = 2753, and you can verify it: 17 × 2753 = 46801 = 15 × 3120 + 1.

The public key is the pair (n, e) = (3233, 17). The private key is d = 2753. The primes and φ(n) are now destroyed or locked away.

Encrypting and decrypting

A message is a number m between 0 and n - 1; a longer message is cut into blocks, and in practice the number encrypted is a key for a faster cipher rather than the text itself. Take m = 65. The ciphertext is c = m^e mod n = 65^17 mod 3233.

Nobody computes 65^17 and then divides. The power is built by repeated squaring, reducing modulo 3233 at every step. First 65² = 4225, and 4225 - 3233 = 992. Then 992² = 984064, and 984064 - 304 × 3233 = 984064 - 982832 = 1232, so 65⁴ ≡ 1232. Then 1232² = 1517824, and 1517824 - 469 × 3233 = 1517824 - 1516277 = 1547, so 65⁸ ≡ 1547. Then 1547² = 2393209, and 2393209 - 740 × 3233 = 2393209 - 2392420 = 789, so 65¹⁶ ≡ 789. Since 17 = 16 + 1, the ciphertext is 789 × 65 = 51285, and 51285 - 15 × 3233 = 51285 - 48495 = 2790. So c = 2790, after four squarings and one multiplication instead of sixteen multiplications. The arithmetic is tedious and one slip ruins it, which is why there are computers; spend your attention on why it works.

To decrypt, raise the ciphertext to the private exponent: 2790^2753 mod 3233 = 65. The message comes back. A Python console does the whole exchange in two lines, pow(65, 17, 3233) and pow(2790, 2753, 3233), and the CrypTool page in the resources of Unit 5 shows every intermediate number.

Why decryption recovers the message

The claim is that (m^e)^d ≡ m (mod n) for every m. Since ed ≡ 1 (mod φ(n)), we can write ed = 1 + kφ(n) for some integer k. Then m^(ed) = m × (m^φ(n))^k.

Euler's theorem says that if m and n are coprime, then m^φ(n) ≡ 1 (mod n). That is the generalization to any modulus of Fermat's little theorem, which is the case of a prime modulus, and Unit 5 proves it by showing that multiplication by m permutes the invertible residues. With the theorem, (m^φ(n))^k ≡ 1, and so m^(ed) ≡ m. That is the whole proof for messages coprime to n.

A message that shares a factor with n is a different matter, and the usual textbook proof skips it. If m is a multiple of p but not of q, Euler's theorem does not apply modulo n, but Fermat's little theorem applies modulo q, giving m^(ed) ≡ m (mod q), while modulo p both sides are 0. The Chinese remainder theorem then combines the two congruences into one modulo pq. So decryption works for every message, including the ones that would in any case be a catastrophe, since a message sharing a factor with n reveals that factor by a gcd.

What an attacker can and cannot do

The attacker knows n = 3233 and e = 17 and sees c = 2790. To decrypt, they need d, and to find d they need φ(n), and to find φ(n) they need the factors of n. For 3233 that is a few seconds of trial division. For a modulus of 2048 bits, about 617 digits, it is beyond every known method. The largest RSA modulus factored in public is RSA-250, with 250 digits, done in February 2020 with the number field sieve and about 2,700 core-years of computation. Each additional 30 digits multiplies the effort by a large factor, and 617 digits is far out of reach, which is why 2048-bit keys are the current standard and 1024-bit keys were retired.

Nobody has proved that factoring is the only way to break RSA, and nobody has proved that factoring is hard. Both are conjectures, and the security of the system is the statement that nearly fifty years of public effort have not found anything better. That is a different kind of certainty from a theorem, and Unit 8 of the masterclass has something to say about the difference.

There is one known method that would break it: a large quantum computer running Shor's algorithm would factor n in polynomial time. No such machine exists, and the switch to other systems is under way in anticipation, under the name post-quantum cryptography. The arithmetic of this article will not stop being true, but it may stop being used.

Where the real breaks have come from

In practice RSA fails through implementation, not through mathematics. In 2012 Nadia Heninger and colleagues collected millions of public keys from devices on the internet and computed the gcd of every pair. If two devices had generated keys sharing one prime, which happens when a device has too little randomness at start-up, the gcd revealed that prime and both keys were broken. About half a percent of the TLS hosts they scanned were affected. The theorem that did the damage was Euclid's algorithm, the oldest in the book, and the research spotlight of Unit 5 is about this paper.

Other failures: choosing d small to make decryption fast (Wiener's attack recovers it when d is below roughly the fourth root of n), encrypting the same short message to several recipients with e = 3 (Håstad's attack recovers it with the Chinese remainder theorem), and the fault attack on the two-prime decryption described in the article on Sunzi's puzzle. Each of these is a theorem from Units 2, 4, and 5 pointed in a direction the designer did not expect.

Signatures, in one paragraph

Run the system backwards and it signs. The owner of the private key computes s = m^d mod n for a message m (in practice, for a hash of the message); anyone with the public key computes s^e mod n and checks that it equals m. Only the holder of d could have produced s, by the same argument that only the holder of d can decrypt. This is what your browser verifies when it checks a certificate, and it is why the same primes protect both the secrecy of a message and the identity of a website.

Unit 5 of the masterclass proves Fermat's and Euler's theorems, works through this example, and goes on to the primality tests that find the primes in the first place: a 300-digit prime is found in a fraction of a second, and the reason why is the prime number theorem.

Study the integers properly

The NT Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program
Keep reading

Related articles