New Prime Factorisation Record obtained
using the General Number Field Sieve
by Friedrich Bahr, Jens Franke and Thorsten Kleinjung
A team of researchers at the University of Bonn established a new record in the art of factoring general integers into primes on 18 January 2002. This has implications for public-key cryptography.
Since the safety of the RSA cryptosystem depends on the difficulty of factoring general integers into primes, the selection of key size for this cryptosystem depends on the state of the art in this area of algorithmic number theory and on likely improvements in the future. Using a new implementation of the general number field sieve (GNFS), we have factored a 158-digit divisor of 2953-1, establishing a new record for the factorisation of general numbers without small divisors into primes.
The previous record was a 155-digit RSA challenge number factored by a team of mathematicians led by CWI in 1999.
Integer factorisations by GNFS start with a massively parallel polynomial selection step. This is followed by the sieving step, which is also massively parallel and takes most of the CPU time. Both steps are usually carried out using the idle time of ordinary office PCs or workstations. Our new contribution to this step is a new algorithm for lattice sieving, which results in a considerable improvement in speed compared to CWI's implementation.
The most time-consuming part of post-processing the siever output can be thought of as a linear algebra problem over the field F2 with two elements on a sparse matrix of a few hundred million rows and columns. In a first filtering step, the size of this matrix is reduced to a few million rows and columns. This condensed matrix is then solved using a block Lanczos algorithm for sparse matrices over F2. For the previous record, the filtering step was done on a large workstation and the Lanczos algorithm was run on a Cray 90 supercomputer. We wrote parallel implementations for both the filtering and the Lanczos step, running them on a LINUX cluster built by the scientific computing department at the institute for applied mathematics in Bonn.
Conclusion
Due to improvements in the algorithms and their implementation as well as improvements in computer hardware since the CWI broke the 512-bit threshold in 1999, factoring a 512-bit RSA key within a year now costs less than 3000 Euro. Extrapolation of the development of the GNFS in the 1990s makes it likely that 768-bit keys become vulnerable at comparable cost within the decade starting in 2010. For large or medium-sized governments, they may become vulnerable within this decade.
We are indebted to the scientific computing department at the Institute for Applied Mathematics and to the Mathematical Institute at Bonn University for providing much of the computer hardware used for this record.
Links:
http://www.crypto-world.com/announcements/c158.txt
http://www.loria.fr/~zimmerma/records/gnfs158
http://wissrech.iam.uni-bonn.de/research/projects/parnass2
Please contact:
Friedrich Bahr, Jens Franke,
Thorsten Kleinjung,
University of Bonn, Germany
Tel: +49 228 73 29 52
E-mail: franke@math.uni-bonn.de
|
