RSA Factoring Challenge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das RSA Factoring Challenge war ein am 18. März 1991 von der Firma RSA Security ausgerufener Wettbewerb, welcher die Sicherheit des RSA-Kryptosystems aufzeigen sollte.

Insbesondere Mathematiker und Informatiker wurden aufgefordert, die Primfaktorzerlegung von vorgegebenen Zahlen verschiedener Länge (von 330 bis 2048 Bit) zu finden. Im Gegensatz zur Erzeugung dieser Zahlen ist das Auffinden der Primfaktoren außerordentlich schwierig. Auf dieser Schwierigkeit beruht die Sicherheit des RSA-Kryptosystems. Kann jemand die Primfaktorzerlegung einfach berechnen, dann kann er auch Geheimtexte entschlüsseln, die mittels RSA erzeugt wurden. Da es andere Angriffsmethoden (wie Timing-Angriffe) auf RSA gibt, ist die Sicherheit des RSA-Kryptosystems jedoch mit dem Fehlen von effizienten Algorithmen zur Faktorisierung nicht beweisbar. Da es sich bei den RSA-Modulen allerdings um schwer zu faktorisierende Semiprimzahlen handelt (also Zahlen die das Produkt von genau zwei Primzahlen sind), sind diese Zahlen gute Kandidaten, um die Effektivität eines Faktorisierungsverfahrens zu zeigen.

Die verschiedenen Zahlen wurden je nach Schwierigkeit mit unterschiedlich hohen Preisen dotiert; die längste Zahl, bezeichnet als RSA-2048, mit 200.000 US-Dollar. Der Gesamtwert der Preise betrug 635.100 USD.

Verlauf[Bearbeiten]

In den ersten Jahren nach Ausschreibung des Wettbewerbs wurden insbesondere von Hendrik Lenstra einige dieser Zahlen faktorisiert, jedoch wurde die 530-Bit-Grenze bis zum Jahr 2003 nicht überschritten.

RSA 576[Bearbeiten]

Die Primfaktorzerlegung dieser 174-stelligen Zahl wurde im Dezember 2003 von Jens Franke und Thorsten Kleinjung vom Mathematischen Institut in Bonn und dem Institut für Experimentelle Mathematik in Essen gefunden. Das Preisgeld lag bei 10.000 US$.

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

RSA 640[Bearbeiten]

Die Faktoren dieser 193-stelligen Zahl wurden im November 2005 von F. Bahr, M. Boehm, J. Franke, T. Kleinjung gefunden, die zuvor schon RSA 200 faktorisiert hatten. Das Preisgeld lag bei 20.000 US$.

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

RSA 768[Bearbeiten]

Die Faktorisierung dieser 232-stelligen Zahl wurde am 12. Dezember 2009 von Thorsten Kleinjung et al. vollendet.[1] Der RSA Factoring Challenge war zu dieser Zeit schon beendet, sodass kein Preisgeld ausgezahlt wurde.

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

Ende[Bearbeiten]

Im Mai 2007 konnte das Team um Jens Franke und Thorsten Kleinjung aus Bonn die Faktorisierung der 1039. Mersenne-Zahl angeben und hatte damit eine 1039-Bit-Zahl faktorisiert, die allerdings nicht zu den von RSA Security dotierten Zahlen gehörte.

Unmittelbar darauf wurde das RSA Factoring Challenge als beendet erklärt. Als Begründung heißt es, die ursprüngliche Intention des Wettbewerbs – die Darlegung der Sicherheit von RSA – sei mittlerweile ausreichend geklärt.

Insgesamt hat RSA Security im Rahmen dieses Wettbewerbes Preise im Wert von 30.100 US-Dollar ausbezahlt.

Einzelnachweise[Bearbeiten]

  1. Bekanntmachung zur Faktorisierung RSA-768 (in English), [1]

Weblinks[Bearbeiten]