Factoring large numbers tests security of electronic data transport
A number of 512 bits (155 digits) was factored at CWI on August 22, 1999. Apparently nothing more than yet another factoring record in a long series over the past fifteen years, in which CWI broke world records several times. This time, however, one could speak of a milestone: the factored number models a popular encryption key used on the internet and to secure transactions in the financial world.
RSA is an encryption method invented some twenty years ago by Rivest, Shamir, and Adleman at MIT in the USA, which is widely used nowadays in hardware and software to secure electronic data transport. This ‘public key' method is based on the fact that, given the product of two carefully chosen ‘large' prime numbers, it is difficult to recover those numbers. The key question is: how large is sufficiently large to make this recovery virtually impossible?
In the eighties it was generally held that prime numbers of a fifty odd digits would suffice. However, developments went much faster than foreseen, and 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 if an operative quantum computer will be realized.
Cryptography for the internet
Public-key cryptography is eminently suited for systems with many users, such as the internet. In this method, every user chooses two ‘large' prime numbers and a so-called exponent, and publishes only the exponent and the product of the prime numbers (the ‘public key'). Whoever wants to send him a message encodes it with this public key. The encryption is such that the message can only be decoded if one knows the original prime numbers (a crucial part of the trick is based on modular computation or ‘clock computation'). Hence, the security of this method depends on the ability of others to factor the product.
For a long time factoring belonged to the realm of pure mathematics, without any practical application. The simplest approach is just go through the series of prime numbers 2, 3, 5, ..., and check which primes divide the number to be factored. This method is not very economical, and now far better methods are available. The latest are the Quadratic Sieve (QS) and the Number Field Sieve (NFS), based on an idea of Pierre de Fermat (1601 - 1665).
The RSA-numbers belong to a Challenge List issued by the US company RSA Data Security, Inc., which sells licences and products based on the RSA method. This way 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 factoring has proceeded to well over two hundred digits. November 2000, a 233 digit number, was factored. An international team called ‘The Cabal', under CWI coordination, performed this factorization. The effort could be compared to the factorization of RSA-155.
RSA-155 required a total of 35 years of computing time on one computer, but since the computations were performed mainly in parallel, the job took only seven calendar months. Part of the computing time was provided by CWI. An essential step in the computation, was carried out at the Amsterdam Academic Computing Centre SARA on its supercomputer in about ten calendar days.
Nowadays, distributed computation projects in which tens of thousands of PC' s participate, are already going on. 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.
In January 2002 Jens Frank and his team of the University of Bonn took a step in this direction by factoring an RSA-number of 158 digits, a new world record. This computing job only used a grid of fast PCs and took about three months.
Since the factorization of RSA-155 six large numbers were ‘crunched', all using the same method as for RSA-155. The current world record (2005) is RSA-200, a 200 digit number. The record is accounted to Prof. Jens Franke and his group at the Mathematical Institute of the University of Bonn, with the support of CWI.
Now, three years after the RSA-200 record of Franke and his group in Bonn, no new RSA-records have yet been reported, but new RSA-record attempts are definitely underway: the race is going on!
Dr.ir. H.J.J. te Riele, Herman.te.Riele@cwi.nl