Eine Arbeitsgruppe des BSI hat die mit 20.000 US-Dollar dotierte Challenge
RSA-640 mit Hilfe der Methode General Number Field Sieve (GNFS) gelöst.
Die Forscher benötigten für die Zerlegung der Zahl mit 193
Dezimalstellen in ihre beiden 320 Bit langen Primfaktoren rund fünf
Monate Rechenzeit auf einem Opteron-Cluster mit 80 2,2-GHz-Prozessoren,
wie der Website Crypto-World zu entnehmen ist.
Das Team konnte bereits im Mai dieses Jahres die Faktorisierung von
RSA-200 abschließen und war ebenfalls im Dezember 2003 an der bisher
größten gelösten Challenge RSA-576 beteiligt.
Wer das Ergebnis beispielsweise mit dem GNU Arbitrary Precision Calculator verifizieren möchte, die Zahlen für RSA-640 lauten:
310 7418240490 0437213507 5003588856 7930037346 0228427275
4572016194 8823206440 5180815045 5634682967 1723286782 4379162728
3803341547 1073108501 9195485290 0733772482 2783525742 3864540146
9173660247 7652346609 = 1634733 6458092538 4844313388 3865090859
8417836700 3309231218 1110852389 3331001045 0815121211 8167511579 *
1900871 2816648221 1312685157 3935413975 4718967899 6851549366
6638539088 0271038021 0449895719 1261465571
Die RSA-Laboratorien schreiben ihre Challenges schon seit Anfang der 90er-Jahre aus. Die nächst größere Challenge
ist nun die mit 30.000 US-Dollar dotierte RSA-704. Wer sich schon an
RSA-1024 oder RSA-2048 versuchen möchte – schließlich benötigt man im
günstigsten Fall mit einer gehörigen Portion Glück nur einige wenige
Divisionsversuche – kann sich auf 100.000 bzw. 200.000 US-Dollar
Preisgeld freuen.
Die Schwierigkeit der Zerlegung großer Zahlen in ihre Primfaktoren
ist das Fundament der meisten aktuell eingesetzten kryptographischen
Verfahren. 35=5*7 lässt sich noch leicht im Kopf rechnen. Doch schon bei 81072007=9001*9007
dürfte dies selbst mit einem guten Taschenrechner problematisch werden.
Bei entsprechend größeren Zahlen scheitern schnell selbst die größten
heute verfügbaren Rechensysteme. Schließlich steigt der Zeitaufwand für
eine Faktorisierung exponentiell mit der Stellenzahl: Für eine
zusätzliche Stelle ist der Aufwand um einen gewissen Faktor X größer,
für zwei Stellen schon X*X, für drei X*X*X usw.
Somit ist es zwar nach aktuellem Stand der Wissenschaft bis zur
erfolgreichen Faktorisierung von 1024 Bit langen Zahlen, wie sie noch
bis in die späten 90er-Jahre für PGP-Keys und SSL-Zertifikate
eingesetzt wurden, noch ein langer Weg, da der Zeitaufwand für eine
Faktorisierung exponentiell mit der Zahl der Bits ansteigt. Doch
berücksichtigt man das ebenfalls exponentielle Wachstum der
Rechenleistung, rückt die Faktorisierung von RSA-1024 schon zumindest
in absehbare Nähe.
Bisher geht man davon aus, dass sich das Faktorisierungsploblem nur
mit exponentiellem Aufwand lösen lässt. Dass es keinesfalls doch mit
polynomialem, also wesentlich geringerem Aufwand zu lösen wäre, konnte
bisher aber nicht bewiesen werden. Es ist deshalb nicht auszuschließen,
dass grundlegende Durchbrüche in der Zahlentheorie zu weiteren
drastischen Verkürzungen im Zeitaufwand führen werden. Und die in
Zukunft wahrscheinlich anstehende Verfügbarkeit von Quantencomputern,
die solche Faktorisierungsprobleme theoretisch im Handumdrehen lösen
können, setzt den heutigen gängigen Verfahren ein jähes Ende.
Nach der schrittweisen Heraufsetzung der verwendeten Schlüssellängen
hilft dann nur noch ein Umschwenken in der zu Grunde liegenden
Mathematik. Man kann das RSA-Verfahren leicht dahingehend modifizieren,
dass es nicht mehr auf den üblichen Zahlenringen, sondern auf so
genannten Elliptischen Kurven operiert. Auf diesen ist das
Faktorisierungsproblem ungleich schwieriger zu lösen. Ein Vorteil der
Elliptic-Curve-Crytography, kurz ECC, ist die wesentlich kürzere
Schlüssellänge. Ein ECC-Schlüssel mit nur 384 Bit ist nach heutigem
Ermessen etwa so sicher wie ein normaler RSA-Schlüssel mit 7680 Bit.
Siehe dazu auch:
(
cr/c't)
