PRESS RELEASE
CWI, Amsterdam - August 26, 1999

Security of E-commerce threatened by 512-bit number factorization
 

On August 22 1999, a team of scientists from six different countries, led by  Herman te Riele of CWI (Amsterdam), found the prime factors of a 512-bit number,  whose size models 95% of the keys used for protection of electronic commerce  on the Internet. This result shows, much earlier than expected at the start  of E-commerce, that the popular key-size of 512 bits is no longer safe against  even a moderately powerful attacker. The amount of money protected by 512-bit keys is immense. Many billions of dollars per day are flowing through financial institutions such as banks and stock exchanges.

The factored key is a model of a so-called "public key" in the well-known  RSA cryptographic system which was designed in the mid-seventies by  Rivest, Shamir and Adleman at the Massachusets Institute of Technology  in Cambridge, USA. At present, this system is used extensively in hardware  and software to protect electronic data traffic such as in the international  version of the SSL (Security Sockets Layer) Handshake Protocol.

Apart from its practical implications, the factorization is a scientific breakthrough: 25 years ago, 512-bit numbers (about 155 decimals) were thought virtually impossible to factor. Estimates based on the then-fastest known algorithms and computers predicted a CPU time of more than 50 billion  (50 000 000 000) years.

The factored number, indicated by RSA-155, was taken from the  "RSA Challenge List", which is used as a yardstick for the security of  the RSA cryptosystem.

In order to find the prime factors of RSA-155, about 300 fast SGI and SUN workstations and Pentium PCs have spent about 35 years of computing time. The computers were running in parallel -- mostly overnight and at weekends -- and the whole task was finished in about seven calendar-months.
The following organizations have made their workstation and PC computing
power available to this project:
Centre Charles Hermite (Nancy, France),
Citibank (Parsippany, NJ, USA),
CWI (Amsterdam),
Ecole Polytechnique/CNRS (Palaiseau, France),
Entrust Technologies (Ottawa, Canada),
Lehigh University (Bethlehem, Pa, USA),
the Medicis Center at Ecole Polytechnique (Palaiseau, France),
Microsoft Research (Cambridge, UK),
Sun Microsystems Professional Services (Camberley, UK),
The Australian National University (Canberra, Australia),
University of Sydney (Australia).

In addition, an essential step of the project which requires 2 Gbytes of internal memory has been carried out on the Cray C916 supercomputer at SARA (Academic Computing Centre Amsterdam).

Given the current big distributed computing projects on Internet with  hundreds of thousands of participants, e.g., to break RSA's DES Challenge  or trace extra-terrestrial messages, it is possible to reduce the time to  factor a 512-bit number from seven months to one week. For comparison, the amount of computing time needed to factor RSA-155 was  less than 2% of the time needed to break RSA's DES challenge.

Coordinator of the project is Herman te Riele of CWI Amsterdam.

The number and the found factors are:

RSA-155 =
109417386415705274218097073220403576120037329454492059909138421314763499842889\
34784717997257891267332497625752899781833797076537244027146743531593354333897
=
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643
 
 

==============================================================================
Note to the editors:
Further information: Herman te Riele, tel. +31 (20 - 592 4106), e-mail: Herman.te.Riele@cwi.nl
http://dbs.cwi.nl:8080/cwwwi/owa/cwwwi.print_projects?ID=12

CWI:
CWI is the national research institute for mathematics and computer science in the Netherlands. Its mission is to perform frontier research in mathematics and computer science, and to transfer this knowledge to society in genreal, and trade and industry in particular. CWI gets a basic subsidy from the Netherlands Organisation for Scientific Research NWO (70%) ; 30% of CWI's budget comes from (inter)national research programmes and commissions from industry and government. CWI is located at the 'Wetenschappelijk Centrum Watergraafsmeer' in Amsterdam, the Netherlands.