A team of computer scientists has improved the record for factorizing prime number products from 795 to 829 bit.
It’s a great success, but it comes at the wrong time: While the world is struggling with the coronavirus, an international expert team has completed the factorization of the longest prime number product ever. The new record stands at 829 bits.
The RSA algorithm
Prime number products and their factorization play an important role for RSA, a crypto algorithm invented by and named for the cryptologists Ron Rivest, Adi Shamir and Leonard Adleman. The following picture of Rivest (right) was taken in 2016:
Source: Schmeh
RSA 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, a process also known as prime factorization) is assumed to be 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 the number 893 when multiplied, is considerably more difficult (these two primes are 19 and 47). The numbers used in practice are a lot greater, of course. Current RSA implementations typically empoly prime number products of 2048 or 4096 bit length.
It’s important to note that it is not proven that prime factorization is difficult. All we know is that even after decades of intensive research, nobody has found a method that finds the factors of a prime number product in an efficient way. Even the best prime factorizing algorithm currently known, the so-called number field sieve, is too weak to factorize a 2048 bit prime number product within, say, a thousand years, even if the best computers in the world are used.
However, there is no guarantee that the number field sieve is the best factorizing method – it is theoretically possible that tomorrow somebody will come up with a better one that is much faster. If somebody invented an algorithm that factorizes a 2048 bit prime number product within seconds, it would lead to a disaster, as millions of crypto implementations in web browsers, email programs, VPN tools, file encryption programs, ATM machines and other IT systems would become useless.
In his 1995 Book The Road Ahead, Bill Gates wrote: “The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers.” Do you know why this statement is wrong and why it is often referred to as one of Gates’ most stupid quotes?
Contrary to today’s information technology, quantum computers can factorize prime number products efficiently. However, this is still science fiction. It is not even clear if powerful quantum computers will ever exist. Nevertheless, cryptologists in all the world are occupying themselves with asymmetric encryption systems that are based on problems that, unlike prime factorization, can’t be solved with a quantum computer. The theory of crypto algorithms of this kind is referred to as post quantum cryptography.
RSA is not only an asymmetric encryption algorithm but also the name of a company (“RSA Data Security”) founded by the three inventors of the crypto system. 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”).
The owner of RSA Security has changed several times. In February this year, it became known that Dell, the then parent company of RSA Security, sold their subsidiary to the Symphony Technology Group for $2.1 billion.
RSA Security is the organizer of the annual RSA Conference in San Francisco, the largest and most important crypto event in the world. I was proud to be a lecturer at the 2020 edition, with a talk about post quantum cryptography.
RSA factoring challenges
In 1991, RSA Data Security started the so-called RSA factoring challenges. This competition was based on a list of numbers, each with two prime factors, and prize money for successfully factorizing these. The smallest number, 330 bit in length, was factorized by April 1st, 1991, which gained Dutch mathematician Arjen Lenstra a cash prize of $1,000. Other successful factorizations were to follow.
RSA Security stopped the factorizing contest in 2007, after the prize money for eight challenges had been paid. 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 money 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’s the 829 bit challenge on MTC3 (named RSA-250 because the number to be factorized has 250 decimal digits).
The 795 bit factorization completed in 2019
Last year in December, reports about a new factorizing world record hit the media. This success was achieved by Emmanuel Thomé, a senior researcher at France’s National Institute for Computer Science and Applied Mathematics and his international team. Here’s the prime number product they successfully attacked:
124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099
And here are the two prime factors:
509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517
244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
A new world record: 829 bit
It took only four months until a new factorizing world record was reached. This success was announced earlier this week. The longest prime number product ever factorized now has a length of 829 bit; it’s the aforementioned one that is available on MTC3.
To my regret, there were only few media reports about this new record; apparently there are more important things to write and talk about these days. The only English article about this mathematical stunt that can be found on Google News was published on the science-news portal Phys.org. There are also a Spanish and a French article, but that’s it.
According to Phys.org, the new record was reached by the same team of computer scientists from France and the United States that had already set the previous one in December 2019. In total, it took 2700 years of running powerful computers to carry out the computation, which was done on tens of thousands of machines around the world over the course of a few months.
Considering that current RSA implementations use 2048 bit prime number products, it is clear that we don’t need to worry about the security of our crypto implementations, just because the factorizing world record has been improved twice within less than half a year. The difference between 829 and 2048 bit is still big enough to assume that a 2048 prime number product won’t be factorized so soon.
So, while the coronavirus is threatening, factorizing attacks on the RSA crypto system currently aren’t. At least one good news these days.
Another crypto world record to break
While the record for factorizing the longest prime number product has been broken several times over the last 15 years, the record for the longest symmetric key solved with brute force has stayed the same. It stands at 64 bit since 2002. If you want to do better, read my blog post about the World Record Challenge.
Follow @KlausSchmeh
Further reading: Ron Rivest publishes new time-lock puzzle
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (5)