Security of E-commerce threatened by 512-bit Number Factorization
by Henk Nieland
On August 22, 1999, a team of scientists from six different countries, led by Herman te Riele of CWI, 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 MIT. 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. However, developments went much faster than foreseen, and at present it is a precarious matter to venture upon quantitative forecasts in this field. When Rivest challenged the world in 1977 to factor RSA-129, a 129 digit number (from a special list), he estimated that on the basis of contemporary computational methods and computer systems this would take about 1016 years of computing time. Seventeen years later it took only eight months in a world-wide cooperative effort to do the job. Moreover, one should realize that it always remains possible that a new computational method is invented which makes factoring ‘easy’ (for example quantum computing, if an operative quantum computer will ever be realized).
The factored number, indicated as RSA-155, belongs to a Challenge List issued by the US company RSA Data Security, Inc., which sells licences and products based on the RSA method. Thus the company hopes to remain well-informed about the power of factoring methods. Factoring numbers on this list measures how secure the RSA method actually is. For special numbers, for example of the form ab ±1, factoring has proceeded to well over two hundred digits. Here too CWI holds the world record: in April 1999 the 211-digit number (10211 - 1)/9 was factored, a computational effort comparable to factoring RSA-140.
RSA-155 required a total of 35 years of computing time on some 300 very fast SGI and SUN workstations and Pentium II PCs. Since the computations were performed mainly in parallel, the job took only seven calendar months. Computing time was provided by Citibank (US), CWI (The Netherlands), Ecole Polytechnique (France), Entrust Technologies (Canada), Centre Charles Hermite (France), Lehigh University (US), Microsoft Research (UK), Sun Microsystems (UK), and the University of Sydney (Australia). An essential step in the computation requiring an extreme amount of internal memory, was carried out at the Amsterdam Academic Computing Centre SARA on its Cray C916 supercomputer in about ten calendar days. Distributed computation projects in which tens of thousands of PCs participate, are already underway. Combined with parallelizing the supercomputer’s part in the computation (still being investigated), this warrants the expectation that factoring 512-bit numbers will require only a few days before long.
Links:
Computational number theory and data security at CWI: http://dbs.cwi.nl:8080/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
