Why the Internet Trusts a Hard Problem

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

RSA encryption, the scheme quietly securing an enormous share of the traffic moving across the internet, rests on an asymmetry that has nothing to do with computers and everything to do with a fact Euclid would have recognized: multiplying two large prime numbers together is fast, but taking the resulting product and working backward to find the two primes that made it is, for numbers large enough, so slow that no known method does it in any practical amount of time. A computer can multiply two three-hundred-digit primes in a fraction of a second; recovering those same two primes from the product alone, with every classical computer on earth working together, could take longer than the universe has existed. RSA's public-key system builds a lock directly out of that gap: the product of the two primes is published openly as part of the public key, doing no harm because reversing it is infeasible, while the two primes themselves stay private and let their owner, and only their owner, decrypt what the public key was used to encrypt. It is worth being honest about the asymmetry's limits rather than treating it as permanent: a sufficiently large quantum computer, running an algorithm published by Peter Shor in 1994, could factor these products efficiently, which is why cryptographers are already building the next generation of schemes that do not depend on this particular hard problem holding forever.