ERCIM News No.35 - October 1998

Factoring Record starts Attack on RSA Code

by Henk Nieland

---

A 186-digit number was factored at CWI early September. This number, compactly written as 3263341 - 1, was factored with the ‘Special Number Field Sieve’, a method particularly suited to numbers of this form.

The previous factoring record with this method, a 181-digit number, was realized about one year ago also at CWI. Although apparently not a spectacular progress, the acquired experience enables CWI researchers Stefania Cavallar, Peter Montgomery (visitor from the USA) and Herman te Riele to attack now a 512-bit RSA key - the present most prominent challenge in this field - using the still more powerful General Number Field Sieve method. This will be done in cooperation with Microsoft and a few other institutions disposing of abundant computing power. The RSA cryptosystem, still considered as virtually uncrackable, is based on the difficulty to factor certain large numbers. The researchers expect to finish the job still in this millennium.

The factoring was completed within one and a half month using 88 SGI/Cray computers at CWI and the Cray C90 supercomputer at the Academic Computing Centre SARA. The factored number was not just another toy for CWI’s number addicts. Last year Warren D. Smith of NEC Research Institute in Princeton asked CWI - a world leader in this field - to factor this number for him. At NEC Research one is interested in fast and reliable algorithms generating random number sets which are applied, eg, in physics (experiment simulation) and the financial world (assessing the value of investment portfolios). Testing the quality of certain random number generators requires the knowledge of the prime factors of numbers having the form of the number now factored at CWI.

More information at http://dbs.cwi.nl/cwwwi/owa/cwwwi.print_projects?ID=12

Please contact:

Herman te Riele - CWI
Tel: +31 20 592 4106
E-mail: Herman.te.Riele@cwi.nl