10.1 量子電腦對密碼學的威脅#
概念說明#
量子電腦用量子位元（qubit）與疊加、糾纏、干涉三種效應計算。它不是「更快的一般電腦」：對絕大多數計算（包括 AES 的正常操作、雜湊的計算），量子電腦沒有指數加速。真正的威脅來自少數已知量子演算法恰好命中了現代公鑰密碼的數學難題。
攻擊面盤點#
| 密碼學元件 | 安全根基 | 量子威脅 | 結局 |
|---|---|---|---|
| RSA | 大數分解 | Shor：多項式時間 | 全毀 |
| DH / ECDH | 離散對數 / ECDLP | Shor：多項式時間 | 全毀 |
| ECDSA / EdDSA | ECDLP | Shor | 全毀 |
| AES | 無已知結構破法 | Grover：窮舉平方加速 | 削弱：128 位元金鑰 → 64 位元安全 |
| SHA-256 | 無已知結構破法 | Grover + BHT 碰撞加速 | 輕微削弱，仍可用 |
| HMAC | 雜湊 + 金鑰 | 同上 | 仍可用 |
| 對稱 AEAD | 對稱安全 | 無特化攻擊 | 仍可用 |
核心結論：公鑰體系（金鑰交換、簽章）需要整體替換；對稱體系（AES、SHA、HMAC）只需加長參數（如 AES-256）。
什麼時候會來？（Mosca 不等式）#
密碼學家 Mosca 給出著名的決策式：
X + Y > Z ⇒ 現在就必須行動
- X：你的資料需要保密的年數（醫療記錄？30 年）。
- Y：遷移整套系統需要的年數（大型組織實務經驗：5~15 年）。
- Z：大型量子電腦問世的年數（未知，樂觀估計 10~20 年）。
只要 X + Y > Z（對多數機構成立），遷移就必須現在開始——這是「harvest now, decrypt later」攻擊的數學化：攻擊者今天錄存密文，等 Z 年後解密，只要 X > Z−Y 你的歷史資料就輸了。
Python 對照：兩種「難題」的模擬#
# 經典：分解、離散對數都用「指數級搜尋空間」
# 量子（概念模擬）：Shor 用量子傅立葉變換找週期，多項式時間
import math
def period_finding_classical_demo(a, N):
"""Shor 的經典側：找 f(x)=a^x mod N 的週期 r（量子部分提供加速）"""
x, r = 1, 0
seen = {}
while x not in seen:
seen[x] = r
x = x * a % N
r += 1
return seen, r
# Shor 化約為「找週期」：
# 若 r 為偶數且 a^(r/2) ≢ −1 (mod N)，則 gcd(a^(r/2) ± 1, N) 給出非平凡因數
a, N = 2, 15
seen, r = period_finding_classical_demo(a, N)
f1 = math.gcd(pow(a, r // 2, N) - 1, N)
f2 = math.gcd(pow(a, r // 2, N) + 1, N)
print(f"a={a}, N={N}: 週期 r={r}, 分解 → {f1} × {f2}") # 3 × 5
print("Shor 的威脅：量子電腦讓『找週期』從指數級變多項式級")
安全性分析#
- 現階段沒有任何真實密碼被量子電腦破解：2026 年的量子硬體仍無法分解 RSA-2048（估計需數百萬物理 qubit 與錯誤修正），威脅是中期的確定性而非眼前的緊急事件。
- 但遷移本身很慢：協定、函式庫、硬體（HSM、智慧卡）、憑證生態都要動。這正是 NIST 2016 年啟動標準徵集、2024 年才出標準的原因。
- 對稱密碼不是免死金牌：AES-128 在 Grover 下剩 64 位元安全（勉強可攻），AES-256 剩 128 位元（夠用）——「加長」是零成本的保險，今天就該做。
練習#
- 用 Mosca 不等式評估三種資料（網站 Cookie：1 年、病歷：30 年、國家機密：50 年）在 X=10 年保密需求下的行動建議。
- 執行上面的 Shor 經典側程式，換 a=7、N=21 與其他小數，驗證週期法確實能分解；並說明「量子加速」發生在哪一步（週期搜尋）。
- 盤點你自己的專案/系統：哪些地方用了 RSA/ECC（簽章、TLS、JWT），哪些用對稱加密——分別標記「需替換」與「需加長」。