Our online world requires us to share private information with others. This is possible thanks to public key encryption, which works because a certain mathematics problem in number theory is currently hard to solve: that of factoring large numbers.
I am not a number theorist. But, from the perspective of a mathematical philosopher, the entire system seems remarkably precarious, as Large Language Models turn their attention to this problem. In this post I’d like to explain this vulnerability in relatively easy-going terms.
A World Built on Encrypted Foundations
Nearly every purchase, payment, health record, and government data-point is communicated online through a public key encryption protocol. Cryptocurrency would be worthless without it. Codes for every missile and missile-defence system use it. If a thief, terrorist, or adversarial state found a way to crack our public key encryption methods, it would likely be followed by abject chaos.
In other words, public key encryption is like a brick on which the whole world is precariously balanced.
Unfortunately, breaking most public key cryptography protocols is something that I think LLMs are well-suited to pursue. I’m not the only one: progress has been made by LLMs on this problem already. Some may already be broken. If so, then the collapse of an enormous amount of private information would already be under way.
In this post I will illustrate the concern using the first public key cryptography protocol, which is called RSA. Others have been developed since then: for example, Bitcoin is encrypted using elliptic curve cryptography. However, similar concerns extend to many other public key encryption protocols too—though perhaps not all. I will discuss this more at the end.
How Public-Key Encryption Works
The German Enigma cipher was broken by Polish and British codebreakers in the 1930s and 40s. This made it particularly difficult to send an encrypted message that is both secure and practical for everyone to use: it was generally impractical to make a decryption key available in a secure way. The tumultuous history of this development is chronicled in Simon Singh’s The Code Book.
Then, in 1977, the RSA encryption algorithm was invented. This suddenly made the world safe for codes again. RSA provides you with a public key that you can send out into the world. Think of this like an open combination lock, which anyone can snap shut to secure a message. Only your private key can open it.
Public key cryptography provides a lock for anyone to secure a message and a key just for you.
Like a combination lock code, your private key is a number. Someone could in principle guess it. There is even an algorithm for cycling through all the possible keys. Fortunately, nobody seems to know any way to guess the private key in a reasonable amount of time—at least not yet.
The reason is that the fast-guessing algorithm depends on a currently-unsolved problem in mathematics, that of how to quickly factor large numbers. It only takes a bit of elementary mathematics to understand this. So, let’s look in a little more detail at how RSA works. Then you’ll be able to see exactly what its weakness is.
Encryption is Possible Because Factoring is Hard
To use RSA, you first choose two prime numbers p and q that are kept secret. You then calculate n = p×q, as well as Euler’s totient function φ(n) = (p-1)(q-1). These numbers determine your public key and your private key. You can share the public key without worrying about somebody figuring out these secret primes because, currently, it is astronomically hard to work backwards. That is, no one knows how to input n and output p and q in a reasonable amount of time. Your private key is ‘private’ only because this is currently such a difficult task.
For example, suppose you are given the number n = 77. What two primes p and q satisfy n = p×q? You know they must be less than 77/2 =38.5, and you know they must be odd. But, that still leaves some possibilities to check. You might go through dividing nineteen different odd numbers before determining the answer is 11 and 7.
Just two prime divisors amongst all the possibilities .
Of course, 77 is pretty easy. But, 95,477 is also the product of two primes. Finding those primes requires checking tens of thousands of numbers. In most serious encryption it would require trillions upon trillions. So, finding the correct two primes is generally like finding two needles in an astronomically large haystack.
Here is an interactive JavaScript that shows in detail how this fact can be ingeniously exploited to encrypt messages. The example starts by choosing p = 61 and q = 53, but you can choose whatever primes you want.
A currently hard problem can become easy
Factoring a number into its prime factors is currently hard. This is because the only known ways to do it are non-polynomial time: this is a precise mathematical way of saying the algorithm takes a very long time to run. For internet transactions, the fastest possible classical computers would take longer than the current age of the universe to complete the task.
However, it might not always be hard. For example, a ‘true’ quantum computer that can execute Shor’s algorithm can factor integers in polynomial time. They would also break elliptic curve cryptography. Quantum computers of this kind would destroy a large amount of modern public key cryptography.
Even more alarmingly, classical computers might break RSA if someone just finds the right algorithm. Nobody thinks this is impossible. For example, integer factorisation is not known to be NP complete, which is a way of saying it’s probably not that hard. There are no known theoretical barriers to factoring integers in polynomial time.
And, scores of better algorithms are being produced with increasing speed by LLMs.
Compare the related problem of determining whether a given number is prime. This was equally hard for more than 2,000 years. An algorithmic way to do it was discovered in Ancient Greece called the Sieve of Eratosthenes, which systematically eliminates multiples of ever-larger primes. But, for very large numbers, it was hard to carry this out in practice: it too is a non-polynomial time algorithm.
Strozzi (1635) Eratosthenes teaching in Alexandria. He discovered a primality test, but which is too slow to be useful on large numbers.
.jpg){kind=link}
Then, in August 2002, computer scientists Agrawal, Kayal and Saxena shocked the mathematical world with the discovery of a fast and easy way to do the same task: the AKS primality test. A polynomial time algorithm was just waiting to be discovered. Although primality testing was already being widely studied, AKS showed that it could be done unconditionally and deterministically in polynomial time. The authors quickly received the Gödel Prize and the Fulkerson Prize for their work. You can watch Numberphile explain it here.
This was an entirely human discovery. Few resources spent on the problem. One can only guess where we are headed with millions of LLM agents unleashed to try to solve it.
A fast way to factor large numbers?
In a 2016 paper, two of the AKS authors Agrawal and Saxena, together with Srivastava, adapted the AKS approach from primality testing to factoring integers. They didn’t manage to get an unconditional way to factor integers in polynomial time. But, they are able to do it under special conditions.
In the 2016 paper, a special algebraic relation had to hold between the prime factors for the factoring algorithm to work. But, it is still a remarkable step forward, opening up a research programme that tries to relax those conditions. For example, one could try to find polynomially many efficiently computable small matrices whose ranks differ modulo the unknown primes. That difference would yield a factor. So, proving that one always occurs would establish a polynomial-time algorithm for factoring integers.
I find it shocking, by the way, that this paper has hardly been cited in the last 10 years, compared to the authors 2,500+ citations on their primality paper.
This is just one of many promising new approaches to breaking RSA. So, how close are we to the end of public key encryption? The silence on this question is deafening. I wonder what others think. But, I would like to at least point out the following:
- Integer factorisation is ranked 16 on a list of 500 open mathematics problems ranked by LLM-assisted importance, and so it is being widely attacked.
- As Scott Aaronson reported last month, in computer science “there’s now a deluge, with longstanding open problems both major and minor falling by the day”.
- Some non-polynomial time algorithms for factoring are fast enough to be accessible: notably TWIRL and Bernstein’s circuit. Some experts speculate that governments have been using them to break 1024-bit RSA ciphers since the mid-2000s. It is not impossible that an even more accessible algorithm has already been discovered.
- Most critically, the tools to attack this problem are not restricted to governments anymore, but widely available to anyone with enough money to spend on computational tokens.
That said, there are other public key cryptography methods besides RSA. So, breaking RSA does not mean all hope is lost. However, you can bet that these protocols are in the cross-hairs as well.
Even more promisingly, in 2024 the US National Institute of Standards and Technology (NIST) issued post-quantum encryption standards. This included a number of new public key encryption tools that can withstand the attack of quantum computers. These and similar alternative public key protocols will slowly be adopted. One simply hopes that this happens before a bad actor breaks current protocols.
Simon Singh’s book describes a breathtaking historical battle between the white-hat cryptographers and the black-hat decipherers. The power has gone back and forth between them many times. Since 1977, the white-hats have been winning. Nearly 50 years later, the black-hats are gaining ground at a rapid pace.
AI Acknowledgement: the interactive RSA Javascript (available here) was created in collaboration with OpenAI Astra. All the remaining materials, including the non-Strozzi illustrations, are entirely by Bryan.