The Mathematics of Public-Key Encryption
Here's a puzzle that stumped cryptographers for thousands of years. You want to send a secret message to someone you've never met. Every message between you is being read by an eavesdropper. You have no shared password. How do you communicate privately?
It sounds impossible. In 1976 it became possible, and today your browser does it every time you see a padlock icon. The solution uses nothing more exotic than remainders.
You Can Publish Your Encryption Key
In public-key cryptography, each person has two mathematically linked keys:
- A public key, which anyone can see, used to encrypt
- A private key, kept secret, used to decrypt
You can print your public key on a billboard. Anyone can use it to lock a message to you, but only your private key can unlock it. It's like handing out open padlocks: anyone can snap one shut, but only you have the key.
A Secret History
The idea was published in 1976 by Whitfield Diffie and Martin Hellman in "New Directions in Cryptography." The next year, Ron Rivest, Adi Shamir and Leonard Adleman at MIT created RSA, the first practical public-key encryption system. The three later received the 2002 Turing Award for it.
But they weren't first. In 1973, Clifford Cocks, a mathematician at Britain's GCHQ intelligence agency, had devised an essentially identical system, reportedly in about half an hour after hearing of the problem. His work stayed classified until 1997.
Tool 1: Modular Arithmetic
Everything below uses modular arithmetic: calculate normally, then keep only the remainder after division by the modulus.
17 mod 5 = 2 (17 = 3 × 5 + 2)
5⁶ mod 23 = 8 (15,625 = 679 × 23 + 8)
The key fact: modular exponentiation is fast to compute, even with huge numbers, but very hard to reverse.
Diffie–Hellman Key Exchange, With Small Numbers
Alice and Bob publicly agree on a prime p = 23 and a base g = 5. An eavesdropper, Eve, sees these.
- Alice picks a secret a = 6 and sends A = 5⁶ mod 23 = 8
- Bob picks a secret b = 15 and sends B = 5¹⁵ mod 23 = 19
- Alice computes B^a = 19⁶ mod 23 = 2
- Bob computes A^b = 8¹⁵ mod 23 = 2
Both arrive at the shared secret 2, because:
(g^b)^a = g^(ab) = (g^a)^b (mod p)
Eve knows 23, 5, 8 and 19. To find the secret, she has to recover a from 5^a mod 23 = 8. That's the discrete logarithm problem. It's trivial for 23, but with primes of 2,048 bits there's no known efficient method.
RSA, With Small Numbers
Key Generation
- Choose two primes: p = 61 and q = 53
- Multiply: n = 61 × 53 = 3,233
- Compute Euler's totient: φ(n) = (p − 1)(q − 1) = 60 × 52 = 3,120
- Choose e = 17, which shares no factor with 3,120
- Find d so that e × d ≡ 1 (mod 3,120): d = 2,753
Check: 17 × 2,753 = 46,801 = 15 × 3,120 + 1. ✓
Public key: (n = 3,233, e = 17). Private key: d = 2,753.
Encrypt and Decrypt
To encrypt the message m = 65:
c = 65¹⁷ mod 3,233 = 2,790
To decrypt:
m = 2,790²⁷⁵³ mod 3,233 = 65
The original message comes back.
Why RSA Works
The magic is Euler's theorem: if m and n share no common factor, then
m^φ(n) ≡ 1 (mod n)
Since e × d = 1 + k·φ(n) for some integer k:
m^(ed) = m^(1 + k·φ(n)) = m × (m^φ(n))^k ≡ m × 1^k = m (mod n)
Encryption followed by decryption is just raising m to the power ed, which lands right back on m.
Why RSA Is Secure
To find d, an attacker needs φ(n). To find φ(n), they need p and q. To find p and q, they need to factor n.
For n = 3,233, that's easy. Try it with the prime factorization tool. But real RSA keys use a 2048-bit n, which has 617 digits. The largest RSA challenge number publicly factored, RSA-250 (829 bits, 250 digits), took about 2,700 CPU core-years in 2020. Factoring a 2048-bit key with known classical methods is far beyond reach.
Two Concepts Worth Knowing
Greatest Common Divisor
The public exponent e must satisfy gcd(e, φ(n)) = 1. The private exponent d is found with the extended Euclidean algorithm, the same idea behind the GCF calculator.
Trapdoor Functions
A trapdoor function is easy to compute, hard to invert, but easy to invert if you know a secret. RSA's trapdoor is the factorization of n. Public-key cryptography is essentially the search for good trapdoors.
What About Quantum Computers?
In 1994, Peter Shor showed that a large enough quantum computer could factor integers and compute discrete logarithms efficiently. That would break both RSA and Diffie–Hellman. In August 2024, NIST published its first post-quantum cryptography standards, mostly built on problems involving mathematical lattices that are believed to resist quantum attack.
Quick Answer: How Does Public-Key Encryption Work?
Public-key encryption uses a pair of linked keys. Anyone can encrypt with the public key, but only the private key can decrypt. In RSA, the keys come from two large primes, and security depends on the difficulty of factoring their product. Diffie–Hellman relies on the difficulty of discrete logarithms.
Try Them Yourself
- Prime Factorization of 3,233: break our toy RSA key
- Prime Checker: verify candidate primes
- GCF Calculator: confirm e and φ(n) are coprime
- Number Theory Formulas: Euler's theorem and modular arithmetic
- Prime Numbers List: pick your own p and q
- The Mathematics Behind Cryptography: from Caesar to AES
Pick two small primes from the list and build your own RSA key pair. Encrypt a number, decrypt it, and you'll have done by hand what your browser does thousands of times a day.