Early Thursday morning, technical researcher Eric Lu sparked worldwide excitement and confusion by posting a sequence of 130 digits on X (formerly Twitter). The reason for the uproar over some seemingly innocuous numbers lies in the two words that followed them: “divides RSA-260.”
Lu, an engineer at the AI startup Cognition, has managed to factor one of the so-called RSA numbers—unwieldy numerical strings created by multiplying two huge, secret prime numbers. The bigger those two factor primes are, conventional thinking goes, the harder their multiplication is to undo—a sentiment that has made RSA one of the world’s most popular encryption schemes since its debut nearly a half-century ago.
To encrypt messages with RSA, someone just needs to know one of these numbers which, like RSA-260, have only two prime factors; decryption requires knowing those specific primes. So factoring amounts to decryption, and someone who could find primes from the number could also break encryption schemes. Since these encryption schemes form the bedrock of how we secure finances, messages, and other forms of online communication, people get pretty skittish about anything resembling a threat to them.
On supporting science journalism
If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
While the one Lu factored is tiny in comparison to the RSA numbers used for modern cryptography, it’s still the largest that’s ever been cracked. And bucking the recent trend of AI-powered math results, Lu’s feat seemingly did not make use of any AI (albeit with some conflicting reports from Devin, the AI that Cognition is developing).
Confirming Lu’s achievement is as simple as inputting the known RSA-260 number in a calculator, then dividing by the 130-digit string he provided. That’s the trick to factoring and the other hard problems underpinning cryptography: Cracking them tends to be computationally difficult, but it’s child’s play to check if they’re right.
For now, Lu has offered very few details about how he found the special prime, other than a dubious claim, perhaps made in jest, that nothing more than “good old paper and pencil” was involved. Presumably, his unclear methodology boiled down to randomly sampling primes, dividing them one-by-one from RSA-260 until one divided evenly. (Neither Lu nor Cognitive has responded to Scientific American’s request for comment.)
Named after its creators—computer scientists Ron Rivest, Adi Shamir, and Leonard Adelman—the concept for the RSA cryptosystem emerged in 1977. In 1991, the company they founded (also named RSA) published a list of “RSA numbers,” each formed by multiplying larger and larger secret primes. The list was pitched as a challenge: Factor one of the numbers and win a cash prize. And while that contest ended well over a decade ago, this hasn’t stopped Lu and other crypto enthusiasts from trying to factor those that remained uncracked, including RSA-260.
2020 was the last time an RSA number was factored. That year, a team of researchers managed to factor RSA-250, which in a similar naming convention to the other RSA numbers has 250 base-10 digits. In that case, they used a technique called sieving, which essentially sifts out non-prime numbers leaving only primes left to test.
That earlier achievement reportedly required several months of work, leveraging the power of thousands of computers. According to another engineer at Cognition, cracking RSA-260 may have taken seven months, in which Lu sampled and tested primes “by hand.” (That is, with the assistance of computers but not the automated cognition of AI.)
The notion of actually cracking a number the size of RSA-260 without computer assistance is inconceivable; Emmanuele Thomé, a researcher at Inria who was part of the group that factored RSA-250, says that “factoring RSA-260 is expected to be roughly three times as [computationally] expensive as RSA-250.” Lu’s feat, Thomé says, was “certainly feasible,” albeit “not exactly low-hanging fruit.”
Lu is no stranger to using computers for some long divisions, though. In 2019, he found a factor to a Mersenne number, proving it wasn’t prime. Mathematicians have for centuries been interested in which Mersenne numbers are prime or not, and Lu’s achievement here is even preserved on a leaderboard online. In that case, the number was over 25 million digits long, though the factor he found was much smaller than here.
Whether or not Lu used sieving or AI or something else entirely this time, the successful factoring of RSA-260 doesn’t spell doom for current RSA-based encryption schemes, as the primes used are much bigger. RSA in practice uses at least about two thousand binary bits, over twice the length of RSA-260. And with the hardness increasing exponentially as the numbers grow, no regular computers are likely to break RSA encryption any time soon.
Instead, advances in quantum computing are far more likely to pose a problem than throwing months of computation at testing each and every prime number. While current quantum computers aren’t nearly big enough to process encryptions, researchers already know how factoring can be sped up using quantum computing, far faster than what we can do without it. For now, anyone with encryption-protected secrets can breathe easier; barring some breakthrough in non-quantum ways to factor RSA numbers, projects like Lu’s remain more of a curiosity than a realistic threat.