Post-Quanten-Kryptographie

Die Post-Quanten-Kryptographie entwickelt Public-Key-Verfahren, deren Sicherheit auf Problemen beruht, die selbst für Quantencomputer als schwer lösbar gelten, und ersetzt RSA und die Elliptic-Curve-Kryptographie, die durch Shors Algorithmus gebrochen werden könnten.

Definition

Post-Quanten-Kryptographie umfasst klassische (nicht-quantenbasierte) kryptographische Algorithmen, die so konzipiert sind, dass sie auch gegenüber Angreifern mit großskaligen Quantencomputern sicher bleiben, indem sie auf Problemen basieren, für die kein effizienter Quantenalgorithmus bekannt ist.

Scope

Dieses Thema behandelt die Quantenbedrohung (Shor- und Grover-Algorithmen), die Hauptfamilien quantenresistenter Schemata – gitterbasiert, codebasiert, hashbasiert und multivariat –, die NIST-Standardisierungsbemühungen und ihre ausgewählten Algorithmen (ML-KEM, ML-DSA, SLH-DSA) sowie Migrationsaspekte wie „Harvest-Now-Decrypt-Later“ und hybride Bereitstellung. Es schließt die eigentliche Quantenkryptographie (Quantenschlüsselverteilung) aus, die Quantenhardware anstelle klassischer Algorithmen verwendet.

Core questions

• Warum brechen Quantencomputer RSA und die Elliptic-Curve-Kryptographie, aber symmetrische Chiffren nicht so stark?
• Welche schwierigen Probleme (Gitter, Codes, Hashes) gelten als resistent gegen Quantenangriffe?
• Welche Schemata hat NIST zur Standardisierung ausgewählt und welche Kompromisse gehen damit einher?
• Was ist die Bedrohung durch „Harvest-Now-Decrypt-Later“ und warum erzeugt sie Dringlichkeit?
• Wie werden Post-Quanten- und klassische Schemata in hybriden Bereitstellungen während der Migration kombiniert?

Key concepts

• Shors Algorithmus
• Grovers Algorithmus
• gitterbasierte Kryptographie (Learning with Errors)
• codebasierte Kryptographie
• hashbasierte Signaturen
• ML-KEM (Kyber) und ML-DSA (Dilithium)
• Harvest-Now-Decrypt-Later
• Krypto-Agilität
• hybrider Schlüsselaustausch

Key theories

Die Quantenbedrohung durch Shors Algorithmus

Shors Quantenalgorithmus faktorisiert ganze Zahlen und berechnet diskrete Logarithmen in polynomieller Zeit, wodurch RSA, Diffie-Hellman und die Elliptic-Curve-Kryptographie gebrochen werden; Grovers Algorithmus beschleunigt die Brute-Force-Suche nur quadratisch, sodass symmetrische Schlüssel lediglich verdoppelt werden müssen.

Quantenharte Problemfamilien

Post-Quanten-Sicherheit wird in Problemen wie Learning-with-Errors und Shortest-Vector-Problemen in Gittern, dem Dekodieren zufälliger linearer Codes und der Sicherheit von Hash-Funktionen gesucht – für keines davon sind effiziente Quantenalgorithmen bekannt.

Mechanisms

Gitterschemata wie ML-KEM (abgeleitet von CRYSTALS-Kyber) basieren die Schlüsselkapselung auf der Schwierigkeit des Modul-Learning-with-Errors-Problems, indem sie kleine zufällige „Fehler“ hinzufügen, die nur der private Schlüssel entfernen kann. Hash-basierte Signaturen (SLH-DSA/SPHINCS+) erstellen Signaturen ausschließlich aus der Sicherheit einer Hash-Funktion. Code-basierte Schemata verbergen eine dekodierbare Struktur in einem zufällig aussehenden linearen Code. Die Migration verwendet typischerweise hybride Konstruktionen, die ein klassisches und ein Post-Quanten-Schema kombinieren, sodass die Sicherheit erhalten bleibt, wenn eines von beiden überlebt.

Clinical relevance

Die Migration ist in den eingesetzten Systemen bereits im Gange: Große Browser und TLS-Bibliotheken haben den hybriden ML-KEM-Schlüsselaustausch ermöglicht, Messaging-Apps (Signals PQXDH) und SSH haben Post-Quanten-Handshakes hinzugefügt, und Standardisierungsgremien fordern Organisationen auf, Kryptographie zu inventarisieren und Übergänge zu planen. Das Risiko „Harvest-Now-Decrypt-Later“ bedeutet, dass Daten, die langfristige Vertraulichkeit erfordern, heute vor Quantenangriffen geschützt werden sollten.

Evidence & guidelines

NIST hat seine ersten Post-Quanten-Standards im Jahr 2024 finalisiert: FIPS 203 (ML-KEM) für die Schlüsselkapselung, FIPS 204 (ML-DSA) und FIPS 205 (SLH-DSA) für Signaturen. Leitlinien von NIST, NSA (CNSA 2.0) und nationalen Behörden legen Migrationszeitpläne fest. Die beste Praxis während des Übergangs bevorzugt hybride Schemata, die Post-Quanten- und klassische Algorithmen kombinieren.

History

Peter Shors Algorithmus von 1994 zeigte, dass Quantencomputer die dominierenden Public-Key-Systeme brechen könnten, was die Suche nach Alternativen motivierte. Die gitterbasierte Kryptographie entwickelte sich durch Ajtais Worst-Case-Härteergebnisse und Regevs Learning-with-Errors-Problem (2005) weiter. NIST startete 2016 einen öffentlichen Standardisierungsprozess; nach mehreren Runden wählte es CRYSTALS-Kyber und andere aus und veröffentlichte die ersten Standards (FIPS 203-205) im Jahr 2024.

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

Gibt es bereits Quantencomputer, die RSA brechen können?

Nein. Aktuelle Quantencomputer sind viel zu klein und zu fehleranfällig, um Shors Algorithmus für reale Schlüsselgrößen auszuführen. Die Sorge gilt zukünftigen Maschinen, kombiniert mit der Tatsache, dass heute verschlüsselte Daten gespeichert und entschlüsselt werden könnten, sobald solche Maschinen existieren.

Benötigt Post-Quanten-Kryptographie Quantenhardware?

Nein. Post-Quanten-Schemata laufen auf gewöhnlichen klassischen Computern; sie basieren lediglich auf mathematischen Problemen, die selbst für Quantenangreifer als schwer lösbar gelten. Die Quantenschlüsselverteilung, die Quantenhardware verwendet, ist ein separater Ansatz.