[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RSA-155 factored last weekend
More information is available (seen on the P1363 mailing list, for
example).
--------------------------------
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 =
10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
=
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643