Why RSA Works: Euler's Theorem
You'll learn: Why raising a message to the power ed and reducing modulo n recovers the original message, making RSA encryption reversible.
The Mathematical Heart of RSA
You've encrypted messages with m^e and decrypted with c^d. But why does this actually work? The magic lies in Euler's Theorem.
The Core Proof
Recall that in RSA, we choose e and d so that:
ed ≡ 1 (mod φ(n))
This means ed = 1 + k·φ(n) for some integer k.
Now let's trace what happens during encryption followed by decryption:
- Encrypt: Send m^e
- Decrypt: Compute (m^e)^d = m^(ed)
- Rewrite the exponent: m^(ed) = m^(1 + k·φ(n)) = m · m^(k·φ(n)) = m · (m^φ(n))^k
Here's where Euler's Theorem enters: if gcd(m, n) = 1, then:
m^φ(n) ≡ 1 (mod n)
Therefore:
- (m^φ(n))^k ≡ 1^k ≡ 1 (mod n)
- m^(ed) ≡ m · 1 ≡ m (mod n)
You get your message back!
What About gcd(m, n) ≠ 1?
Since n = pq (two primes), the only messages that aren't coprime to n are multiples of p or q—vanishingly rare. Even then, the proof works using the Chinese Remainder Theorem applied to p and q separately.
The Analogy
Think of φ(n) as a "cycle length" for exponentiation. Raising m to the power φ(n) brings you full circle back to 1. The exponents e and d are carefully chosen so their product completes exactly one full cycle (plus 1), landing you back at m.
Key Takeaway: RSA works because ed ≡ 1 (mod φ(n)) guarantees m^(ed) ≡ m (mod n) via Euler's Theorem, ensuring decryption perfectly reverses encryption.