RSA Factoring Challenge

The RSA Factoring Challenge was on 18 March 1991 exclaimed by the company RSA Security competition, which should show the security of the RSA cryptosystem.

In particular, mathematicians and computer scientists were invited ( 330-2048 bit) to find the prime factorization of given numbers of different lengths. In contrast to the production of these figures, finding the prime factors is extremely difficult. On this difficulty, the security of the RSA cryptosystem is based. Can someone simply calculate the prime factorization, then he can also decrypt ciphertexts generated using RSA. Since there are other methods of attack (such as timing attacks ) on RSA, but the security of the RSA cryptosystem is not provable with the lack of efficient algorithms for factoring. Since, however, is difficult to be factored semi primes in the RSA modules ( ie numbers which is the product of exactly two primes ), these numbers are good candidates to show the effectiveness of Faktorisierungsverfahrens are.

The various figures were doped depending on the difficulty with different prices; the longest number, referred to as RSA -2048, with U.S. $ 200,000. The total value of the prizes amounted to $ 635,100.

Course

In the first years after announcement of the competition, in particular by Hendrik Lenstra some of these figures have been factored, but the 530 -bit limit was not exceeded until 2003.

RSA 576

The prime factorization of the 174- digit number was found in December 2003 by Jens Franke and Thorsten Kleinjung from the Mathematical Institute in Bonn and the Institute for Experimental Mathematics in Essen. The prize money was $ 10,000 U.S..

RSA -576 = 1881988129206079638386972394616504398071635633794173827007633564229888597152346654853190606065047430            45317388011303396716199692321205734031879550656996221305168759307650257059 RSA -576 = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317 *            472772146107435302536223071973048224632914695302097116459852171130520711256363590397527 RSA 640

The factors of this 193- digit number was found in November 2005 by F. Bahr, M. Boehm, J. Franke, T. Klein Jung, who had previously been factored RSA 200. The prize money was $ 20,000 U.S..

RSA -640 = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286            782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609 RSA -640 = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579 *            1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571 RSA 768

The factorization of the 232 - digit number was on December 12, 2009 by Thorsten Klein Jung et al. completed. The RSA Factoring Challenge was completed at this time, so no prize money was paid.

RSA -768 = 123018668453011775513049495838496272077285356959533479219732245215172640050726            365751874520219978646938995647494277406384592519255732630345373154826850791702            6122142913461670429214311602221240479274737794080665351419597459856902143413 RSA -768 = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 *            36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917 end

In May 2007, the team led by Jens Franke and Thorsten Kleinjung from Bonn could specify the factorization of the 1039th Mersenne number and had thus a 1039- bit number factored, which, however, was not among the doped by RSA Security numbers.

Immediately thereafter, the RSA Factoring Challenge was declared over. The reason it is called, the original intention of the competition - the presentation of the security of RSA - is now sufficiently clarified.

Overall, RSA Security has paid out prizes worth 30,100 U.S. dollars as part of this competition.