Course contentsShow
← Mathematics
Lesson 2768 of 3,12154. Number TheoryFree lesson

Why RSA Works: Euler's Theorem

Understand the mathematical proof that m^(ed) ≡ m (mod n) using Euler's theorem and properties of φ(n).

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:

  1. Encrypt: Send m^e
  2. Decrypt: Compute (m^e)^d = m^(ed)
  3. 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.