# Post‑Quantum‑Kryptografie: Sicherheit im Zeitalter der Quantencomputer
## Einleitung
Die klassische Kryptografie stützt sich auf Probleme wie die Primfaktorzerlegung großer Zahlen oder den diskreten Logarithmus. Diese mathematischen Aufgaben gelten als praktisch unlösbar für heutige Computer, sodass Verfahren wie RSA und elliptische Kurvenkryptografie sicher sind – vorerst. Mit dem Aufkommen von Quantencomputern droht sich diese Annahme zu ändern. Peters und Kollegen haben gezeigt, dass ein Quantenrechner mit Shors Algorithmus das Primfaktorproblem in polynomieller Zeit lösen kann, wodurch die Grundpfeiler der asymmetrischen Kryptografie wegbrechen. Auch Grovers Algorithmus beschleunigt die Suche in unstrukturierten Datenbanken quadratisch und verkürzt effektiv die erforderliche Schlüssellänge von symmetrischen Verfahren um die Hälfte. Post‑Quantum‑Kryptografie (PQC) beschreibt eine Sammlung kryptografischer Verfahren, die selbst angesichts leistungsfähiger Quantencomputer sicher bleiben sollen.
Es ist wichtig, PQC von echter **Quantenkryptografie** zu unterscheiden. Letztere nutzt quantenmechanische Phänomene wie Verschränkung, um beispielsweise in der Quantenkommunikation physikalisch garantierte Sicherheit zu erreichen. PQC hingegen ist rein klassisch implementierbar und basiert auf neuen mathematischen Annahmen, die als schwer lösbar angesehen werden – auch für Quantencomputer. In den folgenden Abschnitten werden die Motivation hinter PQC, die wichtigsten Verfahren, der Stand der Standardisierung und die Herausforderungen beim Einsatz beleuchtet.
## Motivation: Warum Post‑Quantum‑Kryptografie?
Die Bedrohung durch Quantencomputer ist real, auch wenn große, fehlertolerante Systeme noch in der Zukunft liegen. Schätzungen des National Institute of Standards and Technology (NIST) und diverser Forschungsgruppen sehen die Möglichkeit, kryptografisch relevante Größenordnungen in den späten 2030er- oder 2040er-Jahren zu erreichen. Darüber hinaus gibt es das „Harvest‑now‑decrypt‑later“-Szenario: Angreifer sammeln heute verschlüsselte Daten und warten ab, bis sie diese später mit einem ausgereiften Quantencomputer entschlüsseln können. Ohne Gegenmaßnahmen könnten vertrauliche Informationen wie Gesundheitsdaten, vertrauliche E-Mails oder geheime Kommunikation kompromittiert werden.
PQC verfolgt zwei Ziele:
* **Ersetzen unsicherer Verfahren**: Algorithmen wie RSA oder ECDH müssen durch Alternativen ersetzt werden, die resistent gegen Shors Algorithmus sind. Dies betrifft sowohl Schlüssel‑Austausch als auch digitale Signaturen.
* **Sichere Schlüssellängen anpassen**: Symmetrische Verschlüsselung und kryptografische Hashfunktionen bleiben gegen Quantenangriffe tendenziell sicher, erfordern aber längere Schlüssellängen oder Ausgabewerte, um Grovers Algorithmus zu kompensieren.
## Grundtypen post‑quantenkryptografischer Verfahren
Die Forschungsgemeinschaft hat eine Vielzahl mathematischer Strukturen identifiziert, deren zugrunde liegende Probleme auch mit einem Quantencomputer als schwer lösbar gelten. Die wichtigsten Klassen sind folgende:
### Gitterbasierte Kryptografie
Gitterbasierte Verfahren basieren auf Problemen wie dem **Learning With Errors (LWE)** oder dem **Shortest Vector Problem (SVP)**. Ein Gitter ist ein regelmäßiges Punktgitter in einem Vektorraum, das durch eine Basis erzeugt wird. Die Aufgabe, den kürzesten Vektor oder eine kleine Störung innerhalb eines Gitters zu finden, gilt als schwer – selbst für Quantencomputer. Zu dieser Familie gehören:
* **NTRU**: Ein frühes gitterbasiertes System für Verschlüsselung und Signaturen.
* **CRYSTALS‑Kyber**: Ein Key‑Exchange‑Mechanismus (bzw. KEM – Key Encapsulation Mechanism), der als sicher und effizient gilt und vom NIST zur Standardisierung ausgewählt wurde.
* **CRYSTALS‑Dilithium**: Ein Signaturschema, das wie Kyber auf dem Modul‑LWE‑Problem basiert und ebenfalls zur St
### Code‑basierte Kryptografie
Code‑basierte Verfahren beruhen auf der Schwierigkeit, beliebige lineare Codes effizient zu dekodieren. Das prominenteste Beispiel ist **McEliece**, ein Verschlüsselungssystem aus den 1970er‑Jahren, das auf binären Goppa‑Codes basiert. Varianten und Weiterentwicklungen sind:
* **HQC (Hamming Quasi‑Cyclic)** und **BIKE (Bit Flipping Key Encapsulation)**: Diese beiden KEMs befinden sich noch im NIST‑Auswahlprozess und nutzen strukturierte QC‑MDPC‑Codes (quasi‑zyklische, mitteldichte Paritätscheck Codes).
* **Classic McEliece**: Der ursprüngliche McEliece‑Algorithmus mit strengen Parametern; er hat sehr lange öffentliche Schlüssel (mehrere hundert Kilobyte), ist aber extrem robust gegen bekannte Angriffe.
Code‑basierte KEMs zeichnen sich durch schnelle Verschlüsselung und Entschlüsselung aus und gelten als sehr sicher. Ein Nachteil sind die großen Schlüssellängen, insbesondere im Vergleich zu gitterbasierten Verfahren.
### Mehrvariaten‑Polynomial‑Kryptografie
Bei diesen Verfahren basiert die Sicherheit auf der Schwierigkeit, ein System multivariater Polynomgleichungen über endlichen Körpern zu lösen. Wichtige Beispiele sind:
* **Rainbow**: Ein Signaturschema aus der Familie der Unbalanced Oil‑and‑Vinegar (UOV) Systeme. Rainbow war über Jahre ein Kandidat, wurde aber 2022 durch neue Angriffe gebrochen und daher vom NIST ausgeschlossen.
* **HFE (Hidden Field Equations)** und Varianten: Diese nutzen verdeckte algebraische Strukturen, um komplexe Polynomgleichungen zu verbergen.
Mehrvariatenverfahren bieten potenziell kurze Schlüssel und schnelle Signaturerstellung, doch die Kryptanalyse ist sehr dynamisch; Algorithmen können schnell gebrochen werden, wie das Beispiel Rainbow zeigt.
### Hash‑basierte Kryptografie
Hash‑basierte Signaturen wie **XMSS (eXtended Merkle Signature Scheme)** und **SPHINCS+** verwenden nur kryptografische Hashfunktionen als Bausteine. Sicherheit beruht auf der Kollisionsresistenz der Hashfunktion. Merkmale:
* **XMSS**: Stateful, d. h. nach jeder Signatur muss der interne Zustand aktualisiert werden; geeignet für Firmware‑Updates.
* **SPHINCS+**: Stateless, benötigt keinen Zustand und wurde vom NIST als Standard für digitale Signaturen ausgewählt. Die Signaturen sind relativ groß (bis zu ~17 kB), die Schlüssellängen dagegen moderat.
Diese Verfahren sind sehr robust, da ihre Sicherheit lediglich auf den Annahmen zu Hashfunktionen basiert, und resistent gegen Quantenangriffe außer Grover, der die effektive Sicherheitsstufe halbiert.
### Isogenie‑basierte Kryptografie
Isogenie‑basierte Verfahren nutzen die Schwierigkeit, isogene Abbildungen (Algebra‑Morphismen) zwischen elliptischen Kurven zu berechnen. Bekannt sind:
* **SIDH (Supersingular Isogeny Diffie–Hellman)** und **SIKE (Supersingular Isogeny Key Encapsulation)**: Bieten extrem kleine Schlüssel (unter 500 Byte). Jedoch wurde 2022 ein effizienter Angriff veröffentlicht, der die Sicherheit in Frage stellt. SIKE wurde daher nicht zur Standardisierung ausgewählt.
Trotz der jüngsten Angriffe bleibt die Forschung an isogenie‑basierten Verfahren interessant, da sie einzigartige Eigenschaften (sehr kurze Schlüssel) bieten.
## Standardisierung durch das NIST
Das NIST führt seit 2017 einen mehrstufigen Auswahlprozess durch, um PQC‑Algorithmen als Standard zu etablieren. Ziel ist es, klare Empfehlungen für Verschlüsselungs‑ und Signaturalgorithmen zu geben, damit Behörden und Unternehmen rechtzeitig migrieren können. Der Prozess gliedert sich in „Runden“ mit Kandidaten, Reduzierungen und Analysen.
Im Juli 2022 gab das NIST die ersten vier Gewinner bekannt:
* **CRYSTALS‑Kyber** für öffentliche Schlüssel (KEM)
* **CRYSTALS‑Dilithium** für Signaturen
* **FALCON** für Signaturen (zweite Wahl mit anderen Merkmalen)
* **SPHINCS+** für Signaturen (hash‑basiert)
Diese
## Implementierungsaspekte und Leistungsprofile
Der Umstieg auf PQC ist nicht nur eine Frage der Algorithmuswahl, sondern erfordert auch sorgfältige Implementierung und Systemintegration. Zu beachten sind:
* **Schlüsselgrößen**: Gitterbasierte KEMs benötigen öffentliche Schlüssel im Bereich von 1–3 kB, Code‑basierte bis zu 500 kB. Hash‑basierte Signaturen sind groß (bis 17 kB). Dies beeinflusst Speicherbedarf, Netzwerkbandbreite und Zertifikatgrößen.
* **Leistungsfähigkeit**: Viele PQC‑Verfahren arbeiten mit Vektor‑ und Matrixoperationen und sind gut für Hardwarebeschleunigung geeignet. Allerdings können sie höhere Latenzen aufweisen, insbesondere bei Signaturen.
* **Seitenkanäle**: Die meisten Attacken auf PQC‑Implementierungen zielen auf Seitenkanäle (Timing, Stromverbrauch). Sichere Implementierungen müssen konstante Laufzeiten verwenden und sorgfältig codiert sein.
* **Hybride Ansätze**: Aktuelle Protokolle wie TLS 1.3 unterstützen hybride Schlüsselvereinbarungen: Ein klassisches Verfahren (z. B. ECDHE) wird parallel zu einem PQC‑KEM ausgeführt. Dadurch bleibt die Sicherheit erhalten, wenn einer der Algorithmen gebrochen wird.
* **Hardware‑Integration**: Mikrocontroller und Smartcards müssen PQC‑Algorithmen unterstützen; Forschungsprojekte arbeiten an hardware‑beschleunigter Gitterarithmetik.
## Herausforderungen und offene Fragen
Obwohl PQC große Fortschritte macht, gibt es weiterhin Herausforderungen:
* **Kryptanalyse im Wandel**: Neue Angriffe können vorgeschlagene Verfahren obsolet machen (z. B. Rainbow, SIKE). Flexibilität beim Wechseln von Algorithmen bleibt wichtig.
* **Standardisierungszeitplan**: Es kann Jahre dauern, bis alle relevanten Standards verabschiedet und implementiert sind. In Übergangsperioden sind hybride Lösungen nötig.
* **Kompatibilität**: Legacy‑Systeme müssen aktualisiert werden; Software‑Bibliotheken und Protokolle müssen PQC unterstützen. Dies ist ein langfristiges Unterfangen.
* **Kosten und Ressourcen**: Größere Schlüssel und Signaturen bedeuten höhere Speicher‑ und Übertragungskosten, was insbesondere bei IoT‑Geräten berücksichtigt werden muss.
* **Verwaltung von Zuständen**: Einige hash‑basierte Signaturen sind stateful (z. B. XMSS) und erfordern sorgfältige Handhabung des internen Zustands, um Sicherheit zu gewährleisten.
## Empfehlungen für die Migration
Um sich auf die Ära der Quantencomputer vorzubereiten, sollten Organisationen jetzt handeln:
1. **Bestandsaufnahme durchführen**: Ermitteln Sie, welche kryptografischen Protokolle und Schlüssel im Einsatz sind und welche davon durch PQC gefährdet sind.
2. **Hybride Verfahren nutzen**: Wo möglich, hybride Key‑Exchange und Signaturen verwenden (z. B. ECDHE + Kyber). Dadurch bleibt die Sicherheit erhalten, auch wenn ein Verfahren gebrochen wird.
3. **Flexibilität planen**: Systeme so gestalten, dass neue Algorithmen leicht ersetzt werden können (Crypto‑Agility). Verwenden Sie modulare Kryptobibliotheken.
4. **Verfolgen Sie die Standardisierung**: Bleiben Sie auf dem Laufenden über NIST‑ und IETF‑Entwicklungen und passen Sie frühzeitig Implementierungen an die finalen Parameter an.
5. **Schulungen und Testbed**: Entwickeln Sie Expertise im Team, testen Sie PQC‑Implementierungen in Pilotprojekten und prüfen Sie Kompatibilität mit bestehenden Systemen.
## Fazit
Post‑Quantum‑Kryptografie ist ein essenzieller Baustein, um die Vertraulichkeit und Integrität digitaler Kommunikation in der Zukunft zu gewährleisten. Während Quantencomputer noch nicht groß genug sind, um RSA oder ECC in der Praxis zu brechen, ist die Migration langfristig notwendig – und sie beginnt jetzt. Indem wir robuste Verfahren wie **CRYSTALS‑Kyber** und **Dilithium** einsetzen, hybride Lösungen nutzen und die Entwicklungen im Auge behalten, können wir die Auswirkungen der Quantenrevolution abmildern. Weitere Artikel auf dieser Website bieten Hintergrundwissen zu den quantum‑mechanischen Grundlagen wie [Shor‑Algorithmus](https://quanten-computer.net/shor-algorithmus-wie-quantencomputer-die-primfaktorzerlegung-revolutionieren) und [Grover‑Algorithmus](https://quanten-computer.net/grover-algorithmus-quadratische-beschleunigung-der-suche), damit Sie die Motivation hinter PQC tiefer verstehen.
werden in den kommenden Jahren standardisiert und in Protokolle integriert (z. B. TLS, X.509 Zertifikate). In der vierten Runde laufen noch Kandidaten wie **Classic McEliece**, **BIKE**, **HQC** und **SABER** (eine Variante von Kyber). Je nach Fortschritt der Kryptanalyse könnten zusätzliche Standards entstehen.
Neben NIST arbeiten auch andere Standardisierungsorganisationen an PQC, u. a. die Internet Engineering Task Force (IETF) mit Entwürfen wie **MLS** (Messaging Layer Security) und **Hybrid Public Key Encryption (HPKE)** mit PQC‑Optionen.
andardisierung ausgewählt wurde.
* **FALCON**: Ein weiteres signaturbasiertes Verfahren, das auf der sog. NTRU‑Lattice‑Basis aufsetzt. Es bietet kompaktere Signaturen als Dilithium, erfordert aber Floating‑Point‑Operationen und ist schwieriger zu implementieren.
Vorteile gitterbasierter Verfahren sind die gute Effizienz und die Fähigkeit, sowohl Verschlüsselung als auch Signaturen zu liefern. Die Schlüsselgrößen sind moderat (Kyber‑512: ~800 Byte öffentlicher Schlüssel), allerdings sind Implementierungen anfällig für Seitenkanalangriffe, wenn nicht sorgfältig codiert.