RSA Factoring Challenge

From Wikipedia, the free 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 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 in a few days, but many of the bigger numbers have still not been factored and are expected to remain so for quite some time.

The RSA challenges ended in 2007.^[1] 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."^[2]

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 is used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength.

The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits; later, however, beginning with RSA-576, binary digits are counted instead. An exception to this is RSA-617, which was created prior to the change in the numbering scheme.

Contents 1 The mathematics 2 The prizes and records 3 See also 4 Notes 5 External links

[edit] The mathematics

Let n be an RSA Number. RSA Laboratories states there are prime numbers p and q such that

n = p × q.

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

[edit] 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		April 1991	Arjen K. Lenstra
RSA-110	110	364		April 1992	Arjen K. Lenstra and M.S. Manasse
RSA-120	120	397		June 1993	T. Denny et al.
RSA-129	129	426	$100 USD	April 1994	Arjen K. Lenstra et al.
RSA-130	130	430		April 10, 1996	Arjen K. Lenstra et al.
RSA-140	140	463		February 2, 1999	Herman J. J. te Riele et al.
RSA-150[3]	150	496		April 16, 2004	Kazumaro Aoki et al.
RSA-155	155	512		August 22, 1999	Herman J. J. te Riele et al.
RSA-160	160	530		April 1, 2003	Jens Franke et al., University of Bonn
RSA-170	170	563		inactive
RSA-576	174	576	$10,000 USD	December 3, 2003	Jens Franke et al., University of Bonn
RSA-180	180	596		inactive
RSA-190	190	629		inactive
RSA-640	193	640	$20,000 USD	November 2, 2005	Jens Franke et al., University of Bonn
RSA-200	200	663		May 9, 2005	Jens Franke et al., University of Bonn
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	inactive, 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

[edit] See also

• RSA numbers, decimal expansions of the numbers and known factorizations
• 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

[edit] Notes

1. ^ RSA Laboratories, The RSA Factoring Challenge. Retrieved on 2007-05-18.
2. ^ RSA Laboratories, The RSA Factoring Challenge FAQ. Retrieved on 2007-05-30.
3. ^ RSA-150 was withdrawn from the original challenge by RSA Security, but was factored anyway.

[edit] External links

• RSA Security: The RSA factoring challenge
• MathWorld: RSA Number
• Mathematica package for RSA numbers
• The original challenge announcement on sci.crypt
• Certicom ECC Challenge