RSA Factoring Challenge
The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They published a list of semiprimes (numbers with exactly two prime factors) known as the RSA numbers, with a cash prize for the successful factorization of some of them. The smallest of them, a 100 decimal digit number called RSA-100 was factored by April 1, 1991, but many of the bigger numbers have still not been factored and are expected to remain so for quite some time.
The RSA challenges ended in 2007.[1] RSA Laboratories stated: "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active."[2]
The factoring challenge was intended to track the cutting edge in integer factorization. A primary application is for choosing the key length of the RSA public-key encryption scheme. Progress in this challenge should give an insight into which key sizes are still safe and for how long. As RSA Laboratories is a provider of RSA-based products, the challenge was used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength.
The RSA numbers were generated on a computer with no network connection of any kind. The computer's hard drive was subsequently destroyed so that no record would exist, anywhere, of the solution to the factoring challenge.[3]
The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits; later, however, beginning with RSA-576, binary digits are counted instead. An exception to this is RSA-617, which was created prior to the change in the numbering scheme.
The mathematics
Let n be an RSA Number. RSA Laboratories states there are prime numbers p and q such that
- n = p × q.
The problem is to find these two primes, given only n.
The prizes and records
The following table gives an overview over all RSA numbers.
- The challenge numbers in pink lines are numbers expressed in base 10, while the challenge numbers in yellow lines are numbers expressed in base 2. The prizes for RSA-576 and RSA-640 have been awarded. The remaining prizes have been retracted since the challenge became inactive in 2007.
| RSA Number | Decimal digits | Binary digits | Cash prize offered | Factored on | Factored by |
|---|---|---|---|---|---|
| RSA-100 | 100 | 330 | $1,000 USD | April 1, 1991 | Arjen K. Lenstra |
| RSA-110 | 110 | 364 | $4,429 USD | April 14, 1992 | Arjen K. Lenstra and M.S. Manasse |
| RSA-120 | 120 | 397 | $5,898 | June 9, 1993 | T. Denny et al. |
| RSA-129 | 129 | 426 | $100 USD[4] | April 26, 1994 | Arjen K. Lenstra et al. |
| RSA-130 | 130 | 430 | $14,527 USD | April 10, 1996 | Arjen K. Lenstra et al. |
| RSA-140 | 140 | 463 | $17,226 USD | February 2, 1999 | Herman J. J. te Riele et al. |
| RSA-150[5] | 150 | 496 | April 16, 2004 | Kazumaro Aoki et al. | |
| RSA-155 | 155 | 512 | $9,383 | August 22, 1999 | Herman J. J. te Riele et al. |
| RSA-160 | 160 | 530 | April 1, 2003 | Jens Franke et al., University of Bonn | |
| RSA-170 | 170 | 563 | December 29, 2009 | D. Bonenberger and M. Krone | |
| RSA-576 | 174 | 576 | $10,000 USD | December 3, 2003 | Jens Franke et al., University of Bonn |
| RSA-180 | 180 | 596 | inactive | ||
| RSA-190 | 190 | 629 | inactive | ||
| RSA-640 | 193 | 640 | $20,000 USD | November 2, 2005 | Jens Franke et al., University of Bonn |
| RSA-200 | 200 | 663 | May 9, 2005 | Jens Franke et al., University of Bonn | |
| RSA-210 | 210 | 696 | inactive | ||
| RSA-704 | 212 | 704 | $30,000 USD | inactive, prize retracted | |
| RSA-220 | 220 | 729 | inactive | ||
| RSA-230 | 230 | 762 | inactive | ||
| RSA-232 | 232 | 768 | inactive | ||
| RSA-768 | 232 | 768 | $50,000 USD | December 12, 2009 | Thorsten Kleinjung et.al |
| RSA-240 | 240 | 795 | inactive | ||
| RSA-250 | 250 | 829 | inactive | ||
| RSA-260 | 260 | 862 | inactive | ||
| RSA-270 | 270 | 895 | inactive | ||
| RSA-896 | 270 | 896 | $75,000 USD | inactive, prize retracted | |
| RSA-280 | 280 | 928 | inactive | ||
| RSA-290 | 290 | 962 | inactive | ||
| RSA-300 | 300 | 995 | inactive | ||
| RSA-309 | 309 | 1024 | inactive | ||
| RSA-1024 | 309 | 1024 | $100,000 USD | inactive, prize retracted | |
| RSA-310 | 310 | 1028 | inactive | ||
| RSA-320 | 320 | 1061 | inactive | ||
| RSA-330 | 330 | 1094 | inactive | ||
| RSA-340 | 340 | 1128 | inactive | ||
| RSA-350 | 350 | 1161 | inactive | ||
| RSA-360 | 360 | 1194 | inactive | ||
| RSA-370 | 370 | 1227 | inactive | ||
| RSA-380 | 380 | 1261 | inactive | ||
| RSA-390 | 390 | 1294 | inactive | ||
| RSA-400 | 400 | 1327 | inactive | ||
| RSA-410 | 410 | 1360 | inactive | ||
| RSA-420 | 420 | 1393 | inactive | ||
| RSA-430 | 430 | 1427 | inactive | ||
| RSA-440 | 440 | 1460 | inactive | ||
| RSA-450 | 450 | 1493 | inactive | ||
| RSA-460 | 460 | 1526 | inactive | ||
| RSA-1536 | 463 | 1536 | $150,000 USD | inactive, prize retracted | |
| RSA-470 | 470 | 1559 | inactive | ||
| RSA-480 | 480 | 1593 | inactive | ||
| RSA-490 | 490 | 1626 | inactive | ||
| RSA-500 | 500 | 1659 | inactive | ||
| RSA-617 | 617 | 2048 | inactive | ||
| RSA-2048 | 617 | 2048 | $200,000 USD | inactive, prize retracted | |
See also
- RSA numbers, decimal expansions of the numbers and known factorizations
- The Magic Words are Squeamish Ossifrage, the solution found in 1993 to another RSA challenge posed in 1977
- RSA Secret-Key Challenge
- Integer factorization records
Notes
- ^ RSA Laboratories, The RSA Factoring Challenge. Retrieved on 2007-05-18.
- ^ RSA Laboratories, The RSA Factoring Challenge FAQ. Retrieved on 2007-05-30.
- ^ RSA Laboratories. "The RSA Factoring Challenge FAQ". Retrieved 2008-08-05.
- ^ RSA-129 was not part of the RSA Factoring Challenge, but was related to a column by Martin Gardner in Scientific American.
- ^ RSA-150 was withdrawn from the original challenge by RSA Security, but was factored anyway.