Editing RSA Factoring Challenge

{{Short description|Challenge for factoring large semiprimes}}
The '''RSA Factoring Challenge''' was a challenge put forward by [[RSA Laboratories]] on March 18, 1991<ref>{{cite news |last1=Kaliski |first1=Burt |title=Announcement of "RSA Factoring Challenge" |url=https://groups.google.com/u/1/g/sci.crypt/c/AA7M9qWWx3w/m/EkrsR69CDqIJ |archive-url=https://archive.today/20230811232741/https://groups.google.com/u/1/g/sci.crypt/c/AA7M9qWWx3w/m/EkrsR69CDqIJ |url-status=dead |archive-date=August 11, 2023 |access-date=8 March 2021 |date=18 Mar 1991}}</ref> to encourage research into [[computational number theory]] and the practical difficulty of [[Factorization|factoring]] large [[integer]]s and cracking [[RSA (algorithm)|RSA]] keys used in [[cryptography]]. They published a list of [[semiprime]]s (numbers with exactly two [[prime factor]]s) 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 computer]]s make this prediction uncertain due to [[Shor's algorithm]].

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.<ref>{{cite news |last1=Leyden |first1=John |title=RSA poses $200,000 crypto challenge |url=https://www.theregister.com/2001/07/25/rsa_poses_200_000_crypto/ |access-date=8 March 2021 |work=The Register |date=25 Jul 2001}}</ref><ref name="rsa-challenge-2001">{{cite web |url=http://www.rsa.com/rsalabs/challenges/factoring/numbers.html |title=The New RSA Factoring Challenge |author=RSA Laboratories |archive-url=https://web.archive.org/web/20010714162913/http://www.rsa.com/rsalabs/challenges/factoring/index.html |archive-date=2001-07-14 |url-status=dead }}</ref><ref name="rsa-numbers-2001">{{cite web |url=http://www.rsa.com/rsalabs/challenges/factoring/numbers.html |title=The RSA Challenge Numbers |author=RSA Laboratories |archive-url=https://web.archive.org/web/20010805210445/http://www.rsa.com/rsalabs/challenges/factoring/numbers.html |archive-date=2001-08-05 |url-status=dead }}</ref>

The RSA Factoring Challenges ended in 2007.<ref name="rsa-factoring-challenge">{{cite web |url=http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm |title=RSA Factoring Challenge |author=RSA Laboratories |accessdate=2008-08-05 |archive-url=https://web.archive.org/web/20130921043459/http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm |archive-date=2013-09-21 |url-status=dead }}</ref> RSA Laboratories stated: "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common [[Symmetric key algorithm|symmetric-key]] and [[Public key algorithm|public-key algorithm]]s, these challenges are no longer active."<ref name="rsa-factoring-challenge-faq">{{cite web |url=http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm |title=The RSA Factoring Challenge FAQ |author=RSA Laboratories |accessdate=2008-08-05 |archive-url=https://web.archive.org/web/20130921043454/http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm |archive-date=2013-09-21 |url-status=dead }}</ref> When the challenge ended in 2007, only RSA-576 and RSA-640 had been factored from the 2001 challenge numbers.<ref>{{cite web |url=http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm |title=The RSA Challenge Numbers |author=RSA Laboratories |accessdate=2008-08-05 |archive-url=https://web.archive.org/web/20130921041734/http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm |archive-date=2013-09-21 |url-status=dead }}</ref>

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 (algorithm)|RSA]] [[public-key encryption]] scheme. Progress in this challenge should give an insight into which [[key size]]s 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 &mdash; 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.<ref name="rsa-factoring-challenge-faq" />

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 numeral system|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 number]]s ''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<ref name="rsa-factoring-challenge"/> 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]]''
{| class="wikitable"
|-
! RSA number
! Decimal digits
! Binary digits
! Cash prize offered
! Factored on
! Factored by
|-
| [[RSA numbers#RSA-100|RSA100]]
| 100
| 330
| US$1,000<ref name="rsa-news">{{cite web|url=http://www.ontko.com/~rayo/primes/rsa_news.txt|title=Status/news report on RSA data security factoring challenge (as of 3/30/00)|date=30 January 2002}}</ref>
| April 1, 1991<ref name="honor-roll">[http://www.ontko.com/~rayo/primes/hr_rsa.txt RSA Honor Roll]</ref>
| [[Arjen K. Lenstra]]
|-
| [[RSA numbers#RSA-110|RSA110]]
| 110
| 364
| US$4,429<ref name="rsa-news" />
| April 14, 1992<ref name="honor-roll" />
| [[Arjen K. Lenstra]] and [[M.S. Manasse]]
|-
| [[RSA numbers#RSA-120|RSA120]]
| 120
| 397
| US$5,898<ref name="rsa-news" />
| July 9, 1993<ref>{{cite conference|title=On the factorization of RSA-120|last1=Denny|first1=T.|last2=Dodson|first2=B.|last3=Lenstra|first3=A. K.|last4=Manasse|first4=M. S.|work=Advances in Cryptology – CRYPTO' 93|series=Lecture Notes in Computer Science |date=1994|volume=773 |pages=166–174|doi=10.1007/3-540-48329-2_15|isbn=978-3-540-57766-9 |doi-access=free}}</ref>
| [[T. Denny]] ''et al.''
|-
| [[RSA numbers#RSA-129|RSA129]]{{efn|RSA-129 was not part of the RSA Factoring Challenge, but was related to a column by Martin Gardner in ''[[Scientific American]]''.}}
| 129
| 426
| US$100
| April 26, 1994<ref name="honor-roll" />
| [[Arjen K. Lenstra]] ''et al.''
|-
| [[RSA numbers#RSA-130|RSA130]]
| 130
| 430
| US$14,527<ref name="rsa-news" />
| April 10, 1996
| [[Arjen K. Lenstra]] ''et al.''
|-
| [[RSA numbers#RSA-140|RSA140]]
| 140
| 463
| US$17,226
| February 2, 1999
| [[Herman te Riele]] ''et al.''
|-
| [[RSA numbers#RSA-150|RSA150]]
| 150
| 496
| &nbsp;
| April 16, 2004
| [[Kazumaro Aoki]] ''et al.''
|-
| [[RSA numbers#RSA-155|RSA155]]
| 155
| 512
| US$9,383<ref name="rsa-news" />
| August 22, 1999
| [[Herman te Riele]] ''et al.''
|-
| [[RSA numbers#RSA-160|RSA160]]
| 160
| 530
| &nbsp;
| April 1, 2003
| [[Jens Franke]] ''et al.'', [[University of Bonn]]
|-
| [[RSA numbers#RSA-170|RSA170]]{{efn|The number was factored after the challenge ended.|name=retracted}}
| 170
| 563
| &nbsp;
| December 29, 2009
| D. Bonenberger and M. Krone{{efn|RSA-170 was also independently factored by S. A. Danilov and I. A. Popovyan two days later.<ref name="rsa-180" />}}
|- style="background:#ffebad;"
| [[RSA numbers#RSA-576|RSA576]]
| 174
| 576
| US$10,000
| December 3, 2003
| [[Jens Franke]] ''et al.'', [[University of Bonn]]
|-
| [[RSA numbers#RSA-180|RSA180]]{{efn|name=retracted}}
| 180
| 596
| &nbsp;
| May 8, 2010
| S. A. Danilov and I. A. Popovyan, [[Moscow State University]]<ref name="rsa-180">{{cite journal|url=http://eprint.iacr.org/2010/270.pdf|title=Factorization of RSA-180|first1=S. A.|last1=Danilov|first2=I. A.|last2=Popovyan|date=9 May 2010|journal=Cryptology ePrint Archive}}</ref>
|-
| [[RSA numbers#RSA-190|RSA190]]{{efn|name=retracted}}
| 190
| 629
| &nbsp;
| November 8, 2010
| A. Timofeev and I. A. Popovyan
|- style="background:#ffebad;"
| [[RSA numbers#RSA-640|RSA640]]
| 193
| 640
| US$20,000
| November 2, 2005
| [[Jens Franke]] ''et al.'', [[University of Bonn]]
|-
| [[RSA numbers#RSA-200|RSA200]]{{efn|name=retracted}}&nbsp;<sup>'''?'''</sup>
| 200
| 663
| &nbsp;
| May 9, 2005
| [[Jens Franke]] ''et al.'', [[University of Bonn]]
|-
| [[RSA numbers#RSA-210|RSA210]]{{efn|name=retracted}}
| 210
| 696
|
| September 26, 2013<ref>[http://www.mersenneforum.org/showpost.php?p=354259 RSA-210 factored], mersenneforum.org</ref>
| Ryan Propper
|- style="background:#ffebad;"
| [[RSA numbers#RSA-704|RSA704]]{{efn|name=retracted}}
| 212
| 704
| US$30,000
| July 2, 2012 || Shi Bai, Emmanuel Thomé and [[Paul Zimmermann (mathematician)|Paul Zimmermann]]
|-
| [[RSA numbers#RSA-220|RSA220]]{{efn|name=retracted}}
| 220
| 729
| &nbsp;
| May 13, 2016
| S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann
|-
| [[RSA numbers#RSA-230|RSA230]]{{efn|name=retracted}}
| 230
| 762
| &nbsp;
| August 15, 2018
| Samuel S. Gross, Noblis, Inc.
|-
| [[RSA numbers#RSA-232|RSA232]]{{efn|name=retracted}}
| 232
| 768
| &nbsp;
| February 17, 2020<ref>[https://www.inm.ras.ru/math_center_en/rsa-232-number-has-been-factored-5/ INM RAS news]</ref>
| N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev.

|- style="background:#ffebad;"
| [[RSA numbers#RSA-768|RSA768]]{{efn|name=retracted}}
| 232
| 768
| US$50,000
| December 12, 2009
| [[Thorsten Kleinjung]] ''et al.''<ref name="rsa-768-paper">{{Cite conference| publisher = Springer Berlin Heidelberg| isbn = 978-3-642-14623-7| pages = 333–350| editor = Tal Rabin | last1 = Kleinjung| first1 = Thorsten|last2 = Aoki| first2 = Kazumaro| last3 = Franke| first3 = Jens| last4 = Lenstra| first4 = Arjen K.| last5 = Thomé| first5 = Emmanuel| last6 = Bos| first6 = Joppe W.| last7 = Gaudry| first7 = Pierrick| last8 = Kruppa| first8 = Alexander| last9 = Montgomery| first9 = Peter L.| last10 = Osvik| first10 = Dag Arne| last11 = te Riele| first11 = Herman| last12 = Timofeev| first12 = Andrey| last13 = Zimmermann| first13 = Paul| title = Factorization of a 768-Bit RSA Modulus| book-title = Advances in Cryptology – CRYPTO 2010| location = Berlin, Heidelberg| date = 2010|url=https://link.springer.com/content/pdf/10.1007/978-3-642-14623-7_18.pdf|display-authors=2}}</ref>
|-
| [[RSA numbers#RSA-240|RSA240]]{{efn|name=retracted}}
| 240
| 795
| &nbsp;
| Dec 2, 2019<ref>{{cite mailing list|url=https://sympa.inria.fr/sympa/arc/cado-nfs/2019-12/msg00000.html|title=795-bit factoring and discrete logarithms|mailing-list=cado-nfs-discuss|first=Emmanuel|last=Thomé|date=December 2, 2019}}</ref>
| F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
|-
| [[RSA numbers#RSA-250|RSA250]]{{efn|name=retracted}}
| 250
| 829
| &nbsp;
| Feb 28, 2020<ref>{{cite mailing list|url=https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.html|title=Factorization of RSA-250|mailing-list=cado-nfs-discuss|first=Paul|last=Zimmermann|date=February 28, 2020}}</ref>
| F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
|-
| [[RSA numbers#RSA-260|RSA260]]
| 260
| 862
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-270|RSA270]]
| 270
| 895
| &nbsp;
| colspan="2" style="text-align:center;"|
|- style="background:#ffebad;"
| [[RSA numbers#RSA-896|RSA896]]
| 270
| 896
| US$75,000{{efn|The challenge ended before this prize was awarded.|name=not-awarded}}
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-280|RSA280]]
| 280
| 928
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-290|RSA290]]
| 290
| 962
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-300|RSA300]]
| 300
| 995
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-309|RSA309]]
| 309
| 1024
| &nbsp;
| colspan="2" style="text-align:center;"|
|- style="background:#ffebad;"
| [[RSA numbers#RSA-1024|RSA1024]]
| 309
| 1024
| US$100,000{{efn|name=not-awarded}}
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-310|RSA310]]
| 310
| 1028
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-320|RSA320]]
| 320
| 1061
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-330|RSA330]]
| 330
| 1094
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-340|RSA340]]
| 340
| 1128
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-350|RSA350]]
| 350
| 1161
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-360|RSA360]]
| 360
| 1194
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-370|RSA370]]
| 370
| 1227
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-380|RSA380]]
| 380
| 1261
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-390|RSA390]]
| 390
| 1294
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-400|RSA400]]
| 400
| 1327
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-410|RSA410]]
| 410
| 1360
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-420|RSA420]]
| 420
| 1393
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-430|RSA430]]
| 430
| 1427
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-440|RSA440]]
| 440
| 1460
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-450|RSA450]]
| 450
| 1493
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-460|RSA460]]
| 460
| 1526
| &nbsp;
| colspan="2" style="text-align:center;"|
|- style="background:#ffebad;"
| [[RSA numbers#RSA-1536|RSA1536]]
| 463
| 1536
| US$150,000{{efn|name=not-awarded}}
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-470|RSA470]]
| 470
| 1559
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-480|RSA480]]
| 480
| 1593
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-490|RSA490]]
| 490
| 1626
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-500|RSA500]]
| 500
| 1659
| &nbsp;
| colspan="2" style="text-align:center;"|
|-
| [[RSA numbers#RSA-617|RSA617]]
| 617
| 2048
| &nbsp;
| colspan="2" style="text-align:center;"|
|- style="background:#ffebad;"
| [[RSA numbers#RSA-2048|RSA2048]]
| 617
| 2048
| US$200,000{{efn|name=not-awarded}}
| colspan="2" style="text-align:center;"|
|}

{{notelist}}

==See also==
* [[RSA numbers]], decimal expansions of the numbers and known factorizations
* [[LCS35]]
* [[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==
<references />

{{DEFAULTSORT:Rsa Factoring Challenge}}
[[Category:RSA Factoring Challenge| ]]
[[Category:Integer factorization algorithms]]
[[Category:Cryptography contests]]
[[Category:1991 establishments in the United States]]