RSA Factoring Challenge

Template:Short description The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991<ref>Template:Cite news</ref> 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.

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>Template:Cite news</ref><ref name="rsa-challenge-2001">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref name="rsa-numbers-2001">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

The RSA Factoring Challenges ended in 2007.<ref name="rsa-factoring-challenge">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> 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."<ref name="rsa-factoring-challenge-faq">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> When the challenge ended in 2007, only RSA-576 and RSA-640 had been factored from the 2001 challenge numbers.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</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 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.<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 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<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

RSA number	Decimal digits	Binary digits	Cash prize offered	Factored on	Factored by
RSA100	100	330	citation	CitationClass=web }}</ref>	April 1, 1991<ref name="honor-roll">RSA Honor Roll</ref>	Arjen K. Lenstra
RSA110	110	364	US$4,429<ref name="rsa-news" />	April 14, 1992<ref name="honor-roll" />	Arjen K. Lenstra and M.S. Manasse
RSA120	120	397	US$5,898<ref name="rsa-news" />	July 9, 1993<ref>Template:Cite conference</ref>	T. Denny et al.
RSA129Template:Efn	129	426	US$100	April 26, 1994<ref name="honor-roll" />	Arjen K. Lenstra et al.
RSA130	130	430	US$14,527<ref name="rsa-news" />	April 10, 1996	Arjen K. Lenstra et al.
RSA140	140	463	US$17,226	February 2, 1999	Herman te Riele et al.
RSA150	150	496		April 16, 2004	Kazumaro Aoki et al.
RSA155	155	512	US$9,383<ref name="rsa-news" />	August 22, 1999	Herman te Riele et al.
RSA160	160	530		April 1, 2003	Jens Franke et al., University of Bonn
RSA170Template:Efn	170	563		December 29, 2009	D. Bonenberger and M. KroneTemplate:Efn
RSA576	174	576	US$10,000	December 3, 2003	Jens Franke et al., University of Bonn
RSA180Template:Efn	180	596		May 8, 2010	S. A. Danilov and I. A. Popovyan, Moscow State University<ref name="rsa-180">Template:Cite journal</ref>
RSA190Template:Efn	190	629		November 8, 2010	A. Timofeev and I. A. Popovyan
RSA640	193	640	US$20,000	November 2, 2005	Jens Franke et al., University of Bonn
RSA200Template:Efn ?	200	663		May 9, 2005	Jens Franke et al., University of Bonn
RSA210Template:Efn	210	696		September 26, 2013<ref>RSA-210 factored, mersenneforum.org</ref>	Ryan Propper
RSA704Template:Efn	212	704	US$30,000	July 2, 2012	Shi Bai, Emmanuel Thomé and Paul Zimmermann
RSA220Template:Efn	220	729		May 13, 2016	S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann
RSA230Template:Efn	230	762		August 15, 2018	Samuel S. Gross, Noblis, Inc.
RSA232Template:Efn	232	768		February 17, 2020<ref>INM RAS news</ref>	N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev.
RSA768Template:Efn	232	768	US$50,000	December 12, 2009	Thorsten Kleinjung et al.<ref name="rsa-768-paper">Template:Cite conference</ref>
RSA240Template:Efn	240	795		Dec 2, 2019<ref>Template:Cite mailing list</ref>	F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA250Template:Efn	250	829		Feb 28, 2020<ref>Template:Cite mailing list</ref>	F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA260	260	862
RSA270	270	895
RSA896	270	896	US$75,000Template:Efn
RSA280	280	928
RSA290	290	962
RSA300	300	995
RSA309	309	1024
RSA1024	309	1024	US$100,000Template:Efn
RSA310	310	1028
RSA320	320	1061
RSA330	330	1094
RSA340	340	1128
RSA350	350	1161
RSA360	360	1194
RSA370	370	1227
RSA380	380	1261
RSA390	390	1294
RSA400	400	1327
RSA410	410	1360
RSA420	420	1393
RSA430	430	1427
RSA440	440	1460
RSA450	450	1493
RSA460	460	1526
RSA1536	463	1536	US$150,000Template:Efn
RSA470	470	1559
RSA480	480	1593
RSA490	490	1626
RSA500	500	1659
RSA617	617	2048
RSA2048	617	2048	US$200,000Template:Efn

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 />