← Hall of Foundations Exhibit 145 · aᵠ⁽ⁿ⁾ ≡ 1
The Engine of RSA Decryption

Why RSA
undoes itself

RSA encrypts by raising a message to a power, and decrypts by raising the result to another. That these two operations cancel — that you land back on the exact message you started with — is not luck. It's a 400-year-old theorem of Fermat, generalized by Euler.

Small but essential. This is the shortest exhibit in the hall, because the idea is compact: one congruence explains why RSA works at all. Watch a real message make the round trip below.
§1

Fermat's little theorem

For any prime p and any a not divisible by p, raising a to the (p−1) power lands exactly on 1, modulo p. Every base, no exceptions.

aᵖ⁻¹ ≡ 1 (mod p)

Euler generalized it from primes to any modulus n, replacing p−1 with φ(n) — the count of numbers below n that share no factor with it. This is the version RSA runs on.

aφ(n) ≡ 1 (mod n)  when gcd(a, n) = 1
§2

The round trip

RSA picks exponents e and d that are inverses modulo φ(n), so that e·d ≡ 1. Then encrypting (raise to e) and decrypting (raise to d) compose to raising by e·d — which, by Euler's theorem, does nothing at all. The message returns untouched. Type a small number and send it through.

One honest caveat: Euler's theorem as stated needs gcd(m, n) = 1, and with this toy key a few messages — the multiples of 61 or 53 — fail that test. RSA still round-trips them, but the reason is slightly different: you check the congruence separately modulo p and modulo q, where it holds either trivially or by Fermat, then glue the two halves back together with the Chinese Remainder Theorem. Real implementations also use Carmichael's λ(n) rather than φ(n) to pick d; it divides φ(n) and yields the same round trip with a potentially smaller exponent.

—
Toy key: p = 61, q = 53, n = 3233, e = 17, d = 2753. Real RSA uses the same arithmetic with a 2048-bit n. The ciphertext is genuine modular exponentiation, computed live.
Encryption and decryption aren't opposites by design — they're opposites by theorem.
Where this touches your keys

The reason the mailbox opens

Factoring the modulus breaks RSA; the converse equivalence between general RSA inversion and factoring is not known. Correctness is a separate question, supplied here by modular arithmetic and the Chinese remainder theorem. This raw textbook-RSA round trip lacks secure encodings and must not be used for real encryption.

Sources and scope: RFC 8017 (2016), RSA key relations and complete encryption/signature schemes.

Continue with RSA or explore modular arithmetic.