Editing RSA Factoring Challenge (section)

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