New record for crypto-cracking achieved, with less help than usual from Moore’s law

Researchers have reached a new milestone in cryptography annals with factoring the largest RSA key size ever calculated and a matching calculation of the largest-integer discrete logarithm ever. New records of this type take place regularly as the performance of computer hardware increases over time. The records announced Monday evening are more important because they were achieved considerably faster than hardware improvements would predict, thanks to improvements in the software used and the algorithms implemented.

Many public key encryption algorithms rely on extremely large numbers that are the product of two prime numbers. Other encryption algorithms base their protection on the difficulty of solving certain discrete logarithm problems. With sufficiently large key sizes, there is no known way to crack the coding that they offer. The factoring of the large numbers and the calculation of a discrete logarithm defeat the cryptographic guarantees for a given key size and force users to increase the number of bits of entropy that it uses.

The new records include the factoring of RSA-240, an RSA key with 240 decimal digits and a size of 795 bits. The same team of researchers also calculated a discrete logarithm of the same size. The previous records were the factoring in 2010 of an RSA-768 (which, despite its number, is a smaller RSA key than the RSA-240, with 232 decimal digits and 768 bits) and the calculation of a 768-bit prime discrete logarithm in 2016.

The sum of the calculation time for both new records is approximately 4,000 core years with Intel Xeon Gold 6130 CPUs (at 2.1 GHz) as a reference. Like previous records, these were created using a complex algorithm called Number Field Sieve, which can be used to perform both integer factoring and finite field discrete logarithms. A rough breakdown of the time spent on sieving and matrixing both the RSA factoring and the calculation of the discrete logarithm problem is:

• RSA-240 seven: 800 core physical years
• RSA-240 matrix: 100 physical core years
• DLP-240 seven: 2400 physical core years
• DLP-240 matrix: 700 physical core years

Moore’s Law takes a back seat

It is the first time that whole number factorization and discrete logarithmic records are broken together. It is also the first time that two records are set with the same hardware and software. These are not the only things that distinguish the last milestones from earlier ones.

When new records are set, the edicts of Moore’s law inevitably play an important role. Moore’s law is the trend that computer chips generally double the number of transistors they have every 18 months. The increase in transistors, in turn, increases the computing power of computers on which they run, so that computers perform faster and better over time.

Although Moore’s law was originally an observation of the co-founder of Intel Gordon Moore in 1965, it is considered an almost inescapable force of nature, such as the laws of nature. Given the relentless march of Moore’s law, it would be unusual for records such as those announced on Monday not to occur regularly.

However, this is less driven by Moore’s law than previous milestones and more by improvements in the software that performs the Number Field Seven. To demonstrate the increase in efficiency, the researchers used their software on hardware that was identical to the one used to calculate the 768-bit discrete logarithm in 2016. They discovered that using the old hardware to record the 795-bit record would cost 25% less time than it took the same equipment to perform the 768-bit DLP calculation.

Another sign of the improved performance: with identical hardware from 2016, the calculation on the 795-bit logarithm was 1.33 times faster than on the 768-bit. Estimates that are generally accepted in the field of cryptography predict that the larger logarithm should be about 2.25 times harder to calculate. In summary, this suggests a triple performance increase compared to what was expected (ie 2.25 * 1.33 = 3). Because the hardware was the same for both bit sizes, the performance improvement is not due to the availability of ever faster computers.

“The acceleration can be attributed to various algorithmic improvements that were implemented for these calculations,” the researchers wrote in Monday’s announcement. The key to those improvements were updates to the open source software that was used to implement the Number Field Sieve. Known as CADO-NFS, it consists of 300,000 lines of code written in C and C ++.

Emmanuel Thomé, a senior researcher at the French National Institute of Computer Science and Applied Mathematics and the leader of the team that set the record, said it is not easy to describe the optimisations in terms of laymen. The improvements, he wrote in an email, include:

• we have worked on better parallelization and memory use (but our competitors did that too, to be very honest).
• we have more systematically benefited from asymptotically fast algorithms in some calculation-intensive parts of the calculation.
• there is a large part of this crypto-record company that evokes the art of ‘choosing parameters’. We did that very well. An important part of the image is the ability to test and rank many different parameter sets using accurate simulation tools that we have developed.

But it is just a little less pointless than saying ‘different improvements’.

Other researchers on the team included Fabrice Boudot, from the French Ministry of National Education and the University of Limoges, Pierrick Gaudry from the French National Center for Scientific Research, Aurore Guillevic with the French National Institute of Computer Science and Applied Mathematics, Nadia Heninger with the University of Pennsylvania and the University of California, San Diego, and Paul Zimmermann of the French National Institute of Computer Science and Applied Mathematics.

With so much attention for the arrival of quantum computers and their ability to easily break public coding today, researchers have been busy developing new schemes that can withstand such attacks.

“In the meantime, researchers have made progress in improving classical factoring and discrete log algorithms, which together with Moore’s law means that new key sizes are fragile by computational resources available to academics,” Heninger wrote in an email. “The takeaway meals for practitioners are in fact that we hope they have followed advice to go to at least 2048-bit RSA, Diffie-Hellman or DSA keys a few years ago, which would protect them from all these improvements.”