10.2 Shor 與 Grover 演算法的影響#

概念說明#

對密碼學有直接衝擊的量子演算法只有兩個，但威力截然不同：

Shor（1994）：多項式時間解因數分解與離散對數（含橢圓曲線版）——摧毀式攻擊。RSA、DH、ECC 全數失效。
Grover（1996）：對 n 位元搜尋空間提供平方加速——削弱式攻擊。窮舉 2^n 降為約 2^(n/2) 次查詢，對稱密碼金鑰長度「等效減半」。

Shor 演算法的原理（直覺版）#

Shor 把「分解 N」化約為「找函數 f(x) = a^x mod N 的週期 r」（10.1 節的經典側程式已示範）。經典電腦找週期需評估指數多個 x；量子電腦用量子傅立葉變換（QFT）：

把疊加態 Σ|x⟩｜f(x)⟩ 準備好（一次評估所有 x 的 f 值）。
QFT 放大量子態中「以 r 為週期」的干涉結構，測量即以高機率得到含 r 資訊的值。
少數次重測 + 經典後處理（連分數展開）得到 r。

對 DLP 同理：離散對數本質也是找週期（g^x ≡ h），Shor 的變體直接給出 x。橢圓曲線群同樣有 QFT 適用的群結構——ECC 沒有豁免權。

規模需求：分解 RSA-2048 估計需要約 6000 個邏輯 qubit（含錯誤修正即數百萬物理 qubit）——這就是「現在還做不到」的原因，但工程進展是單向的。

Grover 演算法的原理#

在無結構的 n 位元搜尋空間中找目標，Grover 用「疊加 + 振幅放大」：

初始均勻疊加 Σ|s⟩（所有候選同振幅）。
每次迭代：Oracle 反相（目標項振幅變號）→ 平均反轉（整體繞平均翻轉）→ 目標振幅放大。
約 (π/4)·2^(n/2) 次迭代後測量，高機率命中目標。

與窮舉 2^n 相比，這是平方加速：2^128 的 AES-128 金鑰搜尋變為 2^64 次量子查詢——「勉強可行」的邊界。對策便宜得驚人：把金鑰加倍（AES-256 → 2^128 查詢，安全）。

Python：Grover 的經典對照與金鑰長度換算#

import math

def grover_iterations(bits):
    """以位元數估計 Grover 查詢次數（理論值）"""
    n = 2 ** bits
    return round((math.pi / 4) * math.sqrt(n))

def classical_iterations(bits):
    return 2 ** bits

for bits in (56, 80, 128, 256):
    q = grover_iterations(bits)
    c = classical_iterations(bits)
    print(f"{bits:3}-bit: 經典 2^{bits} vs 量子約 2^{bits//2} 次 "
          f"(Grover ≈ {q:.2e})")

# DES（56 位元）在量子下剩 28 位元 → 秒破
# AES-128 → 64 位元 → 危
# AES-256 → 128 位元 → 安全
print("\n對策：對稱金鑰至少 256 位元（AES-256、ChaCha20 金鑰本就是 256 位元）")

# Shor 影響的演示：DLP/分解的經典最佳複雜度 vs 量子
print("\nRSA-2048 分解：經典 GNFS 亞指數 vs Shor 多項式 ~O(n^3 log n) 位元運算")
print("ECDLP-256：經典 Pollard rho 2^128 vs Shor 多項式")

安全性分析#

影響的不對稱：Shor 殺的是「數學結構」（群上的指數/對數），Grover 削的是「暴力空間」。結構可被特化演算法命中，空間只能平方縮——故後量子密碼刻意選擇「無好量子演算法」的結構：格（lattice）、雜湊、編碼、多變數（10.3 節）。
Grover 的實務折扣：量子查詢的平行化並不像經典那樣線性疊加（可逆計算、Oracle 序列化），實際成本還要再乘上錯誤修正開銷；學界普遍認為 AES-256 在量子時代綽綽有餘。
雜湊的碰撞：Grover 給前像 2^(n/2)；BHT 演算法對碰撞約 2^(n/3)——SHA-256 的碰撞安全 128 位元 → 量子下約 85 位元，仍可接受，但簽章應用傾向 SHA-384/512 以留餘裕。

練習#

計算：以 Grover 破解 80 位元金鑰需多少次量子查詢？換算成「每秒 10^6 次查詢的量子機器」需多少年？
說明為什麼「AES-GCM 用 256 位元金鑰」就能完整應對量子時代，而「RSA-4096」不能？（對比 Grover 的平方加速與 Shor 的多項式破解）
用 10.1 節的週期法程式，對 N=77、a=5 找週期並分解；解釋 QFT 如何把「逐項試探找週期」變成「一次疊加測量」。