Why do prime numbers matter for encryption?

Prime numbers matter because of an imbalance in difficulty. Multiplying two large primes is quick, while starting from the product and working out which primes were multiplied is, with known methods, impractically slow. Public key systems such as RSA build on this gap. Everyone can be given the product, but only the person who knows the two primes can easily decrypt messages. One explanation notes that cryptography draws heavily on number theory, and that every integer other than 0 and 1 is built from primes. [1] [2]

Public key cryptography uses two keys, one public and one private. It relies on mathematical puzzles called trapdoor functions, which are easy to compute in one direction and extremely hard to reverse unless you hold a special piece of information, the trapdoor. In the prime-based version, the trapdoor is the pair of prime factors. Princeton course notes give a small illustration: finding the product of 9 and 16 takes almost no time, while recovering the pair from 144 takes longer, and the gap grows enormously with larger numbers. [1] [3]

The NIST mathematical handbook gives a concrete example. A code maker picks two primes of about 400 digits each, which takes little computer time, and publishes their roughly 800-digit product. Encoding needs only that product. Decoding needs the two factors. As of 2010, factoring such a number was estimated to take billions of years on a single computer, so the codes were considered unbreakable given the current state of knowledge about factoring. [4]

RSA was created in 1978 by Ron Rivest, Adi Shamir and Leonard Adleman and is used, for example, to protect credit card numbers sent online. In the usual telling, Alice picks two large primes, keeps them secret and openly shares their product. Bob uses the product to encrypt a message that only Alice's factors can decrypt. An eavesdropper, Eve, would have to factor the product, and no known algorithm can do that in a practical time, even on a supercomputer. [5]

One common misstatement is corrected in the Princeton notes. RSA's security is not about the difficulty of factoring a prime number, since a prime has only two factors. It rests on the difficulty of factoring the product of two primes. [3]

The security rests on a limit of conventional computers, not on a proof that factoring is impossible. NIST says a sufficiently powerful quantum computer, which experts call a cryptographically relevant quantum computer, would not face the same difficulty. NIST suggests that such a machine could solve the factoring problem in days or even hours rather than billions of years, putting encrypted data at risk. This is why NIST works on post-quantum cryptography, which aims to replace these methods. [6]