RSA Factoring Challenge
Encyclopedia
The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory
and the practical difficulty of factoring
large integer
s and cracking 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, but many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time.
The RSA challenges ended in 2007. 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."
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 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 — 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.
s p and q such that
The problem is to find these two primes, given only n.
Computational number theory
In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...
and the practical difficulty of factoring
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
large integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s and cracking RSA keys used in cryptography. They published a list of semiprime
Semiprime
In mathematics, a semiprime is a natural number that is the product of two prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... ....
s (numbers with exactly two prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s) known as the RSA numbers
RSA numbers
In mathematics, the RSA numbers are a set of large semiprimes that are part of the RSA Factoring Challenge. The challenge was to find the prime factors but it was declared inactive in 2007...
, 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, but many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time.
The RSA challenges ended in 2007. 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."
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 size
Key size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...
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 — 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
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
digits; the other RSA numbers (beginning with RSA-576) were generated later and labelled according to their number of binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
digits.
The mathematics
RSA Laboratories states that: for each RSA number n, there exist prime numberPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
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.- The challenge numbers in pink lines are numbers expressed in base 10, while the challenge numbers in yellow lines are numbers expressed in base 2. The prizes for RSA-576 and RSA-640 have been awarded. The remaining prizes have been retracted since the challenge became inactive in 2007.
RSA Number Decimal digits Binary digits Cash prize offered Factored on Factored by RSA-100 100 330 $1,000 USD April 1, 1991 Arjen K. Lenstra RSA-110 110 364 $4,429 USD April 14, 1992 Arjen K. Lenstra and M.S. Manasse RSA-120 120 397 $5,898 July 9, 1993 T. Denny et al. RSA-129 129 426 $100 USD April 26, 1994 Arjen K. Lenstra et al. RSA-130 130 430 $14,527 USD April 10, 1996 Arjen K. Lenstra et al. RSA-140 140 463 $17,226 USD February 2, 1999 Herman te Riele et al. RSA-150 150 496 April 16, 2004 Kazumaro Aoki et al. RSA-155 155 512 $9,383 August 22, 1999 Herman te Riele et al. RSA-160 160 530 April 1, 2003 Jens Franke Jens FrankeJens Franke is a German mathematician. He holds a chair at the University of Bonn's Hausdorff Center for Mathematics since 1992. Franke's research has covered various problems of number theory, algebraic geometry and analysis on locally symmetric spaces.Franke attended the University of Jena,...
et al., University of BonnUniversity of BonnThe University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...RSA-170 170 563 December 29, 2009 D. Bonenberger and M. Krone RSA-576 174 576 $10,000 USD December 3, 2003 Jens Franke Jens FrankeJens Franke is a German mathematician. He holds a chair at the University of Bonn's Hausdorff Center for Mathematics since 1992. Franke's research has covered various problems of number theory, algebraic geometry and analysis on locally symmetric spaces.Franke attended the University of Jena,...
et al., University of BonnUniversity of BonnThe University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...RSA-180 180 596 May 8, 2010 S. A. Danilov and I. A. Popovyan, Moscow State University Moscow State UniversityLomonosov Moscow State University , previously known as Lomonosov University or MSU , is the largest university in Russia. Founded in 1755, it also claims to be one of the oldest university in Russia and to have the tallest educational building in the world. Its current rector is Viktor Sadovnichiy...RSA-190 190 629 November 8, 2010 A. Timofeev and I. A. Popovyan RSA-640 193 640 $20,000 USD November 2, 2005 Jens Franke Jens FrankeJens Franke is a German mathematician. He holds a chair at the University of Bonn's Hausdorff Center for Mathematics since 1992. Franke's research has covered various problems of number theory, algebraic geometry and analysis on locally symmetric spaces.Franke attended the University of Jena,...
et al., University of BonnUniversity of BonnThe University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...RSA-200 200 663 May 9, 2005 Jens Franke Jens FrankeJens Franke is a German mathematician. He holds a chair at the University of Bonn's Hausdorff Center for Mathematics since 1992. Franke's research has covered various problems of number theory, algebraic geometry and analysis on locally symmetric spaces.Franke attended the University of Jena,...
et al., University of BonnUniversity of BonnThe University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...RSA-210 210 696 inactive RSA-704 212 704 $30,000 USD inactive, prize retracted RSA-220 220 729 inactive RSA-230 230 762 inactive RSA-232 232 768 inactive RSA-768 232 768 $50,000 USD December 12, 2009 Thorsten Kleinjung et al. (prize retracted) RSA-240 240 795 inactive RSA-250 250 829 inactive RSA-260 260 862 inactive RSA-270 270 895 inactive RSA-896 270 896 $75,000 USD inactive, prize retracted RSA-280 280 928 inactive RSA-290 290 962 inactive RSA-300 300 995 inactive RSA-309 309 1024 inactive RSA-1024 309 1024 $100,000 USD inactive, prize retracted RSA-310 310 1028 inactive RSA-320 320 1061 inactive RSA-330 330 1094 inactive RSA-340 340 1128 inactive RSA-350 350 1161 inactive RSA-360 360 1194 inactive RSA-370 370 1227 inactive RSA-380 380 1261 inactive RSA-390 390 1294 inactive RSA-400 400 1327 inactive RSA-410 410 1360 inactive RSA-420 420 1393 inactive RSA-430 430 1427 inactive RSA-440 440 1460 inactive RSA-450 450 1493 inactive RSA-460 460 1526 inactive RSA-1536 463 1536 $150,000 USD inactive, prize retracted RSA-470 470 1559 inactive RSA-480 480 1593 inactive RSA-490 490 1626 inactive RSA-500 500 1659 inactive RSA-617 617 2048 inactive RSA-2048 617 2048 $200,000 USD inactive, prize retracted
See also
- RSA numbersRSA numbersIn mathematics, the RSA numbers are a set of large semiprimes that are part of the RSA Factoring Challenge. The challenge was to find the prime factors but it was declared inactive in 2007...
, decimal expansions of the numbers and known factorizations - The Magic Words are Squeamish OssifrageThe Magic Words are Squeamish OssifrageThe text "The Magic Words are Squeamish Ossifrage" was the solution to a challenge ciphertext posed by the inventors of the RSA cipher in 1977. The problem appeared in Martin Gardner's Mathematical Games column in Scientific American. It was solved in 1993–1994 by a large joint computer...
, the solution found in 1993 to another RSA challenge posed in 1977 - RSA Secret-Key ChallengeRSA Secret-Key ChallengeThe RSA Secret-Key Challenge consisted of a series of cryptographic contests organised by RSA Laboratories with the intent of helping to demonstrate the relative security of different encryption algorithms...
- Integer factorization recordsInteger factorization recordsInteger factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography...