How RSA Works
The trapdoor function and computational security
The Trapdoor Function
, created in 1977 by Rivest, Shamir, and Adleman, relies on a trapdoor function — a math problem that is easy to compute in one direction but virtually impossible to reverse without a secret.
The trapdoor in is prime number factorization: multiplying two massive prime numbers (P and Q) together is trivial, but factoring the result (N) back into P and Q is computationally infeasible. The public key (N, e) is published openly; the private key (d) is derived from knowing P and Q.
Computational vs. Information-Theoretic Security
Almost the entire modern internet is only computationally secure. This means the lock can be picked; it just takes a ridiculously long time. relies on the extreme difficulty of factoring massive prime numbers. relies on reverse-engineering a point on an elliptic curve.
Brute-forcing a 2048-bit key would require a supercomputer guessing millions of times per second for a period longer than the age of the universe. We deemed them 'unbreakable' — but that assumption rested on the rules of computing never changing.
This assumption — that computing rules never change — is exactly what quantum computers threaten. The entire crisis of post-quantum cryptography flows from this single point.
Key Takeaways
- RSA's security rests on the difficulty of factoring the product of two large primes
- The public key is published openly; the private key is derived from knowing the prime factors
- RSA keys must grow larger as computers get faster — from 512 bits (1990s) to 2048-4096 bits today