RSA Factoring Challenge

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.

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

. . . RSA Factoring Challenge . . .

RSA Laboratories states that: for each RSA number n, there exists prime numbersp and q such that

n = p × q.

The problem is to find these two primes, given only n.

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 numbers expressed in base 10, while the challenge numbers in yellow lines are numbers expressed in base 2
RSA number Decimal digits Binary digits Cash prize offered Factored on Factored by
RSA-100 100 330 US$1,000[8] April 1, 1991[9] Arjen K. Lenstra
RSA-110 110 364 US$4,429[8] April 14, 1992[9] Arjen K. Lenstra and M.S. Manasse
RSA-120 120 397 US$5,898[8] July 9, 1993[10] T. Dennyet al.
RSA-129[lower-alpha 1] 129 426 US$100 April 26, 1994[9] Arjen K. Lenstraet al.
RSA-130 130 430 US$14,527[8] April 10, 1996 Arjen K. Lenstraet al.
RSA-140 140 463 US$17,226 February 2, 1999 Herman te Rieleet al.
RSA-150 150 496   April 16, 2004 Kazumaro Aokiet al.
RSA-155 155 512 US$9,383[8] August 22, 1999 Herman te Rieleet al.
RSA-160 160 530   April 1, 2003 Jens Frankeet al., University of Bonn
RSA-170[lower-alpha 2] 170 563   December 29, 2009 D. Bonenberger and M. Krone [lower-alpha 3]
RSA-576 174 576 US$10,000 December 3, 2003 Jens Frankeet al., University of Bonn
RSA-180[lower-alpha 2] 180 596   May 8, 2010 S. A. Danilov and I. A. Popovyan, Moscow State University[11]
RSA-190[lower-alpha 2] 190 629   November 8, 2010 A. Timofeev and I. A. Popovyan
RSA-640 193 640 US$20,000 November 2, 2005 Jens Frankeet al., University of Bonn
RSA-200[lower-alpha 2] ? 200 663   May 9, 2005 Jens Frankeet al., University of Bonn
RSA-210[lower-alpha 2] 210 696 September 26, 2013[12] Ryan Propper
RSA-704[lower-alpha 2] 212 704 US$30,000 July 2, 2012 Shi Bai, Emmanuel Thomé and Paul Zimmermann
RSA-220[lower-alpha 2] 220 729   May 13, 2016 S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann
RSA-230[lower-alpha 2] 230 762   August 15, 2018 Samuel S. Gross, Noblis, Inc.
RSA-232[lower-alpha 2] 232 768   February 17, 2020[13] N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev.
RSA-768[lower-alpha 2] 232 768 US$50,000 December 12, 2009 Thorsten Kleinjunget al.[14]
RSA-240[lower-alpha 2] 240 795   Dec 2, 2019[15] F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA-250[lower-alpha 2] 250 829   Feb 28, 2020[16] F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann
RSA-260 260 862  
RSA-270 270 895  
RSA-896 270 896 US$75,000[lower-alpha 4]
RSA-280 280 928  
RSA-290 290 962  
RSA-300 300 995  
RSA-309 309 1024  
RSA-1024 309 1024 US$100,000[lower-alpha 4]
RSA-310 310 1028  
RSA-320 320 1061  
RSA-330 330 1094  
RSA-340 340 1128  
RSA-350 350 1161  
RSA-360 360 1194  
RSA-370 370 1227  
RSA-380 380 1261  
RSA-390 390 1294  
RSA-400 400 1327  
RSA-410 410 1360  
RSA-420 420 1393  
RSA-430 430 1427  
RSA-440 440 1460  
RSA-450 450 1493  
RSA-460 460 1526  
RSA-1536 463 1536 US$150,000[lower-alpha 4]
RSA-470 470 1559  
RSA-480 480 1593  
RSA-490 490 1626  
RSA-500 500 1659  
RSA-617 617 2048  
RSA-2048 617 2048 US$200,000[lower-alpha 4]
  1. RSA-129 was not part of the RSA Factoring Challenge, but was related to a column by Martin Gardner in Scientific American.
  2. 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. The challenge ended before this prize was awarded.

. . . RSA Factoring Challenge . . .

This article is issued from web site Wikipedia. The original article may be a bit shortened or modified. Some links may have been modified. The text is licensed under “Creative Commons – Attribution – Sharealike” [1] and some of the text can also be licensed under the terms of the “GNU Free Documentation License” [2]. Additional terms may apply for the media files. By using this site, you agree to our Legal pages . Web links: [1] [2]

. . . RSA Factoring Challenge . . .

© 2022 The Grey Earl INFO - WordPress Theme by WPEnjoy