Kvantová hrubá síla v kryptoanalýze

Kvantový útok hrubou silou na šifrování

Útok metodou úplného prohledání klíčového prostoru se používá, když je množina možných otevřených textů výrazně menší než celý prostor symbolů. Útočník zachytí šifrovaný text od Alice k Bobovi a implementuje dvě funkce: DECRYPT(key, ciphertext) pro dešifrování a ISPLAINTEXT(text) pro ověření, zda text patří do množiny povolených textů. Pokud je šifrování blokové, DECRYPT pracuje po blocích a ISPLAINTEXT akumuluje výsledky.

Pseudokód útoku je jednoduchý:

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

Kritéria ISPLAINTEXT využívají statistiku symbolů, kombinace nebo heuristiky bez databází – kontroly frekvence, entropie nebo jazykové vzory.

Teorie informace pro odhad úspěšnosti

Pro monoalfabetickou šifru odhadujeme pravděpodobnost falešného poplachu:

• LENGTH(plaintext) – délka v bitech
• LENGTH(key) – délka klíče v bitech
• LENGTH(ciphertext) – délka šifrovaného textu v bitech
• ENTROPY(plaintext) – Shannonova entropie otevřeného textu

Podmínky:

• LENGTH(plaintext) ≤ LENGTH(ciphertext)
• Pravděpodobnost falešného průchodu: 2^-(LENGTH(plaintext) - ENTROPY(plaintext))
• Pokud LENGTH(plaintext) - ENTROPY(plaintext) > LENGTH(key), klíč je jednoznačně určen

Pro algoritmy zachovávající délku: při LENGTH(ciphertext) - ENTROPY(plaintext) ≥ LENGTH(key) útok garantovaně najde klíč.

Kvantový přístup k prohledávání

Kvantové výpočty se opírají o superpozici a provázanost qubitů. Registr z N provázaných qubitů je ekvivalentní 2^N klasických stavů. Aritmetiku (sčítání, násobení, posuny) realizují kvantová hradla – transformace unitárních operátorů.

Libovolnou klasickou funkci nad registrem klíčů převedeme na unitární U(K), kde K je superpozice všech klíčů.

Groverův algoritmus pro hledání klíče

Kroky kvantového útoku:

• Inicializujeme registr K délky LENGTH(key) v rovnoměrné superpozici všech klíčů: |K⟩ = (1/√2^{LENGTH(key)}) Σ |key⟩
• Aplikujeme orákulum U(K) = DECRYPT(K, ciphertext), poté ISPLAINTEXT(U(K)): fáze se invertuje pro stavy s ISPLAINTEXT == 0
• Zesílíme amplitudu cílového stavu Groverovým algoritmem: π/4 * √2^{LENGTH(key)} iterací s difúzními operátory a orákulem
• Změříme registr K – kolaps do správného klíče s pravděpodobností ~1

Orákulum vyžaduje implementaci DECRYPT a ISPLAINTEXT jako reverzibilních kvantových obvodů. Pro blokové šifry – po blocích s pomocnými qubity.

// Pseudokód kvantového obvodu (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));
}

Kvadratické zrychlení: O(√2^{LENGTH(key)}) místo O(2^{LENGTH(key)}).

Co je důležité

• Klasika vs. kvantum: Prohledání klíčů 128 bitů na CPU – 10^38 operací; na kvantovém počítači – 10^19.
• Podmínka úspěchu: Redundance otevřeného textu (LENGTH - ENTROPY) > LENGTH(key)/2 pro praktický útok.
• Omezení: Šum v NISQ-systémech vyžaduje korekci chyb; orákulum DECRYPT je složité pro AES-podobné šifry.
• Post-kvantová kryptografie: Přechod na mřížkové, hashovací schémata je nezbytný.
• Praxe: Simulátory Q# / Cirq demonstrují na 20bitových klíčích.

— Editorial Team