46.211.105.19 am 3. März 2025 um 01:57 Uhr

2025-03-03T01:57:01Z

Neue Seite

Das '''RSA Factoring Challenge''' war ein von 1991 bis 2007 bestehender Wettbewerb des Unternehmens [[RSA Security]], der die Sicherheit des [[RSA-Kryptosystem]]s aufzeigen sollte. Forscher waren öffentlich dazu aufgerufen, die [[Primfaktorzerlegung]] vorgegebener Zahlen unterschiedlicher Längen (von 330 bis 2048 [[Bit]]s) zu finden. 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 Wettbewerb diente dazu, den [[Forschungsstand]] der [[Faktorisierungsverfahren]] zu verfolgen. Im Jahr 2007 wurde der Wettbewerb abgebrochen; bis dahin wurden über 80.000 USD Preisgeld ausgezahlt. Auch nach dem offiziellen Ende des Wettbewerbs werden die verbliebenen Zahlen von [[Zahlentheorie|Zahlentheoretikern]] zur Weiterentwicklung von Faktorisierungsverfahren verwendet.

== Hintergrund ==
Im Gegensatz zur Erzeugung dieser Zahlen ist das Auffinden der Primfaktoren außerordentlich schwierig. Auf dieser Schwierigkeit beruht die Sicherheit der [[Rabin-Kryptosystem|Rabin-]] und RSA-Kryptosysteme. Wenn jemand die Primfaktorzerlegung einfach berechnen kann, dann gelingt ihm auch die Entschlüsselung der Geheimtexte, die mittels RSA erzeugt wurden. Da es andere Angriffsmethoden (wie Timing-Angriffe) auf RSA gibt, ist jedoch die Sicherheit des RSA-Kryptosystems mit dem Fehlen effizienter Algorithmen zur Faktorisierung nicht beweisbar. Da es sich bei den RSA-Modulen allerdings um schwer zu faktorisierende [[Semiprimzahl]]en handelt (also Zahlen die das Produkt von genau zwei Primzahlen sind), sind diese Zahlen gute Kandidaten, um die Effektivität eines [[Faktorisierungsverfahren]]s zu zeigen.

== Verlauf ==
Die RSA Factoring Challenge wurde am 18. März 1991 in der [[Newsgroup]] sci.crypt ausgerufen. Für eine faktorisierte Zahl wurden anfangs pro Quartal 1000 USD ausgezahlt, wobei nicht beanspruchte Preisgelder auf die später möglichen Gewinne angerechnet wurden. Die Zahlen wurden nach dem Muster ''RSA-xxx'' benannt, wobei ''xxx'' die Anzahl an Dezimalstellen der zu faktorisierenden Zahl angab.<ref>https://groups.google.com/u/1/g/sci.crypt/c/AA7M9qWWx3w/m/EkrsR69CDqIJ</ref>

In den ersten Jahren nach Ausschreibung des Wettbewerbs wurden insbesondere von [[Arjen Lenstra]] einige dieser Zahlen faktorisiert.<ref>{{Internetquelle |url=http://www.ontko.com/pub/rayo/primes/hr_rsa.txt |titel=RSA Honor Roll As of March 5, 1999 |werk=ontko.com |hrsg=Ray Ontko & Company |datum=2002-01-30 |abruf=2022-04-29 |sprache=en}}</ref> Im Jahr 2000 war RSA-155 die größte faktorisierte Zahl. Bis dahin wurden insgesamt 52.463 USD Preisgeld ausgezahlt.<ref>https://www.ontko.com/pub/rayo/primes/rsa_news.txt</ref>

Im Jahr 2001 wurden die Bedingungen des Wettbewerbs angepasst. Es wurden neue Zahlen veröffentlicht, die nach dem Muster ''RSA-yyy'' benannt waren, wobei ''yyy'' die Anzahl an Bits der zu faktorisierenden Zahl angab. Das Preisgeld lag je nach Bitlänge zwischen 10.000 USD für RSA-576 und 200.000 USD für RSA-2048.<ref>https://web.archive.org/web/20010714162913/http://www.rsa.com/rsalabs/challenges/factoring/index.html</ref> Insgesamt ergab sich ein Preispool von 635.000 USD.

In den Jahren 2003 und 2005 hatte eine Gruppe um [[Jens Franke]] von den neuen Zahlen RSA-576 und RSA-640 faktorisiert und damit ein Preisgeld von 10.000 und 20.000 USD erworben. Von den alten Zahlen hatten sie außerdem RSA-160<ref>https://web.archive.org/web/20140129031151/http://www.loria.fr/~zimmerma/records/rsa160</ref><ref>https://web.archive.org/web/20130923062453/http://www.emc.com/emc-plus/rsa-labs/historical/rsa-160-factored.htm</ref> und RSA-200<ref>https://web.archive.org/web/20130923061243/http://www.emc.com/emc-plus/rsa-labs/historical/rsa-200-factored.htm</ref> faktorisiert. Im Jahr 2007 konnte Jens Franke außerdem die 1039. [[Mersenne-Zahl]] faktorisieren; hierbei handelt es sich um eine 1039 Bit lange Zahl, die jedoch kein Teil der RSA Factoring Challenge war.<ref>https://link.springer.com/chapter/10.1007/978-3-540-76900-2_1</ref>

Im Jahr 2007 wurde die RSA Factoring Challenge für beendet erklärt. Als Begründung hieß es, die ursprüngliche Intention des Wettbewerbs – die Messung des Fortschritts der praktischen [[Kryptoanalyse]] – sei mittlerweile ausreichend geklärt. Die Industrie habe zwischenzeitlich ein wesentlich besseres Verständnis der kryptanalytischen Stärke von [[Symmetrisches Kryptosystem|symmetrischen]] und [[Asymmetrisches Kryptosystem|asymmetrischen Kryptoverfahren]] erlangt.<ref>https://web.archive.org/web/20130921043454/http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm</ref>

== Ergebnisse ==

=== RSA-576 ===
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 ===
Die Faktoren dieser 193-stelligen Zahl wurden im November 2005 von F. Bahr, M. Boehm, J. Franke und 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 ===
Die Faktorisierung dieser 232-stelligen Zahl wurde am 12. Dezember 2009 von Thorsten Kleinjung u. a. vollendet.<ref>{{Internetquelle |url=https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt |titel=Bekanntmachung der Faktorisierung von RSA-768 |werk=documents.epfl.ch |hrsg=Ecole polytechnique fédérale de Lausanne |abruf=2022-04-29 |sprache=en}}</ref> Der RSA Factoring Challenge war zu dieser Zeit schon beendet, sodass kein Preisgeld ausgezahlt wurde.

RSA-768 = 123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 ×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

== Weblinks ==
* {{Webarchiv |url=http://www.rsa.com/rsalabs/node.asp?id=2092 |wayback=20130507091636 |text=''Website der RSA Factoring Challenge.''}}.
* [http://groups.google.com/group/sci.crypt/msg/a20e42af47ec4a12 ''Ursprüngliche Bekanntmachung auf sci.crypt.'']
* {{Webarchiv |url=http://www.crypto-world.com/announcements/m1039.txt |wayback=20100115001259 |text=''Bekanntmachung zur Faktorisierung der 1039. Mersennezahl.''}}.
* [http://eprint.iacr.org/2010/006 Forschungsbericht ''Factorization of a 768-bit RSA modulus.'']

== Einzelnachweise ==
<references />

{{SORTIERUNG:Rsa Factoring Challenge}}

[[Kategorie:Mathematikwettbewerb]]
[[Kategorie:Geschichte der Kryptologie]]
[[Kategorie:Verteiltes Rechnen]]
[[Kategorie:Erstveranstaltung 1991]]
[[Kategorie:Veranstaltung in den Vereinigten Staaten]]
[[Kategorie:Letzte Veranstaltung 2007]]
[[Kategorie:Informatikwettbewerb]]

RSA Factoring Challenge - Versionsgeschichte

46.211.105.19 am 3. März 2025 um 01:57 Uhr