Number Theory in Cryptography – How RSA Keeps Secrets
Every time a browser connects to a secure website, it very likely uses ideas from this entire section of MathsFamily working together: prime numbers, modular arithmetic, and Euler's totient function combine to form RSA encryption, one of the most widely used public-key cryptography systems in the world.
RSA is named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman, who published it in 1977 while at MIT. Remarkably, an equivalent method had already been secretly invented four years earlier, in 1973, by Clifford Cocks, a mathematician working for Britain's GCHQ – his work remained classified until 1997, by which time RSA's public inventors had already received the credit, and in 2002, the Turing Award. Today RSA and its descendants secure a huge share of the internet's HTTPS traffic, though the rise of quantum computing – specifically Shor's algorithm, which could factor large numbers efficiently on a large enough quantum computer – is driving active research into “post-quantum” replacements.
How RSA Works
- Choose two large prime numbers, p and q.
- Compute n = pq (this becomes the public modulus).
- Compute φ(n) = (p−1)(q−1), using Euler's totient function.
- Choose e, coprime to φ(n), to form the public key (n, e).
- Compute d, the modular inverse of e mod φ(n), to form the private key (n, d).
- Encrypt a message m as c = me mod n.
- Decrypt c back to m as m = cd mod n.
Let p = 3, q = 11. Then n = 33 and φ(n) = (3−1)(11−1) = 20.
Choose e = 3 (coprime to 20). Then d = 7, since 3 × 7 = 21 ≡ 1 (mod 20).
Public key: (n, e) = (33, 3). Private key: (n, d) = (33, 7).
Encrypt m = 5: c = 53 mod 33 = 125 mod 33 = 26.
Decrypt c = 26: m = 267 mod 33 = 5. ✓ The original message is recovered exactly.
Why It's Secure
RSA's security rests on a simple asymmetry: multiplying two large primes p and q together to get n is fast, but factoring a large n back into p and q, without already knowing them, is extremely slow using any algorithm known to run on ordinary computers. This kind of easy-forwards, hard-backwards relationship is called a one-way function, and it is the foundation almost all modern public-key cryptography is built on.
Beyond RSA
- Diffie–Hellman key exchange (1976): lets two parties agree on a shared secret over an open channel, using modular exponentiation.
- Elliptic-curve cryptography: achieves RSA-level security with much smaller keys, using a different area of number theory.
- Hash functions: algorithms like SHA-256 use modular arithmetic to fingerprint data.
- Post-quantum cryptography: new schemes being developed to resist attacks from future quantum computers.
Key Takeaways
- RSA combines primes, modular arithmetic, and Euler's totient function into a working encryption system.
- The public key is (n, e); the private key is (n, d), where d is the modular inverse of e mod φ(n).
- Encryption: c = me mod n. Decryption: m = cd mod n.
- Security relies on how hard it is to factor a large n back into its two prime factors.