On this page
RSA lets anyone lock a message for you while only you can open it. It was described in February 1978 in Communications of the ACM by R. L. Rivest, A. Shamir and L. Adleman of MIT, and the whole idea uses maths you already know: prime numbers, remainders and powers. Below we build a real key with primes small enough to check on paper.
How does RSA encryption work, in simple terms?
RSA uses two keys: a public key you can show the world and a private key you keep. In the original paper's words, "publicly revealing an encryption key does not thereby reveal the corresponding decryption key" (Rivest, Shamir and Adleman, 1978).
The recipe in that paper has three parts:
A message is written as a number M, raised to a public power e, and the remainder is taken on dividing by n, the product of two secret primes p and q.
Decryption is the same move with a secret power d instead of e.
d is chosen so that e × d leaves remainder 1 when divided by (p − 1)(q − 1).
The paper states that the security of the system rests in part on how hard it is to factor the public number n back into p and q.
A worked RSA example with the primes 3 and 11
Take p = 3 and q = 11. You can check every step below with a pen.
Multiply: n = 3 × 11 = 33. This is public.
Work out (p − 1)(q − 1) = 2 × 10 = 20. This stays secret.
Pick a public power e that shares no factor with 20. Take e = 3. Your public key is (33, 3).
Find the private power d so that 3 × d leaves remainder 1 on division by 20. Since 3 × 7 = 21 = 20 + 1, d = 7.
Encrypt the message M = 4: 4³ = 64, and 64 = 33 + 31, so the ciphertext is C = 31.
Decrypt by computing 31⁷ mod 33. Notice that 31 = 33 − 2, so 31 behaves like −2. Then (−2)⁷ = −128, and −128 + 4 × 33 = 4. The message comes back: 4.
Anyone who sees 31 and knows (33, 3) still needs d = 7, which needed 20, which needed the primes 3 and 11.
Why does decryption give the original message back?
The secret number (p − 1)(q − 1) is Euler's totient of n: the count of numbers below n that share no factor with it, which we explain in how many numbers below n are coprime to n. Euler's theorem says that a number sharing no factor with n, raised to a multiple of that count plus one, comes back to itself mod n. Because e × d = 1 + (a multiple of 20), M to the power e and then to the power d returns M. A short extra argument covers the rare messages that do share a factor with n.
For real keys you cannot find d by trial and error. You find it with the extended Euclidean algorithm, the same steps as writing gcd(a, b) as ax + by with Bézout's identity. If totients or modular inverses are new to you, the Fermi Concept Library has its own lesson for every concept in mathematics and computing.
Why is factoring large numbers so hard?
Factoring 33 takes a second: try 2, then 3, done. For a number hundreds of digits long, even trying divisors up to its square root is far too much work, and cleverer methods still slow down sharply as numbers grow.
The largest integer factored with a general-purpose algorithm is RSA-250, a 250-digit number factored on 28 February 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann (Integer factoring records).
RSA-250 is the product of two 125-digit primes and has 829 bits, and factoring it took 2,700 years of computer-core time on tens of thousands of machines over a few months (UC San Diego). The same report notes that current practice calls for RSA keys of at least 2048 bits. Heninger, a professor of computer science at UC San Diego, said there: "Achieving computational records regularly is necessary to update cryptographic security parameters and key size recommendations."
A 2048-bit number has about 617 decimal digits (2048 × log₁₀ 2 ≈ 616.5), more than twice the length of RSA-250.
Try it yourself: an RSA practice plan
Choose p = 5 and q = 11. Find n and (p − 1)(q − 1). You should get 55 and 40.
Check that e = 3 shares no factor with 40, then find d. Since 3 × 27 = 81 = 2 × 40 + 1, d = 27.
Encrypt M = 8: 8³ = 512, which leaves 17 mod 55.
Decrypt 17 with d = 27 by repeated squaring: 17², 17⁴, 17⁸ and 17¹⁶ leave 14, 31, 26 and 16 mod 55. Since 27 = 16 + 8 + 2 + 1, multiply 16 × 26 × 14 × 17, reducing after each step. You should get 8.
Give a friend only n = 55 and e = 3, and time how fast they factor it. Then imagine an n as long as a real RSA key.
If a step goes wrong, the Fermi Problem Library works problems with a step-by-step solver that explains the reasoning, so you can see exactly where a remainder slipped.
If this is the kind of maths you enjoy, read about cryptography careers for maths lovers.
