spacer back contents
spacer
Special Theme: INFORMATION SECURITY
ERCIM News No.49, April 2002
spacer
spacer
Selected polynomials:
16915642778160*X^5
-756958519686871038*X^4
-13302674486415639704432*X^3
89395931439544311110799193*X^2
81521488422532239989865771400*X^1
-664290154060829787211338433347600*X^0
and
X-74760919650729255820151370977

the number:
39505874583265144526419767800614481996
02077646030493645413937605157935562652
94506836097278424682195350935443058704
90251995655335710209799226484977949442
955603

the prime factors:
33884958374667213943683932046721815228
15830368604993048084925840555281177
and
11658823406671259903148376558383270818
13101225814639260043952099413134433416
2924536139

spacer

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