Data sent over the internet relies on public key cryptographical systems to remain secure. Paul Zimmermann of INRIA has been leading a project that has been carrying out record computations of integer factorisation and the discrete logarithm problem, the results of which are used as a benchmark for setting the length of the keys needed to keep such systems secure.
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.
RSA numbers come from the RSA Factoring Challenge put forward by RSA Laboratories in 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They published a list of semiprimes (numbers with exactly two prime factors) known as the RSA numbers. Zimmermann and his team recently set the integer factorisation record with the factorisation of RSA-250 (shown above in red, with the solution in white).
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 Juelich Supercomputing Centre in Germany. 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, RSA250, 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 accepted for publication 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. We can therefore easily calculate the length of keys that would be impossible for such hypothetical government state attackers to break.
Paul Zimmermann, Project Principal Investigator
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 PRACE machine in Germany.”
For more information: caramba.loria.fr/dlp240-rsa240.txt
Resources awarded by PRACE: This project was awarded 32 000 000 core hours on JUWELS hosted by GCS at FZJ, Germany
This article was first published by PRACE on 12 October 2020. It was republished on ScienceNode.