Shors und Grovers Algorithmen erklärt

Quantencomputer führen klassische Algorithmen nicht einfach nur schneller aus – sie nutzen Quantenüberlagerung und Interferenz, um bestimmte Probleme exponentiell schneller zu lösen. Zwei Algorithmen bedrohen den Großteil der eingesetzten Kryptografie: Shor (bricht RSA/ECC) und Grover (schwächt symmetrische Kryptografie und Hashfunktionen).

Shors Algorithmus (1994) löst die ganzzahlige Faktorisierung und den diskreten Logarithmus auf einem Quantencomputer in polynomieller Zeit. Dadurch werden RSA (basiert auf Faktorisierung), Diffie-Hellman (diskreter Logarithmus modulo p) und ECDH/ECDSA (diskreter Logarithmus auf elliptischen Kurven) direkt gebrochen.

Der entscheidende Bestandteil von Shors Algorithmus ist die Quanten-Fourier-Transformation (QFT) – eine exponentiell schnellere Quantenversion der DFT. Bei der Periodenbestimmung identifiziert die QFT die Periode von f(x) = a^x mod N, aus der sich die Faktoren von N mithilfe des GCD ableiten lassen.

Um N zu faktorisieren: (1) Wählen Sie ein zufälliges a < N und prüfen Sie gcd(a,N)=1. (2) Bestimmen Sie mithilfe der QFT die Periode r von f(x)=a^x mod N. (3) Mit hoher Wahrscheinlichkeit liefert gcd(a^{r/2}±1, N) einen nichttrivialen Faktor. Der klassische Schritt benötigt O(log N); die Quanten-Periodenbestimmung benötigt O((log N)^3) – also polynomielle Zeit.

Beste klassische Faktorisierung: GNFS – subexponentiell O(exp((64/9 log N)^{1/3} log log N)^{2/3})). Shors Algorithmus auf einem fehlertoleranten Quantencomputer: polynomiell O((log N)^3). RSA-2048 benötigt etwa 4000 logische Qubits und etwa 10^9 Gatteroperationen. Die heutigen NISQ-Computer verfügen über etwa 1000 verrauschte Qubits – sie stellen noch keine Bedrohung dar.

Grov​​ers Algorithmus (1996) bietet eine quadratische Beschleunigung für die unstrukturierte Suche. Für einen Suchraum mit N Elementen benötigen klassische Algorithmen O(N) Abfragen; Grovers Algorithmus benötigt O(√N). Auf die Kryptografie angewendet: Er bricht n-Bit-Schlüssel der symmetrischen Kryptografie in O(2^{n/2}) statt in O(2^n).

AES-128: klassische Sicherheit 2^128, Grovers Algorithmus reduziert sie auf 2^64 – unsicher gegenüber einem großen Quantencomputer. AES-256: 2^256 → 2^128 – weiterhin sicher. Lösung: Verdoppeln Sie die Größen symmetrischer Schlüssel. Kollisionsresistenz von SHA-256: 2^128 → 2^85 (Geburtstagsangriff + Grover). Präbildresistenz von SHA-256: 2^256 → 2^128 – unproblematisch.

Die aktuellen NISQ-Quantencomputer (IBM Heron: 133 Qubits, Google Sycamore: 70 Qubits) sind für kryptografisch relevante Berechnungen zu klein und zu verrauscht. Schätzungen zufolge kann RSA-2048 mit fehlertoleranten Quantencomputern zwischen 2035 und 2050 gebrochen werden. Angriffe nach dem Muster „heute sammeln, später entschlüsseln“ stellen bereits heute eine Bedrohung dar.

Angreifer sammeln heute verschlüsselten Datenverkehr und speichern ihn. Sobald ein Quantencomputer verfügbar ist, entschlüsseln sie die Daten nachträglich. Dadurch sind langfristig gültige Geheimnisse (geheime Regierungsdaten, medizinische Unterlagen) bereits heute gefährdet. Die Migration zu PQC muss für solche Daten jetzt beginnen.

Gitterprobleme (LWE, SIS), codebasierte Probleme (McEliece), hashbasierte Signaturen (SPHINCS+), multivariate Probleme – es ist kein polynomieller Quantenalgorithmus bekannt, der sie löst. Sie bilden die Grundlage der Post-Quanten-Standards des NIST.

Die PQC-Standards des NIST (ML-KEM, ML-DSA, SLH-DSA) wurden 2024 finalisiert. Organisationen sollten die aktuelle Nutzung kryptografischer Verfahren inventarisieren, langlebige Daten identifizieren und die Bereitstellung von PQC für den Schlüsselaustausch priorisieren (aufgrund von Angriffen nach dem Muster „heute sammeln, später entschlüsseln“ besonders dringend). Für Signaturen bleibt mehr Zeit.

Welche Auswirkungen hat Grovers Algorithmus auf AES-128?

Shors Algorithmus (polynomielle Laufzeit) bricht RSA, DH und ECC. Grovers Algorithmus (quadratische Beschleunigung) halbiert die Stärke symmetrischer Schlüssel. Lösung: Migrieren Sie zu den PQC-Standards des NIST (gitterbasiert). Als Nächstes: CRYSTALS-Kyber KEM.