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.

 

RSA

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:

124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099

And here are the two prime factors:

509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517

244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447

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

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (3)

  1. #1 George Lasry
    6. Dezember 2019

    There is some more info (https://en.wikipedia.org/wiki/RSA_numbers, section on RSA 240), including runtime (at the end of the comment here):

    RSA-240 has 240 decimal digits (795 bits), and was factored in November 2019 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann.[37]

    RSA-240 = 12462036678171878406583504460810659043482037465167880575481878888328966680118821
    08550360395702725087475098647684384586210548655379702539305718912176843182863628
    46948405301614416430468066875699415246993185704183030512549594371372159029236099
    RSA-240 = 50943595228583991455505102358084371413264838202411147318666029652182120646974670
    0620316443478873837606252372049619334517
    × 24462420883831815056781313902400289665380209257893140145204122133655847709517815
    5258218897735030590669041302045908071447
    The CPU time spent on finding these factors amounted to approximately 900 core-years on a 2.1 Ghz Intel Xeon Gold 6130 CPU.

  2. #2 Klaus Schmeh
    8. Dezember 2019

    Dave Howe via Linked-in:
    Surprised Time AI aren’t claiming to have done it first 😀

  3. #3 Joshua Holden
    https://wordpress.rose-hulman.edu/holden/
    8. Dezember 2019

    I believe that the research team made up the discrete logarithm challenge themselves. The prime they used was the first “safe prime” larger than RSA-240. The target they decided to take the discrete logarithm of was an encoding of the sentence “The magic words are still Squeamish Ossifrage” (in reference to the factorization of RSA-129). So it probably wasn’t something they knew the logarithm of to start with. 🙂 The team’s announcement is at https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html