Quanten-Einführung für CISOs: Warum RSA und elliptische Kurven fallen und Gitter sie ersetzen

Ein Quantencomputer bedroht die heutige Public-Key-Verschlüsselung aus einem einzigen Grund. Die Mathematik darunter hat eine Form, und ein Quantencomputer kann eine Form sehen, die ein klassischer Computer Schritt für Schritt abfahren muss.

Die Analogie: eine Buslinie und ein Raster

Die heutige Verschlüsselung folgt einer Route, wie eine Buslinie, die sich durch eine Altstadt windet. RSA und elliptische Kurven sind auf Straßenhöhe schwer zu erraten und von oben offensichtlich. Ein Quantencomputer hat die Kartenansicht, in der die Form die Route verrät.

Ein Gitter ersetzt die Altstadt durch ein strenges modernes Raster. Jede Straßenecke sieht aus wie jede andere, die Ansicht von oben verrät also nichts darüber, an welcher Ecke das Geheimnis liegt. Je größer das Raster, desto schwerer das Raten.

Zwei isometrische Stadtviertel nebeneinander unter der englischen Überschrift „A quantum computer has the map view.“ Links, beschriftet mit RSA und elliptischen Kurven, windet sich eine orangefarbene Buslinie durch eine unregelmäßige Altstadt und ist auf einer Ebene darüber noch einmal eingezeichnet: auf Straßenhöhe schwer zu erraten, von oben offensichtlich. Rechts, beschriftet mit Lattice (Gitter), stehen gleiche Blöcke in einem strengen Raster, und die Ebene darüber zeigt ein gleichmäßiges Punktraster: Jede Ecke sieht aus wie jede andere, und je größer das Raster, desto schwerer das Raten.

Das Bild ist eine Vereinfachung. Die folgenden Abschnitte nennen, was hinter jeder seiner beiden Hälften steht.

Was Shors Algorithmus an RSA und elliptischen Kurven ausnutzt

Peter Shor zeigte 1994, dass ein Quantencomputer in Polynomialzeit ganze Zahlen faktorisieren und diskrete Logarithmen berechnen kann. RSA beruht auf der Faktorisierung. Die Elliptische-Kurven-Kryptographie beruht auf einem diskreten Logarithmus. Beide Probleme lassen sich darauf zurückführen, eine verborgene Periode zu finden, ein Muster, das sich über das gesamte Problem wiederholt, und die Periodenfindung ist die Aufgabe, bei der ein Quantencomputer jedes bekannte klassische Verfahren übertrifft.

Diese Periode ist die Buslinie. Ein klassischer Angreifer fährt sie Haltestelle für Haltestelle ab, und ihm läuft die Zeit davon. Ein Quantenangreifer sieht die ganze Schleife auf einmal. Die Hardware, die den Angriff bei kryptographischen Schlüsselgrößen ausführt, ist noch nicht gebaut, und elliptische Kurven mit 256 Bit fallen auf derselben Hardware früher als RSA-2048.

Was der Beweis der Aaronson-Ambainis-Vermutung hinzufügt

Physical Superintelligence gab am 6. November 2026 einen Beweis der Aaronson-Ambainis-Vermutung bekannt. Die Vermutung stammt aus einer Arbeit von Scott Aaronson und Andris Ambainis aus dem Jahr 2009 mit dem Titel The Need for Structure in Quantum Speedups. Ihre Folge für Ja-Nein-Probleme: Auf einer Eingabe ohne verborgenes Muster kann ein Quantenalgorithmus einen klassischen höchstens um einen polynomiellen Faktor schlagen, gemessen daran, wie viel von der Eingabe jeder der beiden lesen muss.

Ein KI-Forschungssystem hat den Beweis erzeugt, und der Beweisassistent Lean hat ihn geprüft. Aaronson hat geschrieben, dass er ihn für korrekt hält, und verweist auf die maschinelle Prüfung und die Durchsicht durch menschliche Fachleute. Guy Blanc, Jordan Docter, Carmen Strassle und Li-Yang Tan, die im August einen Spezialfall bewiesen haben, haben eine Darstellung des Beweises veröffentlicht. Die Begutachtung durch eine Fachzeitschrift steht noch aus.

Für ein Sicherheitspublikum stellt das Ergebnis ein Theorem hinter eine einzige Aussage: Ein exponentieller Quantenvorteil setzt Struktur voraus. Die Kartenansicht hilft dort, wo es eine Route zu sehen gibt. Der Geltungsbereich ist eng. Das Theorem zählt Lesezugriffe auf die Eingabe und erfasst Entscheidungsprobleme auf den meisten Eingaben. Über ein bestimmtes Kryptosystem trifft es keine Aussage.

Warum Gitter der Ersatz sind

ML-KEM, standardisiert als FIPS 203, beruht auf dem Problem Module Learning with Errors: ein Geheimnis aus Gleichungen über einem hochdimensionalen Gitter zurückzugewinnen, nachdem kleine Fehler hinzugefügt wurden. Niemand hat dort eine verborgene Periode gefunden, die Shors Verfahren nutzen könnte, und ein anderer effizienter Quantenalgorithmus für das Problem ist nicht bekannt.

Diese Härte ist eine Vermutung. Sie stützt sich auf Jahrzehnte gescheiterter Angriffe, darunter eine Quantenbehauptung, die im August widerlegt wurde. Der Beweis der Aaronson-Ambainis-Vermutung lässt diesen Status unverändert. Er erklärt, warum sich die Quantenbedrohung auf RSA und elliptische Kurven konzentriert, und die Sicherheit der Gitter stützt sich weiterhin auf ihre eigene Evidenz.

Was das für die Reihenfolge der Migration bedeutet

Der Schlüsselaustausch kommt zuerst. Heute aufgezeichneter Verkehr lässt sich entschlüsseln, sobald ein leistungsfähiger Quantencomputer existiert, die Exposition beginnt also im Moment der Aufzeichnung. Die ausgerollte Antwort ist der hybride Schlüsselaustausch. RFC 10024 definiert X25519MLKEM768, das die elliptische Kurve und das Gitter gemeinsam ausführt, sodass die Sitzung sicher bleibt, solange eines von beiden hält.

Signaturen folgen, weil eine Fälschung einen Quantencomputer zum Zeitpunkt des Angriffs erfordert. ML-DSA ist final und sein Zertifikatspfad ist spezifiziert, und die Argumente dafür, mit Leaf-Zertifikaten zu beginnen, stehen in einem eigenen Beitrag.

Beide Schritte beginnen mit einem Inventar der Endpunkte, die noch eine Kurve allein aushandeln. [PQ]probe meldet die Schlüsselaustauschgruppen und Signaturalgorithmen, die jeder Endpunkt aushandelt, und gibt der Migration damit eine Liste von Hosts, mit der sie arbeiten kann.

Quellen:

Alle [PQ]files