量子暴力破解在密码分析中

量子计算对加密的暴力破解攻击

当可能的明文空间远小于整个字符空间时，会应用暴力密钥搜索攻击。Eve拦截了Alice发送给Bob的密文，并实现两个函数：DECRYPT(key, ciphertext)用于解密，ISPLAINTEXT(text)用于检查文本是否属于有效明文集合。如果加密是基于块的，DECRYPT按块工作，ISPLAINTEXT则累积结果。

攻击的伪代码很简单：

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

ISPLAINTEXT标准使用字符统计、组合或启发式方法，无需数据库——检查频率、熵或语言模式。

成功评估的信息论

对于单表替换密码，我们估计误报的概率：

• LENGTH(plaintext) — 明文长度（比特）
• LENGTH(key) — 密钥长度（比特）
• LENGTH(ciphertext) — 密文长度（比特）
• ENTROPY(plaintext) — 明文的香农熵

条件：

• LENGTH(plaintext) ≤ LENGTH(ciphertext)
• 误通过概率：2^-(LENGTH(plaintext) - ENTROPY(plaintext))
• 如果 LENGTH(plaintext) - ENTROPY(plaintext) > LENGTH(key)，密钥被唯一确定

对于长度保持算法：当 LENGTH(ciphertext) - ENTROPY(plaintext) ≥ LENGTH(key) 时，攻击保证能找到密钥。

暴力破解的量子方法

量子计算依赖于量子比特的叠加和纠缠。N个纠缠量子比特的寄存器相当于2^N个经典状态。算术（加法、乘法、移位）通过量子门实现——即酉算子的变换。

密钥寄存器上的任何经典函数都可以转换为酉算子U(K)，其中K是所有密钥的叠加态。

密钥搜索的Grover算法

量子攻击的步骤：

• 初始化一个长度为LENGTH(key)的寄存器K，使其处于所有密钥的均匀叠加态：|K⟩ = (1/√2^{LENGTH(key)}) Σ |key⟩
• 应用预言机U(K) = DECRYPT(K, ciphertext)，然后ISPLAINTEXT(U(K))：对于ISPLAINTEXT == 0的状态，相位反转
• 使用Grover算法放大目标态的振幅：π/4 * √2^{LENGTH(key)}次迭代，结合扩散算子和预言机
• 测量寄存器K——它以概率~1坍缩到正确密钥

预言机需要将DECRYPT和ISPLAINTEXT实现为可逆量子电路。对于分组密码——按块处理，使用辅助量子比特。

// 量子电路伪代码（Q#风格）
operation BruteForce(keyReg : Qubit[], ciphertext : String) : (Int, String) {
    // 对所有量子比特应用H门以创建叠加态
    ApplyToEach(H, keyReg);
    // 预言机：如果ISPLAINTEXT(DECRYPT(keyReg, ciphertext)) == 0，则相位翻转
    Oracle(keyReg, ciphertext);
    // Grover迭代
    for iter in 0 .. GroverIterations() - 1 {
        GroverDiffusion(keyReg);
        Oracle(keyReg, ciphertext);
    }
    // 测量
    let key = MeasureKey(keyReg);
    return (0, DECRYPT(key, ciphertext));
}

二次加速：O(√2^{LENGTH(key)}) 替代 O(2^{LENGTH(key)})。

关键要点

• 经典与量子对比： 在CPU上暴力破解128位密钥需要10^38次操作；在量子计算机上仅需10^19次。
• 成功条件： 明文冗余度（LENGTH - ENTROPY）> LENGTH(key)/2 时，攻击才实用。
• 局限性： NISQ系统中的噪声需要纠错；DECRYPT预言机对于AES类密码很复杂。
• 后量子密码学： 向基于格、基于哈希的方案过渡至关重要。
• 实践： Q# / Cirq模拟器可在20位密钥上演示。

— Editorial Team