ENGINEERING AND CFD

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.