2.3.6 What is the RSA Factoring Challenge?
The RSA Factoring Challenge was started in March 1991 by RSA Data Security (now RSA Security) to keep abreast of the state of the art in factoring. Since its inception, well over a thousand numbers have been factored, with the factorers returning valuable information on the methods they used to complete the factorizations. The Factoring Challenge provides one of the largest test-beds for factoring implementations and provides one of the largest collections of factoring results from many different experts worldwide. In short, this vast pool of information gives us an excellent opportunity to compare the effectiveness of different factoring techniques as they are implemented and used in practice. Since the security of the RSA public-key cryptosystem relies on the inability to factor large numbers of a special type, the cryptographic significance of these results is self-evident.
The most important result thus far is the factorization of RSA-155 (a number with 155 digits), which was completed in August 1999 after seven months. A group consisting of, among several others, Arjen K. Lenstra and Herman te Riele performed the necessary computations on 300 workstations and PCs. The factorization of this 512-bit number is crucial as 512 is the default key size used for the major part of the e-commerce on Internet. The result indicates that a well-organized group of users such as distributed.net (see Question 2.4.4) might be able to break a 512-bit key in just a couple of days.
Yet, the practical significance of the factorization of RSA-155 should not be exaggerated. The result is very impressive, but the cost for breaking a 512-bit key is still high enough to prevent potential attackers to apply the techniques on a wider basis. Consider it as a reminder of the importance of choosing sufficiently large key sizes; choosing key sizes of at least 768 bits was recommended by RSA Laboratories long before this factorization.
As a curiosity, we mention that the RSA-155 factorization is
10941738641570527421809707322040357612003732945449 20599091384213147634998428893478471799725789126733 24976257528997818337970765372440271467435315933543 33897 = 10263959282974110577205419657399167590071656780803 8066803341933521790711307779 * 10660348838016845482092722036001287867920795857598 9291522270608237193062808643.
For more information about the RSA Factoring Challenges, see http://www.emc.com/emc-plus/rsa-labs/historical/cryptographic-challenges.htm.
The challenge is administered by RSA Security with quarterly cash awards. Send e-mail to firstname.lastname@example.org for more information. For an analysis of early results from the factoring challenge, see [FR95].
A predecessor to the RSA Factoring Challenge is RSA-129. This number is a 129-digit (426-bit) integer published in Martin Gardner's column in Scientific American in 1977; it is not part of the RSA Factoring Challenge. A prize of $100 was offered to anybody able to factor the number; it was factored in March 1994 by Atkins, Graff, Lenstra, and Leyland [AGL95] after eight months of extensive computations.