RSA Factoring Challenge

The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991{{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}} 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.{{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}}{{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 }}{{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 }}

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

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.

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 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
RSA100 \| 100 \| 330 \| US$1,000{{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}} \| April 1, 1991[http://www.ontko.com/~rayo/primes/hr_rsa.txt RSA Honor Roll] \| Arjen K. Lenstra
RSA110 \| 110 \| 364 \| US$4,429 \| April 14, 1992 \| Arjen K. Lenstra and M.S. Manasse
RSA120 \| 120 \| 397 \| US$5,898 \| July 9, 1993{{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}} \| T. Denny et al.
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 \| Arjen K. Lenstra et al.
RSA130 \| 130 \| 430 \| US$14,527 \| 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 \| August 22, 1999 \| Herman te Riele et al.
RSA160 \| 160 \| 530 \| \| April 1, 2003 \| Jens Franke et al., University of Bonn
RSA170{{efn\|The number was factored after the challenge ended.\|name=retracted}} \| 170 \| 563 \| \| 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.}}
style="background:#ffebad;" \| RSA576 \| 174 \| 576 \| US$10,000 \| December 3, 2003 \| Jens Franke et al., University of Bonn
RSA180{{efn\|name=retracted}} \| 180 \| 596 \| \| May 8, 2010 \| S. A. Danilov and I. A. Popovyan, Moscow State University{{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}}
RSA190{{efn\|name=retracted}} \| 190 \| 629 \| \| November 8, 2010 \| A. Timofeev and I. A. Popovyan
style="background:#ffebad;" \| RSA640 \| 193 \| 640 \| US$20,000 \| November 2, 2005 \| Jens Franke et al., University of Bonn
RSA200{{efn\|name=retracted}} ^? \| 200 \| 663 \| \| May 9, 2005 \| Jens Franke et al., University of Bonn
RSA210{{efn\|name=retracted}} \| 210 \| 696 \| \| September 26, 2013[http://www.mersenneforum.org/showpost.php?p=354259 RSA-210 factored], mersenneforum.org \| Ryan Propper
style="background:#ffebad;" \| RSA704{{efn\|name=retracted}} \| 212 \| 704 \| US$30,000 \| July 2, 2012	Shi Bai, Emmanuel Thomé and Paul Zimmermann
RSA220{{efn\|name=retracted}} \| 220 \| 729 \| \| May 13, 2016 \| S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann
RSA230{{efn\|name=retracted}} \| 230 \| 762 \| \| August 15, 2018 \| Samuel S. Gross, Noblis, Inc.
RSA232{{efn\|name=retracted}} \| 232 \| 768 \| \| February 17, 2020[https://www.inm.ras.ru/math_center_en/rsa-232-number-has-been-factored-5/ INM RAS news] \| N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev.
style="background:#ffebad;" \| RSA768{{efn\|name=retracted}} \| 232 \| 768 \| US$50,000 \| December 12, 2009 \| Thorsten Kleinjung et al.{{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}}
RSA240{{efn\|name=retracted}} \| 240 \| 795 \| \| Dec 2, 2019{{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}} \| F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA250{{efn\|name=retracted}} \| 250 \| 829 \| \| Feb 28, 2020{{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}} \| F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA260 \| 260 \| 862 \| \| colspan="2" style="text-align:center;"\|
RSA270 \| 270 \| 895 \| \| colspan="2" style="text-align:center;"\|
style="background:#ffebad;" \| RSA896 \| 270 \| 896 \| US$75,000{{efn\|The challenge ended before this prize was awarded.\|name=not-awarded}} \| colspan="2" style="text-align:center;"\|
RSA280 \| 280 \| 928 \| \| colspan="2" style="text-align:center;"\|
RSA290 \| 290 \| 962 \| \| colspan="2" style="text-align:center;"\|
RSA300 \| 300 \| 995 \| \| colspan="2" style="text-align:center;"\|
RSA309 \| 309 \| 1024 \| \| colspan="2" style="text-align:center;"\|
style="background:#ffebad;" \| RSA1024 \| 309 \| 1024 \| US$100,000{{efn\|name=not-awarded}} \| colspan="2" style="text-align:center;"\|
RSA310 \| 310 \| 1028 \| \| colspan="2" style="text-align:center;"\|
RSA320 \| 320 \| 1061 \| \| colspan="2" style="text-align:center;"\|
RSA330 \| 330 \| 1094 \| \| colspan="2" style="text-align:center;"\|
RSA340 \| 340 \| 1128 \| \| colspan="2" style="text-align:center;"\|
RSA350 \| 350 \| 1161 \| \| colspan="2" style="text-align:center;"\|
RSA360 \| 360 \| 1194 \| \| colspan="2" style="text-align:center;"\|
RSA370 \| 370 \| 1227 \| \| colspan="2" style="text-align:center;"\|
RSA380 \| 380 \| 1261 \| \| colspan="2" style="text-align:center;"\|
RSA390 \| 390 \| 1294 \| \| colspan="2" style="text-align:center;"\|
RSA400 \| 400 \| 1327 \| \| colspan="2" style="text-align:center;"\|
RSA410 \| 410 \| 1360 \| \| colspan="2" style="text-align:center;"\|
RSA420 \| 420 \| 1393 \| \| colspan="2" style="text-align:center;"\|
RSA430 \| 430 \| 1427 \| \| colspan="2" style="text-align:center;"\|
RSA440 \| 440 \| 1460 \| \| colspan="2" style="text-align:center;"\|
RSA450 \| 450 \| 1493 \| \| colspan="2" style="text-align:center;"\|
RSA460 \| 460 \| 1526 \| \| colspan="2" style="text-align:center;"\|
style="background:#ffebad;" \| RSA1536 \| 463 \| 1536 \| US$150,000{{efn\|name=not-awarded}} \| colspan="2" style="text-align:center;"\|
RSA470 \| 470 \| 1559 \| \| colspan="2" style="text-align:center;"\|
RSA480 \| 480 \| 1593 \| \| colspan="2" style="text-align:center;"\|
RSA490 \| 490 \| 1626 \| \| colspan="2" style="text-align:center;"\|
RSA500 \| 500 \| 1659 \| \| colspan="2" style="text-align:center;"\|
RSA617 \| 617 \| 2048 \| \| colspan="2" style="text-align:center;"\|
style="background:#ffebad;" \| RSA2048 \| 617 \| 2048 \| US$200,000{{efn\|name=not-awarded}} \| colspan="2" style="text-align:center;"\|

class="wikitable"

RSA number

! Decimal digits

! Binary digits

! Cash prize offered

! Factored on

! Factored by

RSA100

| 100

| 330

| US$1,000{{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}}

| April 1, 1991[http://www.ontko.com/~rayo/primes/hr_rsa.txt RSA Honor Roll]

| Arjen K. Lenstra

RSA110

| 110

| 364

| US$4,429

| April 14, 1992

| Arjen K. Lenstra and M.S. Manasse

RSA120

| 120

| 397

| US$5,898

| July 9, 1993{{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}}

| T. Denny et al.

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

| Arjen K. Lenstra et al.

RSA130

| 130

| 430

| US$14,527

| 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

| August 22, 1999

| Herman te Riele et al.

RSA160

| 160

| 530

| April 1, 2003

| Jens Franke et al., University of Bonn

RSA170{{efn|The number was factored after the challenge ended.|name=retracted}}

| 170

| 563

| 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.}}

style="background:#ffebad;"

| RSA576

| 174

| 576

| US$10,000

| December 3, 2003

| Jens Franke et al., University of Bonn

RSA180{{efn|name=retracted}}

| 180

| 596

| May 8, 2010

| S. A. Danilov and I. A. Popovyan, Moscow State University{{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}}

RSA190{{efn|name=retracted}}

| 190

| 629

| November 8, 2010

| A. Timofeev and I. A. Popovyan

style="background:#ffebad;"

| RSA640

| 193

| 640

| US$20,000

| November 2, 2005

| Jens Franke et al., University of Bonn

RSA200{{efn|name=retracted}} ^?

| 200

| 663

| May 9, 2005

| Jens Franke et al., University of Bonn

RSA210{{efn|name=retracted}}

| 210

| 696

| September 26, 2013[http://www.mersenneforum.org/showpost.php?p=354259 RSA-210 factored], mersenneforum.org

| Ryan Propper

style="background:#ffebad;"

| RSA704{{efn|name=retracted}}

| 212

| 704

| US$30,000

| July 2, 2012

Shi Bai, Emmanuel Thomé and Paul Zimmermann

RSA220{{efn|name=retracted}}

| 220

| 729

| May 13, 2016

| S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann

RSA230{{efn|name=retracted}}

| 230

| 762

| August 15, 2018

| Samuel S. Gross, Noblis, Inc.

RSA232{{efn|name=retracted}}

| 232

| 768

| February 17, 2020[https://www.inm.ras.ru/math_center_en/rsa-232-number-has-been-factored-5/ INM RAS news]

| N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev.

style="background:#ffebad;"

| RSA768{{efn|name=retracted}}

| 232

| 768

| US$50,000

| December 12, 2009

| Thorsten Kleinjung et al.{{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}}

RSA240{{efn|name=retracted}}

| 240

| 795

| Dec 2, 2019{{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}}

| F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann

RSA250{{efn|name=retracted}}

| 250

| 829

| Feb 28, 2020{{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}}

| F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann

RSA260

| 260

| 862

| colspan="2" style="text-align:center;"|

RSA270

| 270

| 895

| colspan="2" style="text-align:center;"|

style="background:#ffebad;"

| RSA896

| 270