RSA Factoring Challenge
|
|
The RSA Factoring Challenge is 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. 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 in a few days, but many of the bigger numbers have still not been factored and are expected to remain so for quite some time.
This challenge is intended to track the state of the art in integer factorisation. 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 is used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength.
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.
| Contents |
The mathematics
Let n be a RSA Number. There are prime numbers p and q such that
- <math>n=pq.<math>
The problem is to find these two primes, given only n.
Let s be <math>p+q<math>; then the values of some basic arithmetic functions are
- <math>d(n) = 2<math>
- <math>\phi(n)=(p-1)(q-1) = n + 1 - s<math>
- <math>\sigma(n)=(p+1)(q+1) = n + 1 + s.<math>
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 orange lines are numbers expressed in base 2, and for which a cash prize is still assigned.
| RSA Number | Decimal digits | Binary digits | Cash prize offered | Factored on | Factored by |
|---|---|---|---|---|---|
| RSA-100 | 100 | 330 | April 1991 | ||
| RSA-110 | 110 | 364 | April 1992 | ||
| RSA-120 | 120 | 397 | June 1993 | ||
| RSA-129 | 129 | 426 | $100 USD | April 1994 | Arjen K. Lenstra et al. |
| RSA-130 | 130 | 430 | April 10 1996 | Arjen K. Lenstra et al. | |
| RSA-140 | 140 | 463 | February 2 1999 | Herman J. J. te Riele et al. | |
| RSA-150 | 150 | 496 | withdrawn but factored in 2004 | ||
| RSA-155 | 155 | 512 | 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 | open | ||
| RSA-576 | 174 | 576 | $10,000 USD | December 3, 2003 | Jens Franke et al., University of Bonn |
| RSA-180 | 180 | 596 | open | ||
| RSA-190 | 190 | 629 | open | ||
| RSA-640 | 193 | 640 | $20,000 USD | open | |
| RSA-200 | 200 | 663 | May 9 2005 | Jens Franke et al., University of Bonn | |
| RSA-210 | 210 | 696 | open | ||
| RSA-704 | 212 | 704 | $30,000 USD | open | |
| RSA-220 | 220 | 729 | open | ||
| RSA-230 | 230 | 762 | open | ||
| RSA-232 | 232 | 768 | open | ||
| RSA-768 | 232 | 768 | $50,000 USD | open | |
| RSA-240 | 240 | 795 | open | ||
| RSA-250 | 250 | 829 | open | ||
| RSA-260 | 260 | 862 | open | ||
| RSA-270 | 270 | 895 | open | ||
| RSA-896 | 270 | 896 | $75,000 USD | open | |
| RSA-280 | 280 | 928 | open | ||
| RSA-290 | 290 | 962 | open | ||
| RSA-300 | 300 | 995 | open | ||
| RSA-309 | 309 | 1024 | open | ||
| RSA-1024 | 309 | 1024 | $100,000 USD | open | |
| RSA-310 | 310 | 1028 | open | ||
| RSA-320 | 320 | 1061 | open | ||
| RSA-330 | 330 | 1094 | open | ||
| RSA-340 | 340 | 1128 | open | ||
| RSA-350 | 350 | 1161 | open | ||
| RSA-360 | 360 | 1194 | open | ||
| RSA-370 | 370 | 1227 | open | ||
| RSA-380 | 380 | 1261 | open | ||
| RSA-390 | 390 | 1294 | open | ||
| RSA-400 | 400 | 1327 | open | ||
| RSA-410 | 410 | 1360 | open | ||
| RSA-420 | 420 | 1393 | open | ||
| RSA-430 | 430 | 1427 | open | ||
| RSA-440 | 440 | 1460 | open | ||
| RSA-450 | 450 | 1493 | open | ||
| RSA-460 | 460 | 1526 | open | ||
| RSA-1536 | 463 | 1536 | $150,000 USD | open | |
| RSA-470 | 470 | 1559 | open | ||
| RSA-480 | 480 | 1593 | open | ||
| RSA-490 | 490 | 1626 | open | ||
| RSA-500 | 500 | 1659 | open | ||
| RSA-617 | 617 | 2048 | open | ||
| RSA-2048 | 617 | 2048 | $200,000 USD | open | |
See also
- The Magic Words are Squeamish Ossifrage, the solution found in 1993 to another RSA challenge posed in 1977
- RSA Factoring Challenge numbers list
External links
- RSA Security: The new RSA factoring challenge (http://www.rsasecurity.com/rsalabs/challenges/factoring/)
- MathWorld: RSA Number (http://mathworld.wolfram.com/RSANumber.html)
- Mathematica package for RSA numbers (http://mathworld.wolfram.com/packages/RSANumbers.m)
- The original challenge announcement on sci.crypt (http://www.google.com/groups?selm=BURT.91Mar18092126%40chirality.rsa.com)fr:Compétition de factorisation RSA