RSA-640 geknackt
Einer Arbeitsgruppe des BSI ist es gelungen, die mit 20.000 US-Dollar dotierte RSA-Challenge mit 640 Bit in die beiden 320-Bit-langen Primfaktoren zu zerlegen.
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)
