Do the Math: Prime Number Breakthrough Could Upend Encryption
Mathematicians for centuries have banked on the randomness of prime numbers. You know who else has, too? Cryptographers.
So, when researcher Way Kuo, a senior fellow at the Hong Kong Institute for Advanced Study, claimed in a working paper appearing in the SSRN Electronic Journal that his team had “devised a way to accurately and swiftly predict when prime numbers will appear,” it set off a bit of a tizzy.
Because if the researchers are correct and their success can be repeated, then encryption wouldn’t be the safeguard it was once believed to be. Writing in earth.com, Eric Ralls notes that the researchers have presented a Periodic Table of Primes, much like the periodic table for chemicals, “which plots each prime inside repeating blocks,” a grid that “not only pinpoints where the next prime hides but also estimates the largest gap between primes in any stretch of numbers.”
Acknowledging that “number theory and the assumed randomness of the distribution of prime numbers has been a challenge for mathematicians for a very long time,” Jason Soroko, senior fellow at Sectigo, that acceptance of the “formulae that compute the next prime and set bounds on gaps with polynomial time complexity” would put an end to “the randomness assumption that supports analytic number theory and the security estimates behind factor-based cryptosystems” that “are critical to how most of our computer systems keep things secure and private.”
For example, as a cryptographic algorithm, RSA “rests on the search cost for prime factors of moduli,” Soroko notes. “If that cost drops from exploratory search to table lookup, key length loses meaning and migration to lattice, code or hash-based schemes becomes urgent.”
Public key cryptography is a powerful tool underpinning the security of the internet. And indeed, algorithms like RSA, DSA, Diffie-Hellman, or ECC, may provide certainty that the right door is being knocked on. But, says Sergio A. Figueroa, senior security consultant at Black Duck, “there is a quirk about these algorithms: They all rely, in one way or another, on an assumption — that factoring certain numbers is hard.”
A breakthrough on number theory emerges, such as in factorization. “It could bring all these building blocks down to shambles,” he says. “Such a breakthrough is looming: Quantum computers, a radically new approach to computing based on quantum physics, are expected to break all these algorithms.”
Researchers have gone from questioning the viability of quantum computers, since they are hard to build, Figueroa explains, to how long it will take for them to be mature enough to become a threat to cryptography,” by some estimates that timeframe is less than a decade.
Figueroa is clearly spot on when he says, “Relying on a single assumption was a mistake.” But, as he points out, the industry knows that. For nearly a decade, NIST has worked toward a standardization process for post-quantum cryptography, “algorithms that can withstand the attack of both classical and quantum computers,” he points out. Key to that has been “assumption diversity” or “algorithms that rely on different assumptions, like obscure mathematical constructs called lattices,” error correction codes, hash functions and the like. “That way, if one assumption is proven wrong, a replacement is readily available,” Figueroa says. “So far, NIST has standardized five new post-quantum algorithms (LMS, XMSS, ML-KEM, ML-DSA and SLH-DSA), and more will come.”
When asked about the prime number findings by Way Kuo’s team, Figueroa gives the verbal equivalent of a shrug. “Every now and then, a new claim about prime numbers emerges and brings with it a renewed sense of alarm,” he says. “In fact, that alarm is misplaced.”
He sees prime numbers as “an exciting field that will surely keep mathematicians busy for years to come,” but notes that “relying solely on them as the basis of online security is a major mistake.”
Instead, developing “cryptoagile” systems “that can quickly be updated to new algorithms or settings,” will give the security industry “fewer reasons to fear any new discovery in the field.”
