Quanten-Brute-Force in der Kryptanalyse

Quanten-Brute-Force-Angriff auf Verschlüsselung

Ein Brute-Force-Schlüsselsuchangriff wird angewendet, wenn der Raum möglicher Klartexte deutlich kleiner ist als der gesamte Zeichenraum. Eve fängt einen Geheimtext von Alice an Bob ab und implementiert zwei Funktionen: DECRYPT(Schlüssel, Geheimtext) zur Entschlüsselung und ISPLAINTEXT(Text), um zu prüfen, ob der Text zur Menge gültiger Klartexte gehört. Bei blockbasierter Verschlüsselung arbeitet DECRYPT blockweise, und ISPLAINTEXT sammelt die Ergebnisse.

Der Pseudocode für den Angriff ist einfach:

for each key
    text = DECRYPT(key, ciphertext)
    if ISPLAINTEXT(text) == 0 then return (key,text)
end for

ISPLAINTEXT-Kriterien nutzen Zeichenstatistiken, Kombinationen oder Heuristiken ohne Datenbanken – Prüfungen auf Häufigkeit, Entropie oder Sprachmuster.

Informationstheorie zur Erfolgsbewertung

Für eine monoalphabetische Verschlüsselung schätzen wir die Wahrscheinlichkeit eines falschen Positivs:

• LÄNGE(Klartext) – Länge in Bits
• LÄNGE(Schlüssel) – Schlüssellänge in Bits
• LÄNGE(Geheimtext) – Geheimtextlänge in Bits
• ENTROPIE(Klartext) – Shannon-Entropie des Klartexts

Bedingungen:

• LÄNGE(Klartext) ≤ LÄNGE(Geheimtext)
• Wahrscheinlichkeit eines falschen Durchgangs: 2^-(LÄNGE(Klartext) - ENTROPIE(Klartext))
• Wenn LÄNGE(Klartext) - ENTROPIE(Klartext) > LÄNGE(Schlüssel), ist der Schlüssel eindeutig bestimmt

Für längenbewahrende Algorithmen: Wenn LÄNGE(Geheimtext) - ENTROPIE(Klartext) ≥ LÄNGE(Schlüssel), findet der Angriff garantiert den Schlüssel.

Quantenansatz für Brute-Force

Quantencomputing basiert auf Superposition und Verschränkung von Qubits. Ein Register aus N verschränkten Qubits entspricht 2^N klassischen Zuständen. Arithmetik (Addition, Multiplikation, Verschiebungen) wird mit Quantengattern implementiert – Transformationen unitärer Operatoren.

Jede klassische Funktion über ein Schlüsselregister kann in ein unitäres U(K) transformiert werden, wobei K eine Superposition aller Schlüssel ist.

Grover-Algorithmus zur Schlüsselsuche

Schritte des Quantenangriffs:

• Initialisiere ein Register K der Länge LÄNGE(Schlüssel) in einer gleichmäßigen Superposition aller Schlüssel: |K⟩ = (1/√2^{LÄNGE(Schlüssel)}) Σ |Schlüssel⟩
• Wende das Orakel U(K) = DECRYPT(K, Geheimtext) an, dann ISPLAINTEXT(U(K)): Die Phase wird für Zustände mit ISPLAINTEXT == 0 invertiert
• Verstärke die Amplitude des Zielzustands mit Grovers Algorithmus: π/4 * √2^{LÄNGE(Schlüssel)} Iterationen mit Diffusionsoperatoren und dem Orakel
• Miss Register K – es kollabiert mit Wahrscheinlichkeit ~1 zum korrekten Schlüssel

Das Orakel erfordert die Implementierung von DECRYPT und ISPLAINTEXT als reversible Quantenschaltkreise. Für Blockchiffren – Verarbeitung blockweise mit Hilfsqubits.

// Quantenschaltkreis-Pseudocode (Q#-Stil)
operation BruteForce(keyReg : Qubit[], ciphertext : String) : (Int, String) {
    // Wende H auf alle Qubits für Superposition an
    ApplyToEach(H, keyReg);
    // Orakel: Phasenflip, wenn ISPLAINTEXT(DECRYPT(keyReg, ciphertext)) == 0
    Oracle(keyReg, ciphertext);
    // Grover-Iterationen
    for iter in 0 .. GroverIterations() - 1 {
        GroverDiffusion(keyReg);
        Oracle(keyReg, ciphertext);
    }
    // Messung
    let key = MeasureKey(keyReg);
    return (0, DECRYPT(key, ciphertext));
}

Quadratische Beschleunigung: O(√2^{LÄNGE(Schlüssel)}) statt O(2^{LÄNGE(Schlüssel)}).

Wichtige Erkenntnisse

• Klassisch vs. Quanten: Brute-Force eines 128-Bit-Schlüssels auf einer CPU – 10^38 Operationen; auf einem Quantencomputer – 10^19.
• Erfolgsbedingung: Klartextredundanz (LÄNGE - ENTROPIE) > LÄNGE(Schlüssel)/2 für einen praktischen Angriff.
• Einschränkungen: Rauschen in NISQ-Systemen erfordert Fehlerkorrektur; das DECRYPT-Orakel ist komplex für AES-ähnliche Chiffren.
• Post-Quanten-Kryptografie: Übergang zu gitterbasierten, hashbasierten Verfahren ist essenziell.
• Praxis: Q#-/Cirq-Simulatoren demonstrieren an 20-Bit-Schlüsseln.

— Editorial Team