On 22 August 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
