Einleitung Post-Quanten-Kryptografie

Bitte beachten Sie die Abgrenzungen zwischen Quantenkryptologie, Quantenkryptografie, Quantenkryptoanalyse und Post-Quanten-Kryptografie, wie sie auf der Index-Seite nachzulesen ist.

Das am Horizont auftauchende Problem: Quantencomputer

Quantenkryptoanalyse ist das, was man gemeinhin als Kryptoanalyse, also das Knacken von Chiffren, versteht, nur halt mit Quantencomputern statt mit herkömmlichen Computern.

Der große Unterschied zwischen herkömmlichen und Quanten-Computern ist, dass ein herkömmlicher Computer alles sequentiell, also Eins nach dem Anderen abarbeiten muss, während ein Quantencomputer alle Vielzahl von Rechenschritten parallel ausführen kann. Er findet sozusagen die sprichwörtliche Nadel im Heuhaufen sofort, statt sich sich einen Strohhalm (oder vermeintliche Nadel) nach dem anderen anzuschauen.

Der herkömmliche Computer führt die sequentiellen Schritten zwar sehr sehr schnell aus - milliardenfach pro Sekunde - doch kommt er unterm Strich trotzdem nicht an die Geschwindigkeit eines Quantencomputers heran, wenn es um Aufgaben geht, die durch paralleles Rechnen gelöst werden können. Bei weitem nicht. Wie das genau funktioniert, erfahren Sie im Artikel Quantencomputer und wie sie funktionieren, dessen Lektüre ich vor dem Weiterlesen sehr empfehle, um das hier Geschriebene zu verstehen.

Welche klassischen Verschlüsselungsverfahren sind betroffen?

Es gibt Verschlüsselungsalgorithmen, die sind anfälliger für Quantenkryptoanalyse, eben weil die Aufgabenstellung, diese Chiffre zu knacken, wie gemacht ist für das Rechenprinzip von Quantencomputern. Dies sind vornehmlich asymmetrische Chiffren wie zum Beispiel RSA.

Und es gibt Verschlüsselungsalgorithmen, bei denen man keinen großen Geschwindigkeits-Vorteil durch den Einsatz von Quantencomputern erreichen kann. Das sind vornehmlich symmetrische Chiffren wie zum Beispiel AES.
Bei solchen erhält man beispielsweise durch Einsatz des Grover-Algorithmus für Quantencomputer maximal eine Beschleunigung auf das Quadrat des ursprünglichen Geschwindigkeit.

Das kann im Fall von AES aber allein schon dadurch ausgeglichen werden, dass man die Schlüssellänge verdoppelt, also statt den 128 Bit, die für herkömmliche Computer derzeit als sicher gelten, 256 Bit benutzt. Das Knacken von 256 Bit gegenüber 128 Bit dauert im Quadrat länger. Was genau den Vorteil, den ein Quantencomputer bietet, ausgleicht bzw. zunichte macht.

Anders sieht es bei asymmetrischen Algorithmen aus. Das sind Verfahren, die in eine Richtung schnell berechenbar sind und in die andere wesentlich schwieriger. Das nennt man eine Einwegfunktion oder Einbahnfunktion. RSA zum Beispiel benutzt als Einwegfunktion Primzahlen. Zahlen, auch große Primzahlen, miteinander zu multiplizieren ist für einen herkömmlichen Computer einfach und geht schnell. Aber herauszufinden, aus welchen Faktoren das Ergebnis eine Multiplikation zweier Primzahlen besteht, das ist schwierig und dauert. Bisher. Für Menschen und herkömmliche Computer. Das macht sich RSA zunutze.

Für Quantencomputer, die massiv parallel rechnen, ist es allerdings nicht ganz so schwierig, die beiden Nadeln (Primzahlen) im Heuhaufen zu finden. Dafür wurde sogar schon ein spezieller Algorithmus entwickelt, der Shor-Algorithmus. In der Theorie kann man damit z. B. RSA-Chiffren knacken.

Solche Publik-Key-Verfahren kommen im Internetverkehr ständig vor, auch wenn wir sie nicht sehen: beim Versenden und Empfangen von e-mails, beim Aufrufen von sicheren Web-Seiten via HTTPS, beim Austausch von Nachrichten via Messenger-App, beim Übertragen von Kreditkarteninformationen zu Webshops oder bei Transaktionen zwischen Banken.

Quantencomputer stellen damit eine Gefahr für asymmetrische Chiffren, sogenannte Publik-Key-Verfahren dar, bei denen es geteilte Schlüssel und Einwegfunktionen gibt. Diese werden wahrscheinlich irgendwann in der Zukunft viel schneller zu knacken sein als jetzt.

Wozu dient Post-Quanten-Kryptografie?

Die Post-Quanten-Kryptografie (englisch post-quantum cryptography, kurz PQC) ist eine Gegenmaßnahme gegen die Quantenkryptoanalyse. Sie sucht nach Public-Key-Algorithmen für herkömmliche Computer, die eben nicht mit Quantencomputern zu brechen sind. Und natürlich auch nicht mit herkömmlichen. Sie macht sozusagen den Geschwindigkeitsvorteil von Quantencomputern zunichte.

Dabei steht das mathematische Verfahren, dass die Einbahnfunktion abbildet, im Vordergrund. Für diese Einbahnfunktion darf es keine Möglichkeit der Abkürzung durch Quantencomputer geben.

Es gibt mit der Quantenkryptografie bzw. dem Quantenschlüsselaustausch (QKD) zwar bereits eine Möglichkeit für ein quantenkryptoanalytisch sicheres Verfahren. Die Entwicklung ist auch schon soweit, dass es einsetzbar wäre, aber es ist noch sehr kostspielig. Darum sucht die Post-Quanten-Kryptografie nach kostengünstigen und einfach implementierbaren Verfahren für klassische Computer. Diese Algorithmen bieten keine Angriffsfläche, die die Quantencomputer-Technologie ausnutzen könnten oder es gibt keine nennenswerte Geschwindigkeitsvorteile dabei.

Auf der Suche nach der perfekten, quantensicheren Einwegfunktion

Das National Institute of Standards and Technology (NIST) in den USA führt seit 2017 einen Auswahlprozess zur Standardisierung von Post-Quanten-Kryptographie (NISTPQC) durch. Diese meist auf dem Prinzip von mathematisches Gittern beruhenden Algorithmen sollen dann statt z. B. RSA zum Einsatz kommen.

Diese Auswahlprozesse des NIST haben sich als gute Möglichkeit herausgestellt, Kryptologen mit ihren Ideen zusammenzubringen, damit diese diese gegenseitig verifizieren. 2000 gab es eine Ausschreibung, um DES abzulösen und es gab am Schluss einen Sieger - die Rijndael-Chiffre- die zum neuen Advanced Encryption Standard, AES wurde. Dieser gilt bis heute als sicher und es wurden darin noch keine Schwächen gefunden.

Ähnliches gilt auch für den SHA-3-Wettbewerb des NIST, der 2006 einen Nachfolger für SHA-2 suchte: Es startete 64 Kandidaten, 14 kamen in die 2. Runde und schließlich wurde Keccak als Sieger gekürt und neuer Standard.

Dieses Erfolgsrezept wollte das NIST 2017 wiederholen und startete den Post-Quanten-Wettbewerb, diesmal sollten allerdings mehrere Sieger zulässig sein.

Es gingen 82 Kandidaten in das Rennen, von Big Quake bis WalnutDSA, wobei 17 Publik-Key-Verschlüsselungs-Verfahren in Runde 2 gingen. Davon blieben in Runde 3 nur noch vier übrig: Classic McEliece, CRYSTALS-KYBER, NTRU und SABER.

Dabei sind CRYSTALS-Kyber, NTRU und SABER sogenannte Lattice-basierte Algorithmen. Da heißt, ihre mathematischen Funktionen basieren auf den geometrischen Eigenschaften von Gitterstrukturen, die aus einer Reihe mit Regeln verbundenen Punkten bestehen. Classic McEliece ist ein Code-basierter Algorithmus.

Im Jahr 2022 verkündete das NIST nach 6 Jahren Auswahlverfahren die ersten Sieger: CRYSTALS-Kyber für Verschlüsselung und für Signatur-Zwecke CRYSTALS-Dilithium, FALCON (beide Lattice-basiert) und SPHINCS+ (Hash-basiert).

Im August 2024 erfolgte dann die Standardisierung nach FIPS (Federal Information Processing Standard):

FIPS 203 ist für Verschlüsselungen und basiert auf dem CRYSTALS-Kyber algorithm, kurz auch ML-KEM für Module-Lattice-Based Key-Encapsulation Mechanism
FIPS 204 ist für Signaturen und basiert auf CRYSTALS-Dilithium, kurz ML-DSA für Module-Lattice-Based Digital Signature Algorithm
FIPS 205 ist ebenfalls für Signaturen und basiert auf Sphincs+, kurz SLH-DSA für Stateless Hash-Based Digital Signature Algorithm und stellt ein Backup für FIPS 204 dar.
Wenn der Entwurf des FIPS 206-Standards, der auf FALCON aufbaut, veröffentlicht wird, wird der Algorithmus FN-DSA heißen, kurz für FFT (Fast-Fourier-Transformation) over NTRU-Lattice-Based Digital Signature Algorithm.

Die NIST Sieger-Algorithmen für Kryptografie sind also "Lattice-Based".

Wie funktioniert Gitter-basierte Post-Quanten-Kryptografie?

Gitter-basierte Kryptografie verschlüsseln Daten mithilfe von mathematischen Strukturen, die Gitter (engl. lattices) genannt werden.

Ein Gitter kann man sich ganz einfach als eine regelmäßige Anordnung von Punkten vorstellen. Nehmen wir zum Beispiel ein Schachbrett. Das hat acht mal acht, also 64 Felder. Nun ziehen wir horizontale und vertikale Linien zwischen den Feldern und liegen auf jede Kreuzung davon einen Dame-Stein. Diese Kreuzungen sind unsere Gitterpunkte. Es gibt auf dem Schachbrett je Richtung sieben Kreuzungslinien, also 49 Gitterpunkte. Wir haben ein zweidimensionales Gitter.

Nun stellen wir acht Schachbretter hochkant hintereinander, schön gegeneinander ausgerichtet. Unsere Gitter-Matrix wird dreidimensional, weil wir jetzt auch gedachte Linien von vorne nach hinten durch die Schachbretter ziehen können. Für das Befestigen der Dame-Steine, um die Gitterpunkte zu markieren, brauchen wir jetzt zwar Kleber, aber es gelingt uns, ein dreidimensionales Gitter zu erschaffen.

Nun denken wir uns schwierig zu lösende Probleme für unsere Gitter-Matrix aus. Gerne genommen sind Kürzester Vektor (SVP): Finde den kürzesten Abstand zwischen zwei Punkten im Gitter. Und Nächster Vektor (CVP): Finde den nächstgelegenen Gitterpunkt zu einem beliebigen Punkt, der irgendwo zwischen den Gitterpunkten im Raum liegt.

Das mag bei drei Dimensionen nach einer einfachen Lösung ausschauen: Man nimmt einfach einen Faden und verbindet die entsprechenden Gitterpunkte probehalber miteinander, bis man die Lösung hat - und schon hat man den Vektor mit Länge und Richtung. Doch die Mathematik ist nicht auf drei Dimensionen beschränkt. Man kann auch mit Matrizen in hunderten Dimensionen rechnen. Beim CVP-Problem hat dann ein Punkt nicht mehr nur vier Nachbarn wie im zweidimensionalen Raum, sondern bei einem 500-dimensionalen Gitter gleich 2⁵⁰⁰ (eine Zahl mit 150 Dezimalstellen) Nachbarn. Und das treibt den Rechenaufwand nach oben. Auf herkömmlichen, als auch auf Quantencomputern. Denn bei diesen Problemen gibt es keine Geschwindigkeitsvorteile für Quantencomputer. Die Abkürzung kommt erst in Form eines Schlüsselteils, der genutzt werden kann, um das Problem wesentlich zu vereinfachen.

Zur Verschlüsselung werden diese schwierigen Probleme so genutzt, dass die Sicherheit des Verschlüsselungssystems darauf beruht – ein Angreifer müsste also genau diese mathematisch schwierigen Probleme lösen, um an die verschlüsselte Information zu kommen.

Die Probleme lassen sich auch als algebraische Gleichungen ausdrücken und lösen. Der Schlüssel zum Ver- und Entschlüsseln sind Variablen, die beim Versuch des Brute-Force-Angriffs ohne Schlüssel unbekannt sind und zur Lösung der Gleichung immens Zeit brauchen. Erst mit dem Schlüssel werden alle Variablen in der Gleichung bekannt und die Rechnung wird zu einer simplen Mal und Plus-Aufgabe, die sich blitzschnell berechnen lässt.

Post-Quantenkryptografie ist heute schon einsetzbar. Quantencomputer sind noch lange nicht soweit.

Die Schätzungen, zu welchem Zeitpunkt in der Zukunft RSA durch Quantencomputer schnell geknackt werden kann, gehen auseinander. Aber mit dem Hintergrund, dass Chiffrate auch schon heute zwischengespeichert werden können, um dann später entschlüsselt zu werden, rückt eher das "Verfalldatum" der Chiffrate, ab dem sie dem Angreifer keinen Nutzen mehr bieten, in den Vordergrund.

Wie lange das noch hin sein mag, darüber kann man nur spekulieren. Siehe auch den Abschnitt Wann bricht die Kryptokalypse aus? in der Einleitung zur Quantenkryptoanalyse.