Too tired to read? Listen on Spotify:
Prime numbers are used in cryptography because they are difficult to factorize. This means that it is difficult to find the prime factors of a composite number without knowing the factors to begin with. This makes it difficult for someone to intercept a message and read it without the proper key.
A typical 2048-bit RSA key has roughly 10617 possible values. Even using the best known factoring algorithm (the general number-field sieve) on the fastest supercomputers, the run-time is estimated at around 1020 years — far longer than the age of the universe (about 1.4 × 1010 years, or roughly 1017 seconds). Cracking that kind of code, in other words, is a job no thief is going to finish in this lifetime.
When Fermat, primarily known for Fermat’s Last Theorem, discovered a subtle method to determine whether a number is prime or composite, his peers couldn’t comprehend the proof’s utility. The proof, for most of its existence, was perceived as a statue is – beautiful, but utterly useless. In fact, discoveries regarding prime numbers were venerated for merely the essence of discovery — for disclosing and making sense of the hidden complexities in mathematics, for solving a curious puzzle — except that they didn’t contribute any substantial solutions to the problems of the real world.
This was until 400 years later when the Internet was born, and the privacy of its billion users, from the content of confidential emails to transactions on e-commerce websites, relied solely on prime numbers.
Recommended Video for you:
Trapdoor
Prime numbers are commonly referred to as the “atoms” of the numerical realm, for they are the fundamental, indivisible units that make up every number. For instance, 10 can be written as a product of 2 and 5, two prime numbers. Or, 150 as a product of 15 and 10, which can be further broken down and written as the product of 3, 5, 2 and 5 – all prime numbers. Or, a larger number such as 126, 356, which is composed of larger prime numbers 2,2,31 and 1019.
This process of reducing a composite number to a product of prime numbers is known as prime factorization. For a computer, multiplying two prime numbers, each even 100 digits long, isn’t that difficult, however, factorizing the product back into its components is notoriously difficult, even for supercomputers. It is this shortcoming that Rivest, Shamir and Adleman exploited to create RSA encryption in 1977. In cryptography jargon, this unidirectionality is known as a “trapdoor”.
The Keys
Let’s say that C is a product of two prime numbers P and Q. While encrypting, say, your credit card details, the number C is used to generate the “public” key. This key, as its name suggests, is available to the public, meaning that it can be intercepted and read by anyone in the network. Banks are known to use public keys that are 617 digits long to secure your private transactions.
A public key secures private information by locking it in a box whose handles are tightly clasped with a several hundred-digit combination-lock. The box itself can be accessed by anyone, but the content inside it can’t. While a thief may furtively steal the box, he can’t unlock it without knowing the combination, without possessing the “private” key. This private key is only possessed by the sender and receiver of the content — the bank and you, the proprietor of the credit card.
The private key constitutes the two prime numbers P and Q, which were multiplied to produce C, the public key. Without their knowledge, the thief, to peek in, must factorize C, which could take him billions of years if the numbers are hundreds of digits long. And trust me, there are a lot of huge prime numbers. The largest known prime, as of October 2024, is 2136,279,841 − 1 — a Mersenne prime with 41,024,320 digits, discovered through the Great Internet Mersenne Prime Search (GIMPS) using a network of cloud GPUs. If you were to write this number out on A4 paper, the sequence would fill a stack of roughly 13,800 sheets.
Lastly, factorization is not impossible; it can be done. It is just exorbitantly time-consuming. As technology progresses, we are able to crunch numbers more quickly. The current factoring record is RSA-250 (an 829-bit number), which a team led by Fabrice Boudot and Paul Zimmermann factored in February 2020 after roughly 2,700 core-years of computing time. Most websites and banks today still use 2048-bit RSA keys (about 617 digits long), which are well out of reach of any classical attack. Quantum computers, in principle, could break RSA much faster using Shor’s algorithm, but the machines available today have nowhere near the qubits or error rates needed to threaten 2048-bit keys. Anticipating that, NIST finalized its first post-quantum cryptography standards (ML-KEM, ML-DSA and SLH-DSA, published as FIPS 203, 204 and 205) in August 2024, and the migration is now underway. So, don’t worry, your drunk texts are still in safe hands — but the cryptographic ground is shifting under them.
