Lesson · Number Theory and Cryptography · Cryptography

RSA Encryption

Generate n = pq, choose e coprime to φ(n), compute d = e⁻¹ mod φ(n). Encryption is m^e mod n and decryption c^d mod n. Every step is a theorem from this course, and the security is one unproved assumption.

Open the interactive lesson Practice

n = pq, φ(n) = (p−1)(q−1), gcd(e, φ(n)) = 1, d = e⁻¹ mod φ(n) PUBLIC (n, e) PRIVATE (d, and p, q) encrypt c = m^e mod n decrypt m = c^d mod n security: factoring n is believed hard. It is not proved.

The whole system

Core ideas

What this lesson establishes

RSA uses six results from this course and adds one assumption. Naming both lists is the honest way to present it.

Correctness is Euler's theorem

ed ≡ 1 (mod φ(n)) makes m^{ed} ≡ m (mod n), which is why decryption returns the message.

The public key reveals n, not φ(n)

Knowing φ(n) = (p−1)(q−1) together with n = pq gives p and q immediately. So φ(n) is as secret as the factorisation.

Security is an assumption, not a theorem

No proof exists that factoring is hard, and no proof exists that breaking RSA requires factoring. Both are believed and neither is established.

The material

RSA

Key generation, the correctness proof, the attacks, and the honest caveats.

Key generation

1. choose two large distinct primes p, q 2. n = p·q 3. φ(n) = (p−1)(q−1) 4. choose e with 1 < e < φ(n) and gcd(e, φ(n)) = 1 5. compute d = e⁻¹ mod φ(n) extended Euclid PUBLIC KEY (n, e) PRIVATE KEY (n, d) and p, q, φ(n) must stay secret

Every step is a lesson from this course: primality testing from “Fermat's Little Theorem and Euler's Theorem”, the totient formula from “Fermat's Little Theorem and Euler's Theorem”, coprimality from “Greatest Common Divisor”, and the modular inverse from “Bézout's Identity and Modular Inverses”.

Encryption and decryption

With the message encoded as an integer m with 0 ≤ m < n, encryption is c = m^e mod n and decryption is m = c^d mod n. Both are single modular exponentiations, computed by “Modular Exponentiation”'s algorithm.

Theorem · Correctness

For 0 ≤ m < n, (m^e)^d ≡ m (mod n).

ed ≡ 1 (mod φ(n)) means ed = 1 + kφ(n) for some integer k, so m^{ed} = m · (m^{φ(n)})^k.

If gcd(m, n) = 1, Euler's theorem gives m^{φ(n)} ≡ 1 (mod n), so m^{ed} ≡ m.

If gcd(m, n) ≠ 1 the argument still works via the Chinese remainder theorem: modulo p, either p | m and both sides are 0, or Fermat gives m^{p−1} ≡ 1 and m^{ed} ≡ m. The same holds modulo q, and since p and q are coprime the congruence holds modulo n.

□

Four of this course's theorems appear in that proof. RSA is not an application of number theory so much as an assembly of it.

The standard example

p = 61, q = 53 n = 3233 φ(n) = 60 · 52 = 3120 e = 17 gcd(17, 3120) = 1 ✓ d = 17⁻¹ mod 3120 = 2753 (“Bézout's Identity and Modular Inverses” computed this) encrypt m = 65: 65^17 mod 3233 = 2790 decrypt: 2790^2753 mod 3233 = 65 ✓

What the security rests on

An attacker sees n and e. To find d they need φ(n), and computing φ(n) from n is equivalent to factoring n: knowing n = pq and φ(n) = (p−1)(q−1) gives p + q = n − φ(n) + 1, and with pq = n that is a quadratic whose roots are p and q.

So RSA is secure only if factoring large numbers is hard. That is believed and not proved. The best known general algorithm, the number field sieve, is sub-exponential but not polynomial; the largest RSA modulus factored publicly is 829 bits, which took thousands of core-years.

Two further caveats, both important. Nobody has proved that breaking RSA requires factoring — there might be an easier attack on the exponentiation itself. And Shor's algorithm factors in polynomial time on a quantum computer, so RSA is broken outright if a large enough one is ever built.

Why the lab can break its own key

The lab on this page factors the modulus it just generated, by trial division, in microseconds — and recovers the private exponent. Nothing about the method resists that; only the SIZE of the primes does. Real keys use primes of about 1024 bits each, where the same trial division would outlast the universe.

One last honest note: textbook RSA as described here is not secure to deploy. It is deterministic, so identical messages produce identical ciphertexts and an attacker can test guesses; small messages with small e can be recovered by taking an ordinary integer root. Real systems use randomised padding (OAEP) for exactly these reasons. The mathematics here is right and the engineering is not present.

Interactive

RSA, generated and broken

Small enough to check by hand

Method

Using RSA

Each step is a theorem from this course.

Choose two distinct primes and multiply

n = pq. They must be distinct, or φ(n) = p(p−1) rather than (p−1)² and n is a square, trivially factorable.

Compute φ(n) = (p−1)(q−1)

Multiplicativity of φ from “Fermat's Little Theorem and Euler's Theorem”. This value must never be published.

Choose e coprime to φ(n) and invert it

gcd(e, φ(n)) = 1 by “Greatest Common Divisor”, and d = e⁻¹ mod φ(n) by “Bézout's Identity and Modular Inverses”. e need not be prime, only coprime; 65537 is the usual choice because a prime is coprime to φ(n) unless it divides it, one check, and 2¹⁶ + 1 has two set bits, so m^e costs sixteen squarings and one multiplication.

Exponentiate to encrypt and decrypt

By “Modular Exponentiation”'s square and multiply, which is what makes 2048-bit exponents practical.

RSA

Score 0 / 0

Choose the answer you can justify.

A complete small key

Every step, with the theorem that licenses it.

p = 11, q = 13 two distinct primes n = 143 φ(n) = 10 · 12 = 120 multiplicativity of φ e = 7 gcd(7, 120) = 1 valid public exponent d = 7⁻¹ mod 120: 120 = 17·7 + 1 ⟹ 1 = 120 − 17·7 ⟹ d ≡ −17 ≡ 103 check 7 · 103 = 721 = 6·120 + 1 ✓ encrypt m = 9: 9^7 mod 143 9² = 81 9⁴ = 81² = 6561 ≡ 126 (mod 143) 9^7 = 9⁴·9²·9 ≡ 126·81·9 126·81 = 10206 = 71·143 + 53 ≡ 53; 53·9 = 477 ≡ 48 (mod 143) c = 48 decrypt: 48^103 mod 143 = 9 (103 = 1100111₂, “Modular Exponentiation”) ✓

The public key (143, 7) is enough to encrypt and useless for decrypting — unless you factor 143, which takes one division by 11. That is the whole security story, and the only thing that changes at 2048 bits is how long that division takes.

Common mistakes

Publishing or leaking φ(n)With n it gives p + q and hence the factorisation. It is as sensitive as the primes themselves.

Using equal or close primesp = q makes n a perfect square. Primes that are close make Fermat's factorisation method succeed quickly.

Deploying textbook RSAIt is deterministic and malleable. Real systems randomise with OAEP padding, and the mathematics on this page is not the whole system.

Check your understanding

✓

Finish when you can generate a key and say what each step assumes.

Build a key from p = 17, q = 23, encrypt a small message, decrypt it, and then factor n to recover d. With e = 3 you should find n = 391, φ(n) = 352 and d = 235. Doing the attack yourself is what makes the security argument concrete rather than asserted.

Note: This course ends where cryptographic engineering begins. Padding schemes, key management, side-channel resistance and protocol design are all essential and none of them is number theory. What number theory supplies is the core operation and an honest account of what it does and does not guarantee.