RSA factoring challenge

from Wikipedia, the free encyclopedia

The RSA Factoring Challenge was a competition called on March 18, 1991 by the company RSA Security , which was supposed to demonstrate the security of the RSA cryptosystem .

Mathematicians and computer scientists in particular were asked to find the prime factorization of given numbers of various lengths (from 330 to 2048 bits ). In contrast to generating these numbers, finding the prime factors is extremely difficult. The security of the Rabin cryptosystem and the RSA cryptosystem is based on this difficulty . If someone can simply calculate the prime factorization, then he can also decipher ciphertexts that were generated using RSA. Since there are other attack methods (such as timing attacks) on RSA, the security of the RSA cryptosystem cannot be proven with the lack of efficient algorithms for factorization. However, since the RSA modules are semi- prime numbers that are difficult to factorize (i.e. numbers that are the product of exactly two prime numbers), these numbers are good candidates for demonstrating the effectiveness of a factorization method .

The different numbers were endowed with different high prices depending on the difficulty; the longest number called RSA 2048, with 200,000 US dollars . The total value of the prizes was $ 635,100.

course

In the first few years after the competition was announced, some of these numbers were factored by Arjen Lenstra in particular , but the 530-bit limit was not exceeded until 2003.

RSA-576

The prime factorization of this 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 US $ 10,000. 

RSA-576 = 1881988129206079638386972394616504398071635633794173827007633564229888597152346654853190606065047430
          45317388011303396716199692321205734031879550656996221305168759307650257059

RSA-576 = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317 *
          472772146107435302536223071973048224632914695302097116459852171130520711256363590397527

RSA-640

The factors of this 193-digit number were found in November 2005 by F. Bahr, M. Boehm, J. Franke, T. Kleinjung, who had already factored RSA 200 before. The prize money was US $ 20,000. 

RSA-640 = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286
          782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609

RSA-640 = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579 *
          1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571

RSA-768

The factorization of this 232-digit number was carried out on December 12, 2009 by Thorsten Kleinjung et al. accomplished. The RSA Factoring Challenge was already over at this time, so no prize money was paid out. 

RSA-768 = 123018668453011775513049495838496272077285356959533479219732245215172640050726
          365751874520219978646938995647494277406384592519255732630345373154826850791702
          6122142913461670429214311602221240479274737794080665351419597459856902143413

RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 *
          36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

The End

In May 2007, Jens Franke and Thorsten Kleinjung's team from Bonn was able to specify the factorization of the 1039th Mersenne number and thus factored a 1039-bit number, which, however, was not one of the numbers endowed by RSA Security .

Immediately afterwards, the RSA Factoring Challenge was declared over. The reason given is that the original intention of the competition - the presentation of the security of RSA - has meanwhile been sufficiently clarified.

In total, RSA Security paid out prizes worth US $ 30,100 as part of this competition.

Web links

Individual evidence

  1. ↑ From challenge-administrator@majordomo.rsasecurity.com. January 30, 2002, accessed May 17, 2019 .
  2. ↑ Announcement on factorization RSA-768 (in English)