Zahlenknacker melden Rekordzerlegung in Primfaktoren

Schon seit Jahren ist es Sport der Mathematiker um Professor Dr. Jens Franke und Dr. Thorsten Kleinjung an der Rheinischen Friedrich-Wilhelm-Universität zu Bonn immer größere Zahlen in Primfaktoren zu zerlegen. Solche großen zusammengesetzten Zahlen, insbesondere die RSA-Zahlen (nach Rivest, Shamir, Adelman) werden für Verschlüsselungsverfahren eingesetzt, und die Firma RSA Laboratories hatte eine Challenge-Liste veröffentlicht, verbunden mit einem – je nach Größe – wachsenden Preisgeld von 10.000 bis 200.000 US-Dollar. Die Bonner waren bei der Rekord-Jagd mehrmals erfolgreich und zerlegten im Dezember 2003 den RSA-576 und im November 2005 RSA-640.

Nun hat sich das japanische Telekommunikationsunternehmen NTT zusammen mit den Bonnern und ihrem Kollegen von der Polytechnischen Hochschule in Lausanne, Arjen Lenstra (übrigens ein Bruder des ebenfalls sehr bekannten Zahlentheoretikers Hendrik Lenstra), an die Aufgabe gemacht, die Mersenne-Zahl 2¹⁰³⁹–1 genauer zu untersuchen. Die entlarvt sich, wie man spätestens auf den zweiten Blick sieht, als zusammengesetzt, mit 5080711 als einfachem Teiler. Aber über den 307-stelligen Koteiler (siehe unten) wusste man bislang noch nichts. Elf Monate ackerten die Rechner (überwiegend in Japan), bis jetzt eine Zerlegung in zwei 80- und 227-stellige Primzahlen gefunden wurde. Die von Ajren Lenstra und den Bonner Mathematikern entwickelte Methode GNFS (General Number Field Sieve) arbeitete dabei in vier Schritten:

• Kandidatensuche (Rechenzeit: 125,7 Opteron-248-Jahre),
• Siebberechnung (Rechenzeit 95 Pentium-D-Jahre),
• Lineare Algebra (zwei Cluster des NTT mit 146 PCs rechneten zwei Monate)
• Wurzelziehen (wenige Stunden auf dem PC-Cluster der Uni Bonn)

Mit 1017 Binärstellen ist der zerlegte Koteiler nahezu genauso groß wie die noch zur Fahndung ausgeschriebene RSA-1024-Zahl. 1024 Bit ist die derzeit übliche Schlüssellänge.

Als Teiler einer Mersenne-Zahl hat der Koteiler jedoch eine bestimmte Struktur, die das Aufspüren weiterer Faktoren vereinfacht. Für zufällige Zahlen, so betont Kleinjung, schafft man es mit ihrer Methode vielleicht, Schlüssel mit 700 Binärstellen in mehreren Monaten zu knacken. Hier steht also als Herausforderung RSA-704 an. Bis man RSA-1024 wirklich knacken kann, wird es nach Kleinjungs Meinung noch viele Jahre dauern.

Allerdings wird es jetzt kein Preisgeld mehr geben, die Auslobung der RSA Laboratories ist inzwischen ausgelaufen. Wer dennoch ein bisschen experimentieren will, hier die von NTT, Kleinjung, Lenstra und Co zerlegte 307-stellige Zahl:

115942057407257306436980714887689464075389979170201772498686835353882248385
996675660800060954080051794720539932612302048744028604353028619141014409345
351233471273967988850226307575280937916602855510550042581077117617761009413
797078797380618700843777718682868088984471282200293520180607475545154137071
1023817

und die Lösung:

5585366661993629126074920465831594496864
6527018488637648010052346319853288374753
×
2075818194644238276457048137035946951629
3970800739520988120838703792729090324679
3823431438841448348825340533447691122230
2815832769652537609141018910524199389933
4109711624358962065972167481161749004803
659735573409253205425523689


(as)