A French expert team has succeeded in factorizing a 795 bit prime number product. This is a new world record. The old one (768 bit) dated from 2009.
The RSA crypto algorithm, invented by and named for Rivest, Shamir and Adleman, is the most popular asymmetric crypto system. Its security is based on the fact that multiplying two prime numbers is easy, while the reverse process (i.e., finding the factors of a prime number product) is difficult.
As a toy example, try to multiply the prime numbers 29 and 31. Using a pocket calculator or a piece of paper, you will easily see that the result is 899. On the other hand, finding the two prime numbers that result in 893 when multiplied, is a lot more difficult (these two primes are 19, 47). The numbers used for RSA in practice are a lot greater, of course. Current implementations typically apply prime number products of 2048 bit or 4096 bit length.
RSA is not only an encryption algorithm but also the name of a company founded by the three inventors of the crypto system (it was called “RSA Data Security”, to be precise). In the late 1990s, RSA Data Security was acquired by the much larger competitor Security Dynamics, which later rebranded to RSA Security (“the most-trusted name in security”).
RSA Security is the organizer of the annual RSA Conference in San Francisco, the largest and most important crypto event in the world. I am proud to be a lecturer at the 2020 edition. On February 26th, I will speak about Understanding and Explaining Post-Quantum Crypto with Cartoons. It’s my second appearance at this conference after 2016.
RSA factoring challenges
Back in 1991, RSA Data Security started the so-called RSA factoring challenges. They published a list of numbers with exactly two prime factors, with a cash prize for the successful factorization of 14 of them. The smallest one, a 330 bit number, was factored by April 1st, 1991, which gained Dutch mathematician Arjen Lenstra $1,000. Other solutions were to follow.
RSA Security stopped the factorizing contest in 2007, after the money for eight challenges had been payed. The longest number factorized at this point had a length of 663 bit. This world record had been set by a team from the University of Bonn, Germany.
Although there was no prize to win any more, the hunt for solving the remaining RSA factoring challenges went on. In 2009, a team led by Thorsten Kleinjung factorized the 768 bit number from the RSA challenge. For a decade, this remained the longest prime number product ever factorized.
In 2012, the German crypto puzzle website MysteryTwister C3 (MTC3) received permission to publish the remaining 38 prime number products as crypto challenges. For instance, here is the 795 bit challenge.
New world record announced
Yesterday, reports about a new factorizing world record hit the media. For instance, the portal ars technica wrote: “Researchers have reached a new milestone in the annals of cryptography with the factoring of the largest RSA key size ever.” This success was achieved by Emmanuel Thomé, a senior researcher at France’s National Institute for Computer Science and Applied Mathematics and his team. Here’s the prime number product they attacked:
And here are the two prime factors:
The articles published about this new record don’t mention how long it took the researchers to solve the problem. Usually, factorizing large numbers is a matter of years. Apparently, Thomé and his team needed less time than their predecessors – not only due to Moore’s law, which states that computation power doubles every 18 months, but also because they used an improved factorizing algorithm.
Along with the factorizing challenge, the researchers also solved a discrete logarithm problem (DLP) of the same size. I don’t know where this problem comes from; it was not a part of the RSA competition or published on MTC3. Perhaps a reader knows more about the origin of this challenge. The discrete logarithm problem is the foundation of the Diffie-Hellman key exchange (I had the pleasure to give a presentation with Diffie at the NSA Symposium on Cryptologic History recently, as the following picture shows).
I congratulate Emmanuel Thomé and his team on this great success. I’m sure that even longer RSA challenge numbers will be factorized in the years to come.
Further reading: The Top 50 unsolved encrypted messages: 45. The World Record Challenge