An international team of computer scientists has set a new record for integer factorization, one of the most important computational problems underlying the security of nearly all public-key cryptography currently used today.
One of the most commonly used public-key cryptographic algorithms for both encryption and digital signatures is the RSA cryptosystem, invented in 1977.
To encourage research into integer factorization, the “RSA Factoring Challenges” were created in 1991. These challenges consisted of challenge integers of varying sizes, named for the number of integer digits.
The team of computer scientists from France and the United States set a new record by factoring the largest integer of this form to date, the RSA-250 cryptographic challenge. This integer is the product of two prime numbers, each with 125 decimal digits. In total, it took 2700 years of running powerful computer cores to carry out the computation, which was done on tens of thousands of machines around the world over the course of a few months.
The key broken with this record computation is smaller than keys that would typically be used in practice by modern cryptographic applications: it has 829 binary bits.
The same team set the previous integer factoring record back in December 2019, when they factored the RSA-240 challenge, a 795-bit integer.
The researchers carried out this computation using CADO-NFS.They used a number of computer clusters, including research group, university, and national research clusters in France, Germany, and UC San Diego.