Weltrekord im Zahlenknacken

Die Mathematiker Jens Franke und Thorsten Kleinjung von der Universität Bonn haben nach eigenen Angaben gemeinsam mit Kollegen des Amsterdam Centrum voor Wiskunde en Informatica einen neuen Weltrekord im Zahlenknacken aufgestellt. Sie haben die 200-stellige Zahl RSA200 in ihre beiden Primfaktoren zerlegt. Die Rechenarbeit fand auf Computern beider beteiligter Hochschulen statt, zusätzlich halfen Maschinen des Bundesamtes für Sicherheit in der Informationsverarbeitung (BSI). Allein an der Universität Bonn musste ein Cluster aus 80 2,2-Gigahertz-Rechnern des Typs Opteron, verbunden durch ein Gigabit-Netzwerk, drei Monate lang arbeiten.

Die Zerlegung von RSA-200 war eine der Aufgaben, die das US-amerikanische Kryptografie-Unternehmen RSA Security im Rahmen seines Faktorisierungswettbewerbs stellt. Sie sind weitaus mehr als purer Denksport: Auf der Tatsache, dass große Zahlen so schwierig zu zerlegen sind, beruhen wichtige gängige Verschlüsselungs- und Signaturverfahren der so genannten Public-Key-Kryptografie -- allen voran das RSA-Verfahren. Jeder, der im Internet über eine verschlüsselte Seite einkauft, Online-Banking macht oder sein Auto mit einer elektronischen Wegfahrsperre sichert, muss sich auf sie verlassen. Die neue Faktorisierung stellt die Sicherheit dieser Chiffren zwar nicht grundsätzlich in Frage, mahnt jedoch zu gesteigerter Wachsamkeit beim Umgang mit ihnen. Derzeit empfehlen Experten die Verwendung von 300-stelligen Zahlen bei RSA.

Mit RSA-200 hat sich das Team von Franke wieder den Faktorisierungsrekord zurückgeholt, den sie nur für eine Woche verloren hatten. Erst am 2. Mai hatte eine japanische Gruppe um Kazumaro Aoki bekannt gegeben, dass sie mit einem Rechnerverbund des Telekommunikationskonzerns NTT die 176-stellige Zahl C176, einen Faktor von 11²⁸¹+1 zerlegt haben, wobei sie die Rechenverfahren der Bonner Konkurrenz benutzten. Die vorige Bestmarke von Franke, Kleinjung und Kollegen, aufgestellt im Dezember 2003, stand bei RSA-576 mit zwei Stellen weniger. Gleich anschließend hatten sich Franke und Kleinjung mit ihren niederländischen Kollegen an die Zerlegung von RSA-200 gemacht.

Alle diese Faktorisierungen basieren auf einer zahlentheoretischen Technik namens Zahlkörpersieb. Dieses Verfahren strukturiert und beschleunigt die zu leistende Rechenarbeit beträchtlich. Aber im Prinzip ist Faktorisierung noch immer mehr stupides Suchen als gezieltes Finden. Im Fall von RSA200 hätte ein einzelner 1-Gigahertz-Pentium-Rechner dazu 121 Jahre gebraucht -- und das nur für den wichtigsten Schritt des Zahlenrätsels. (Tobias Hürter, Technology Review) / (wst)