Spezialhardware bedroht möglicherweise RSA-Sicherheit

Selten hat ein mathematischer Forschungsantrag derart für Wirbel gesorgt, wie das Proposal Circuits for integer factorisation des Mathematikers und qmail-Autors Daniel J. Bernstein. Er will versuchen, mit Hilfe spezieller Hardware bei der Bewältigung zahlentheoretischer Probleme beachtliche Fortschritte zu erzielen -- ein Vorschlag, der vor allem Kryptographie-Experten aufgeschreckt hat.

Ein spezielles Augenmerk legte Bernstein auf das so genannte Faktorisierungsproblem: Dieses basiert auf der Tatsache, dass es sehr einfach ist, zwei ganze Zahlen zu multiplizieren (polynomineller Zeitaufwand), es allerdings bisher nicht gelungen ist, einen Algorithmus anzugeben, welcher in polynomineller Zeit, sprich annehmbar schnell, die Faktoren einer hinreichend großen Zahl bestimmen kann. Auf dieser Problemstellung basiert das bekannteste Public-Key-Verfahren für Verschlüsselung und Signaturen RSA, benannt nach seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adleman. Es findet Verwendung in sehr vielen wichtigen Internet-Protokollen (PGP, SSH, SSL, usw.) und soll auch in Hochsicherheitsbereichen wie der Atomwaffensicherung zum Einsatz kommen.

Gelingt es, die Faktorisierung des Modulus eines öffentlichen RSA-Schlüssels zu finden, ist daraus die Berechnung des zugehörigen geheimen Schlüssels sehr einfach möglich. Damit wäre das RSA-Verfahren gebrochen: Es können unautorisierte Signaturen geleistet und in den meisten Systemen neben der aktuellen, auch die vergangene und zukünftige Kommunikation entschlüsselt werden. Dies hätte ganz erhebliche Auswirkungen.

Eine erste Analyse von Bernsteins Publikation legt allerdings nahe, dass mathematisch betrachtet die vorgeschlagenen Techniken keinen revolutionären Durchbruch darstellen. Schlüssellängen über 1024 Bit bleiben damit wahrscheinlich vorerst außerhalb der Reichweite "normaler" Angreifer. Allerdings werfen Bernsteins feine Optimierungen die Frage auf, ob für Organisationen mit hinreichend großem Etat selbst 1536-Bit-Schlüssel in realistischer Reichweite sind.

Für sehr große Schlüssellängen will Bernstein die Faktorisierungskosten bezüglich der Schlüssellänge um den Faktor "3,009..." reduzieren. Dies würde in der Tat bedeuten, dass angesichts der Tatsache, dass 1999 unter der Führung einer Amsterdamer Forschergruppe eine 512-Bit-Zahl erfolgreich faktorisiert wurde, Schlüssellängen unter 2048 Bit akut gefährdet wären. Allerdings ist der Faktor drei asymptotisch zu sehen -- vereinfacht ausgedrückt, ist es keinewegs klar, ob unter realistischen Annahmen mit Bernsteins Ideen für derzeit gängige Schlüssellängen (1024 bis 4096 Bit) eine deutliche Beschleunigung zu erzielen ist.

Wie so häufig wurde nach der Bernstein-Veröffentlichung die Frage nach Alternativen zu RSA gestellt. Die am weitesten verbreiteten Systeme für Kryptographie mit öffentlichen Schlüsseln basieren auf den beiden schon lange Zeit untersuchten zahlentheoretischen Problemen der Faktorisierung (FP) und des Diskreten Logarithmus (DLP). Die vorherrschende wissenschaftliche Meinung ist, dass beide Probleme eng miteinander verknüpft sind, und dass ein Durchbruch bei der Lösung des einen Problems auch zu dramatischen Verbesserungen bei der Lösung des anderen Problems führen würde. In der Tat weisen die bisher bekannten Methoden, diese beiden Probleme algorithmisch anzugehen, einige Ähnlichkeiten auf. So äußerte Bernstein ebenfalls, dass die von ihm untersuchten Methoden sich auch auf das Diskrete Logarithmus-Problem und damit insbesondere auch gegen Eliptische-Kurven-Kryptosysteme einsetzen lassen.

Was in jedem Falle hilft, sind größere Schlüssellängen. Hier unterstützt die Mathematik den Schwächeren. Etwas mehr Aufwand beim Verschlüsseln beziehungsweise Signieren erhöht die Kosten für den Angreifer ganz erheblich: Für neuerzeugte Schlüssel empfiehlt sich eine Mindestlänge von 2048 Bit. Falls keine Echtzeitnotwendigkeit besteht, bietet sich die Verwendung von Schlüsseln an, die länger als 2048 Bit sind. (Rüdiger Weis) / (wst)