New Records for Integer Factorization and Discrete Logarithm
French National Institute for computer science and applied mathematics (INRIA), France
Local Project ID:
HPC Platform used:
JUWELS of JSC
Public key cryptography is a mainstay of the internet, allowing people to send secure, sensitive data over what is essentially an insecure network. It uses a pair of keys to encrypt and decrypt data to protect it against unauthorised access or use. Network users have a pair of keys, one private and one public. If other users want to send encrypted data to someone, they get the intended recipient’s public key from a public directory. This key is used to encrypt the message, and to send it to the recipient. When the message arrives, the recipient decrypts it using their private key, to which no one else has access.
For public key cryptography to work, it is essential that computing the private key from the public key is computationally infeasible. This means that public keys can be freely shared, allowing users an easy and convenient method for encrypting content and verifying digital signatures. Private keys, meanwhile, can be kept secret, ensuring only their owners can decrypt content meant for them.
Nowadays, many of the main algorithms for public key cryptography are based on the RSA cryptosystem, which leverages the difficulty of factorisation into prime numbers i.e. working out the two prime numbers (the private key) that can be multiplied together to reach a specific very large “semi-prime” number (the public key). The other main group of algorithms used for public key cryptography are based on the discrete logarithm problem (DLP), which is also mathematically difficult to solve.
Paul Zimmermann is a computational mathematician who has contributed to a number of the record computations for integer factorisation and discrete logarithm. Recently, he and five colleagues tasked themselves with setting new records for each of these problems with numbers of the same size. Zimmermann was looking to disprove the previously held belief that the discrete logarithm problem is harder to solve than integer factorisation. “We wanted to show that these problems are actually about the same in difficulty,” says Zimmermann. “To prove this, we used the same hardware, the same software, around
the same amount of CPU hours and the same algorithm – the number field sieve – to set new equally-sized records.”
Zimmermann and his colleagues used their own implementation of the number field sieve algorithm in a piece of publicly-available software they developed called CADO-NFS. In December 2019 the group announced two new records, RSA-240 and DLP-240. In the case of the RSA number, the 240 indicates that the group were able to calculate the two prime factors of a given 240 digit semi-prime number.
These records were set using a 32 million core hour allocation at the Jülich Supercomputing Centre. After having set these records, however, the group had some time remaining within their allocation, and thus were also able to set another new record, RSA-250, which was announced in February 2020.
Algorithmic development within the CADO-NFS software was largely responsible for the achievement of these new records, the details of which are outlined in a paper that has been published at the Crypto 2020 conference. “The variants of the algorithm allowed us to speed up our calculations by a factor of between two and three,” explains Zimmermann. “For example, if we compare the discrete logarithm problem record to the previous one, mathematically the new record should be about three times more difficult. But, if you compare the running times, we used about the same number of CPU hours.”
The setting of these records represents an important benchmark for the design of modern cryptography schemes. When creating new schemes, it is important to know that they will be secure not only now but also for the next ten or twenty years. Government agencies use these records to provide recommendations for key sizes to ensure that they are secure.
“When we set these records, we know that if a government state were to try and break such a cryptography scheme that they would have computing power in the order of ten times more powerful than we have at our disposal,” explains Zimmermann. “We can therefore easily calculate the length of keys that would be impossible for such hypothetical government state attackers to break.”
This was the group’s first PRACE project, having previously used the French Grid’5000 testbed for their work. “The Grid’5000 was not really built for production work – it was made for the development of new parallel algorithms,” says Zimmermann. “Although we were able to use it for our work previously, the advantage of the resources that PRACE offer is that they provide access to a lot of homogeneous CPUs at the same time.”
During the peak of the project, which ran for a year starting from 1st April, 2019, the researchers had access to 128 nodes, each with about 100 cores, meaning that they had around 12 000 homogeneous cores working on the problem at the same time. “The hardware at hand made our work much easier,” says Zimmermann. “Our job was also made easier by the excellent support from the PRACE engineers, although we had very few problems when running CADO-NFS on the HPC system installed at JSC, made available to us by a computing time allocation through PRACE.”
Fabrice Boudot2, Pierrick Gaudry4, Aurore Guillevic1, Nadia Heninger3, Emmanuel Thomé1, Paul Zimmermann (PI)1,
1French National Institute for Computer Science and Applied Mathematics (INRIA), France
2Education Nationale, France
3University of Pennsylvania, United States of America
Dr. Paul Zimmermann
Centre de recherche Inria Nancy Grand Est
Équipe-Projet CARAMBA - bâtiment B
615 rue du jardin botanique, F-54600 Villers-lès-Nancy Cedex (France)
e-mail: Paul.Zimmermann [@] inria.fr
NOTE: This is a reprint of the article published by PRACE. The simulation project was made possible by PRACE (Partnership for Advanced Computing in Europe) allocating a computing time grant on GCS HPC system JUWELS of the Jülich Supercomputing Centre (JSC). GCS is a hosting member of PRACE.
LRZ project ID: RSA250