Kwantowa brutalna siła w kryptoanalizie

Kwantowy atak brute force na szyfrowanie

Atak metodą pełnego przeglądu kluczy stosuje się, gdy przestrzeń możliwych tekstów jawnych jest znacznie mniejsza niż cała przestrzeń symboli. Ewa przechwytuje szyfrogram od Alicji do Boba i implementuje dwie funkcje: DECRYPT(klucz, szyfrogram) do odszyfrowania oraz ISPLAINTEXT(tekst) do sprawdzenia przynależności do zbioru dopuszczalnych tekstów. Jeśli szyfrowanie jest blokowe, DECRYPT działa na blokach, a ISPLAINTEXT agreguje wyniki.

Pseudokod ataku jest prosty:

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

Kryteria ISPLAINTEXT wykorzystują statystykę symboli, kombinacje lub heurystyki bez baz danych — sprawdzają częstotliwość, entropię lub wzorce językowe.

Teoria informacji do oceny sukcesu

Dla szyfru monoalfabetycznego szacujemy prawdopodobieństwo fałszywego trafienia:

• LENGTH(plaintext) — długość w bitach
• LENGTH(key) — długość klucza w bitach
• LENGTH(ciphertext) — długość szyfrogramu w bitach
• ENTROPY(plaintext) — entropia Shannona tekstu jawnego

Warunki:

• LENGTH(plaintext) ≤ LENGTH(ciphertext)
• Prawdopodobieństwo fałszywego przejścia: 2^-(LENGTH(plaintext) - ENTROPY(plaintext))
• Jeśli LENGTH(plaintext) - ENTROPY(plaintext) > LENGTH(key), klucz jest jednoznacznie określony

Dla algorytmów zachowujących długość: przy LENGTH(ciphertext) - ENTROPY(plaintext) ≥ LENGTH(key) atak gwarantuje znalezienie klucza.

Podejście kwantowe do przeglądu

Obliczenia kwantowe opierają się na superpozycji i splątaniu kubitów. Rejestr z N splątanych kubitów odpowiada 2^N stanom klasycznym. Arytmetykę (dodawanie, mnożenie, przesunięcia) realizują bramki kwantowe — transformacje operatorów unitarnych.

Każdą funkcję klasyczną na rejestrze kluczy przekształcamy w unitarny U(K), gdzie K — superpozycja wszystkich kluczy.

Algorytm Grovera do wyszukiwania klucza

Kroki ataku kwantowego:

• Inicjalizujemy rejestr K długości LENGTH(key) w jednolitej superpozycji wszystkich kluczy: |K⟩ = (1/√2^{LENGTH(key)}) Σ |key⟩
• Stosujemy wyrocznię U(K) = DECRYPT(K, ciphertext), następnie ISPLAINTEXT(U(K)): faza jest odwracana dla stanów z ISPLAINTEXT == 0
• Wzmacniamy amplitudę stanu docelowego algorytmem Grovera: π/4 * √2^{LENGTH(key)} iteracji z operatorami dyfuzji i wyrocznią
• Mierzymy rejestr K — kolaps do poprawnego klucza z prawdopodobieństwem ~1

Wyrocznia wymaga implementacji DECRYPT i ISPLAINTEXT jako odwracalnych obwodów kwantowych. Dla szyfrów blokowych — na blokach z kubitami pomocniczymi.

// Pseudokod obwodu kwantowego (styl Q#)
operation BruteForce(keyReg : Qubit[], ciphertext : String) : (Int, String) {
    // Apply H to all qubits for superposition
    ApplyToEach(H, keyReg);
    // Oracle: phase flip if ISPLAINTEXT(DECRYPT(keyReg, ciphertext)) == 0
    Oracle(keyReg, ciphertext);
    // Grover iterations
    for iter in 0 .. GroverIterations() - 1 {
        GroverDiffusion(keyReg);
        Oracle(keyReg, ciphertext);
    }
    // Measure
    let key = MeasureKey(keyReg);
    return (0, DECRYPT(key, ciphertext));
}

Przyspieszenie kwadratowe: O(√2^{LENGTH(key)}) zamiast O(2^{LENGTH(key)}).

Co jest ważne

• Klasyka vs kwant: Przegląd kluczy 128 bitów na CPU — 10^38 operacji; na komputerze kwantowym — 10^19.
• Warunek sukcesu: Redundancja tekstu jawnego (LENGTH - ENTROPY) > LENGTH(key)/2 dla praktycznego ataku.
• Ograniczenia: Szum w systemach NISQ wymaga korekcji błędów; wyrocznia DECRYPT jest złożona dla algorytmów typu AES.
• Kryptografia postkwantowa: Przejście na schematy oparte na kratach, funkcjach skrótu jest konieczne.
• Praktyka: Symulatory Q# / Cirq demonstrują na 20-bitowych kluczach.

— Editorial Team