RSA-Code gefährdet

Kein Schutz durch Primzahlen

05.04.2004
Von Nikolaus Deussen

Um den 48-Bit-Schlüssel zu decouvrieren, musste Germano Caronni von der ETH Zürich 1997 noch 300 Enthusiasten mit 5000 Computern zusammenbringen. Zum Millenniumswechsel knackte ein schwedisches Kryptologen-Team um Fredrik Almgren den RSA-Code mit 512 Bit. 70 Jahre Rechenzeit hätte ein Computer mit den bisher bekannten Berechnungsmethoden benötigt. Doch die Stockholmer Forscher setzten nicht nur auf die schiere Rechenkraft von Elektronengehirnen. Um das Rätsel zu lösen, ersannen sie ein neues, schnelles Rechenverfahren. Der ausgebuffte Algorithmus präsentierte schon nach wenigen Wochen das Ergebnis.

576 Bit nur ein bisschen sicher

Ende letzten Jahres zerlegte Jens Franke von der Bonner Universität die Chiffre mit 576 Bit: ein Weltrekord. Das Preisgeld: 10 000 US-Dollar. "Unser Rekord ist der erste dieser Art, bei dem ein Netzwerk handelsüblicher Linux-Rechner zum Einsatz kam", so Mathematiker Franke. Beteiligt an der Rekordleistung waren das Centrum voor Wiskunde en Informatica in den Niederlanden, das Bundesamt für Sicherheit für Informationstechnik sowie das Bonner Institut für Numerische Simulation. Die heute verwendeten RSA-Schlüssel sind meist 1024 Bit lang. "Das heißt, als Binärzahl aus Nullen und Einsen geschrieben hätten sie 1024 Ziffern", erklärt Marc Alexander Schweitzer vom Institut für Numerische Simulation.

Peter Shor aus den Forschungslabors von AT & T hat jedoch schon vor ein paar Jahren ein Rechenverfahren vorgestellt, das eine Zerlegung in Faktoren genauso schnell erledigt wie die Multiplikation. Dabei nutzt der amerikanische Mathematiker die Fähigkeit der Quantenbits, sich unterschiedliche Zustände merken und dadurch parallel abarbeiten zu können.

Faktorieren so schnell wie Multiplizieren

Allerdings funktioniert Shors Methode nur auf Quantencomputern, von denen es bislang lediglich Prototypen gibt. Isaac Chuang von IBMIBM baute 2001 einen kleinen Versuchs-Quantenrechner, mit dem er die Tauglichkeit des Shorschen Quantenparallelismus überprüfte. Der Q-Computer schaffte mit sieben Quantenbits aus Fluoratomen bereits die korrekte Zerlegung der Zahl 15. Das klingt noch nicht wirklich bedrohlich. Dennoch: "Es gibt keinen Grund anzunehmen, dass der dramatische Fortschritt der letzten 20 Jahre schon an seinem Ende angelangt sei", warnt Johannes Buchmann, Mathematiker an der Technischen Hochschule Darmstadt. Alles zu IBM auf CIO.de

In Ermangelung von Quantencomputern versuchen die Bonner Mathematiker erst einmal, mit herkömmlicher Technik den nächsten Code zu knacken. Sie visieren als Nächstes RSA-640 an. Im Laufe des Jahres, hoffen sie, können sie die Zahl tranchieren. Wie lange es braucht, um RSA-2048, die größte durch RSA Security veröffentlichte Zahl, zu faktorisieren, kann derzeit nicht einmal vermutet werden. Dem Sieger winkt dann allerdings das erkleckliche Sümmchen von 200 000 US-Dollar.

Zur Startseite