Was this record-setting encryption crack a fluke—or the new normal?
A researcher’s social media post that revealed how to break part of a popular encryption protocol has gone viral. But did he really do it with just “good old paper and pencil”?
Early on 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 artificial intelligence start-up 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 both specific primes. So factoring an RSA number amounts to decryption, and someone who could find primes from the number could also break encryption schemes. Because these encryption schemes form the bedrock of how we secure finances, messages and other forms of online communication, people get pretty skittish about anything that resembles a threat to them.
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 RSA number that Lu factored is tiny compared with the ones 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 (though there were 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 and then dividing by the 130-digit string he provided. That’s the trick to factoring RSA numbers and solving the other hard problems that underpin cryptography: cracking them tends to be computationally difficult, but it’s child’s play to check if the solutions are 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 and dividing each from RSA-260 until one of them 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. The three co-founded a company named RSA Security, and in 1991 it published a list of “RSA numbers,” each formed by multiplying larger and larger secret primes. The list was pitched as a challenge: if you factored one of the numbers, you’d win a cash prize. And while that contest ended well more than a decade ago, this hasn’t stopped Lu and other crypto enthusiasts from trying to factor the remaining uncracked numbers, including RSA-260.
The last time an RSA number was factored was in 2020. That year a team managed to factor RSA-250, which, in a similar naming convention to the other RSA numbers has 250 base-10 digits. In that case, the researchers used a technique called sieving, which essentially sifts out nonprime numbers, leaving only primes left to test.
That earlier achievement reportedly required several months of work and leveraged the power of tens of thousands of computers. According to another engineer at Cognition, cracking RSA-260 may have taken at least 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 the French National Institute for Research in Digital Science and Technology (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 in this area is even preserved on an online leaderboard. In that case, the number is more than 25 million digits long, though the factor he found was much smaller.
Whether or not Lu used sieving, AI or something else entirely this time, the successful factoring of RSA-260 doesn’t spell doom for current RSA-based encryption schemes because the primes that are used are much bigger. In practice, RSA uses at least about 2,000 binary bits, more than 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 anytime soon.
Source: Read the original article on www.scientificamerican.com
