RSA Factoring Challenge

Last updated

The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 [1] 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. Many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time, however advances in quantum computers make this prediction uncertain due to Shor's algorithm.

Contents

In 2001, RSA Laboratories expanded the factoring challenge and offered prizes ranging from $10,000 to $200,000 for factoring numbers from 576 bits up to 2048 bits. [2] [3] [4]

The RSA Factoring Challenges ended in 2007. [5] 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." [6] When the challenge ended in 2007, only RSA-576 and RSA-640 had been factored from the 2001 challenge numbers. [7]

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. [6]

The first RSA numbers generated, RSA-100 to RSA-500 and RSA-617, were labeled according to their number of decimal digits; the other RSA numbers (beginning with RSA-576) were generated later and labelled according to their number of binary digits. The numbers in the table below are listed in increasing order despite this shift from decimal to binary.

The mathematics

RSA Laboratories states that: for each RSA number n, there exist 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. Note that the RSA Factoring Challenge ended in 2007 [5] and no further prizes will be awarded for factoring the higher numbers.

The challenge numbers in white lines are part of the original challenge and are expressed in base 10, while the challenge numbers in yellow lines are part of the 2001 expansion and are expressed in base 2
RSA numberDecimal digitsBinary digitsCash prize offeredFactored onFactored by
RSA100 100330US$1,000 [8] April 1, 1991 [9] Arjen K. Lenstra
RSA110 110364US$4,429 [8] April 14, 1992 [9] Arjen K. Lenstra and M.S. Manasse
RSA120 120397US$5,898 [8] July 9, 1993 [10] T. Denny et al.
RSA129 [a] 129426US$100April 26, 1994 [9] Arjen K. Lenstra et al.
RSA130 130430US$14,527 [8] April 10, 1996 Arjen K. Lenstra et al.
RSA140 140463US$17,226February 2, 1999 Herman te Riele et al.
RSA150 150496 April 16, 2004 Kazumaro Aoki et al.
RSA155 155512US$9,383 [8] August 22, 1999 Herman te Riele et al.
RSA160 160530 April 1, 2003 Jens Franke et al., University of Bonn
RSA170 [b] 170563 December 29, 2009D. Bonenberger and M. Krone [c]
RSA576 174576US$10,000December 3, 2003 Jens Franke et al., University of Bonn
RSA180 [b] 180596 May 8, 2010S. A. Danilov and I. A. Popovyan, Moscow State University [11]
RSA190 [b] 190629 November 8, 2010A. Timofeev and I. A. Popovyan
RSA640 193640US$20,000November 2, 2005 Jens Franke et al., University of Bonn
RSA200 [b]  ?200663 May 9, 2005 Jens Franke et al., University of Bonn
RSA210 [b] 210696September 26, 2013 [12] Ryan Propper
RSA704 [b] 212704US$30,000July 2, 2012Shi Bai, Emmanuel Thomé and Paul Zimmermann
RSA220 [b] 220729 May 13, 2016S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann
RSA230 [b] 230762 August 15, 2018Samuel S. Gross, Noblis, Inc.
RSA232 [b] 232768 February 17, 2020 [13] N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev.
RSA768 [b] 232768US$50,000December 12, 2009 Thorsten Kleinjung et al. [14]
RSA240 [b] 240795 Dec 2, 2019 [15] F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA250 [b] 250829 Feb 28, 2020 [16] F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA260 260862 
RSA270 270895 
RSA896 270896US$75,000 [d]
RSA280 280928 
RSA290 290962 
RSA300 300995 
RSA309 3091024 
RSA1024 3091024US$100,000 [d]
RSA310 3101028 
RSA320 3201061 
RSA330 3301094 
RSA340 3401128 
RSA350 3501161 
RSA360 3601194 
RSA370 3701227 
RSA380 3801261 
RSA390 3901294 
RSA400 4001327 
RSA410 4101360 
RSA420 4201393 
RSA430 4301427 
RSA440 4401460 
RSA450 4501493 
RSA460 4601526 
RSA1536 4631536US$150,000 [d]
RSA470 4701559 
RSA480 4801593 
RSA490 4901626 
RSA500 5001659 
RSA617 6172048 
RSA2048 6172048US$200,000 [d]
  1. ↑ RSA-129 was not part of the RSA Factoring Challenge, but was related to a column by Martin Gardner in Scientific American .
  2. 1 2 3 4 5 6 7 8 9 10 11 12 The number was factored after the challenge ended.
  3. ↑ RSA-170 was also independently factored by S. A. Danilov and I. A. Popovyan two days later. [11]
  4. 1 2 3 4 The challenge ended before this prize was awarded.

See also

Notes

  1. ↑ Kaliski, Burt (18 Mar 1991). "Announcement of "RSA Factoring Challenge"". Archived from the original on August 11, 2023. Retrieved 8 March 2021.
  2. ↑ Leyden, John (25 Jul 2001). "RSA poses $200,000 crypto challenge". The Register. Retrieved 8 March 2021.
  3. ↑ RSA Laboratories. "The New RSA Factoring Challenge". Archived from the original on 2001-07-14.
  4. ↑ RSA Laboratories. "The RSA Challenge Numbers". Archived from the original on 2001-08-05.
  5. 1 2 RSA Laboratories. "RSA Factoring Challenge". Archived from the original on 2013-09-21. Retrieved 2008-08-05.
  6. 1 2 RSA Laboratories. "The RSA Factoring Challenge FAQ". Archived from the original on 2013-09-21. Retrieved 2008-08-05.
  7. ↑ RSA Laboratories. "The RSA Challenge Numbers". Archived from the original on 2013-09-21. Retrieved 2008-08-05.
  8. 1 2 3 4 5 "Status/news report on RSA data security factoring challenge (as of 3/30/00)". 30 January 2002.
  9. 1 2 3 RSA Honor Roll
  10. ↑ Denny, T.; Dodson, B.; Lenstra, A. K.; Manasse, M. S. (1994). On the factorization of RSA-120. Advances in Cryptology – CRYPTO' 93. Lecture Notes in Computer Science. Vol. 773. pp. 166–174. doi: 10.1007/3-540-48329-2_15 . ISBN   978-3-540-57766-9.
  11. 1 2 Danilov, S. A.; Popovyan, I. A. (9 May 2010). "Factorization of RSA-180" (PDF). Cryptology ePrint Archive.
  12. ↑ RSA-210 factored, mersenneforum.org
  13. ↑ INM RAS news
  14. ↑ Kleinjung, Thorsten; Aoki, Kazumaro; et al. (2010). "Factorization of a 768-Bit RSA Modulus" (PDF). In Tal Rabin (ed.). Advances in Cryptology – CRYPTO 2010. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 333–350. ISBN   978-3-642-14623-7.
  15. ↑ Thomé, Emmanuel (December 2, 2019). "795-bit factoring and discrete logarithms". cado-nfs-discuss (Mailing list).
  16. ↑ Zimmermann, Paul (February 28, 2020). "Factorization of RSA-250". cado-nfs-discuss (Mailing list).
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.