How does RSA turn two prime numbers into a lock anyone can close but only you can open?

RSA works because some arithmetic is easy forwards and brutally hard backwards. Your private key is a pair of large prime numbers chosen at random and kept secret. Your public key is built from their product. Multiplying two primes takes a computer no time at all, but recovering them from the product is the "factoring problem", and the security of RSA is tied to how hard it is.

The lock itself is clock arithmetic. On a 12-hour clock, 8 hours after 7 o'clock is 3, not 15: numbers wrap around. RSA does the same with a giant clock of size n, the product of the primes. To lock a message, you turn it into a number and raise it to a public power e, keeping only the remainder on the clock. To unlock it, you raise the result to a secret power d, and the original number comes back. Anyone can do the first step. Without d, undoing it is infeasible.

And d is easy to compute only if you know the two primes. In a classroom example, the primes 61 and 53 give n = 3233, the public power is 17 and the secret one is 413. The message 65 locks into 2790, and 2790 unlocks back into 65. With primes this small, anyone could factor 3233 and steal the key. Real keys use numbers hundreds of digits long: factoring a 250-digit RSA number in 2020 took about 2,700 CPU-years.

The idea was made public in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman, after a sleepless night in which Rivest wrote much of the paper by daybreak. The guarantee rests on a gamble: no fast way to factor large numbers is known, but no one has proven that none exists.