9.3 密碼學的一瞥#

導言：資訊論的保密面#

Shannon 的 1948 論文專注「傳得快、傳得準」，但他在 1949 年發表的《Communication Theory of Secrecy Systems》（源自二戰機密報告）建立了資訊論密碼學：用熵與互資訊定義「完美保密」，並證明 one-time pad 是唯一實現。此後密碼學分為兩大範式：資訊論安全（無條件安全，攻擊者算力無限）與計算安全（攻擊者多項式時間內攻不破）。本節一窺兩者的核心思想，特別關注與編碼理論的交匯（糾錯碼密碼學）與現代通訊中的物理層安全。

完美保密：Shannon 的定義與定理#

定義#

密文 \(C = E_K(M)\) 。完美保密：

密文不洩漏任何訊息資訊——即使攻擊者算力無限。

Shannon 定理（1949）#

完美保密要求金鑰熵至少等於訊息熵：

（證明骨架： \(H(M \mid C) \le H(K \mid C) + \dots\) 與 \(H(C \mid M) \le H(K)\) 的鏈式論證。）One-time pad（OTP）： \(C = M \oplus K\) ， \(K\) 均勻隨機、只用一次，恰好達到等號——唯一「免費午餐」的例外，但金鑰與訊息一樣長，實務上金鑰分發與一次性使用是死穴（1943 年蘇聯 VENONA 破譯即因金鑰重用）。

例題：OTP 的完美性驗證#

\(M\) 為單位元， \(K\) 均勻 \(\{0,1\}\) 。 \(C = M \oplus K\) ：

• \(P(C = 0) = P(M=0, K=0) + P(M=1, K=1) = 0.5\) ——密文均勻，與 \(M\) 無關。
• \(P(M = 0 \mid C = 0) = P(M = 0)\) ：任意先驗下成立（ \(C\) 恆均勻）。
• \(I(M;C) = H(C) - H(C \mid M) = 1 - 1 = 0\) 。✓

對照流密碼重用：兩則訊息用同一 \(K\) ， \(C_1 \oplus C_2 = M_1 \oplus M_2\) ——金鑰的資訊痕跡顯現，互資訊大於零，保密崩潰。

計算安全：從混淆到複雜度#

資訊論安全太貴（ \(H(K) \ge H(M)\) ）。1976 年 Diffie–Hellman 與 1977 年 RSA 開啟公鑰密碼學：安全基於計算難題（因數分解、離散對數），允許密鑰短於訊息，代價是「假設攻擊者沒有超級演算法」。

計算安全的資訊理論語言：攻擊者的優勢（advantage）以統計距離/互資訊定義，但限制其計算資源——「計算互資訊」把 Shannon 量與複雜度類合併。

糾錯碼密碼學：與編碼理論的交匯#

McEliece 公鑰系統（1978）#

Robert McEliece 的提案（與 RSA 同年，幾乎被遺忘 40 年）：

1. 私鑰：秘密選擇可高效解碼的碼（Goppa 碼 \([n, k, d]\) ，7.1–7.3 節的代數結構）及其解碼演算法。
2. 公鑰：碼的生成矩陣經隨機置換與可逆擾動後公開 \(\hat G = S G P\) （偽裝成一般線性碼）。
3. 加密： \(c = m \hat G + e\) （隨機錯誤向量 \(e\) ，重量 \(\le t\) ）。
4. 解密：私鑰持有者用 Goppa 解碼移除 \(e\) 。

安全性：攻擊者看到的是「一般線性碼 + 隨機錯」，而一般線性碼的最大似然解碼是 NP-hard（Berlekamp–McEliece–van Tilborg 1978，6.2 節）——無已知量子攻擊有效加速。McEliece 是 NIST 後量子密碼標準化（2022–2024 選定 Classic McEliece 為候選/入圍）的核心之一：1978 年的編碼理論，在量子威脅時代復活為國家級安全基建。

其他交匯#

• 秘密共享（Shamir 1979）：以 \(\mathbb{F}_q\) 多項式內插分配份額（RS 求值觀點，7.2 節）， \(k\) 份可復原、 \(k-1\) 份零資訊（完美保密的閾值版）。
• RS 碼與零知識：多項式承諾（KZG 2010、FRI 2018）用 RS 求值做「我有一個低次多項式」的簡短證明——現代區塊鏈 rollup 的基礎（7.3 節）。
• 格密碼學（LWE，2005–）：歐氏空間的「編碼」與加性雜訊（8.2 節量化雜訊的表親），是全同態加密與後量子標準（Kyber/Dilithium）的基礎——碼、量化、密碼三線合流。

物理層安全：用通道本身保密#

Wyner（1975）的竊聽通道（wiretap channel）：主通道 \(X \to Y\) 、竊聽通道 \(X \to Z\) ，若主通道更「乾淨」（ \(Z\) 是 \(Y\) 的退化），則無需預共享金鑰即可達到

透過隨機化編碼（同一訊息對應多個碼字，Eve 無法分辨）實現。 secrecy capacity：

例題：竊聽 BSC#

Bob 錯誤率 \(p_B = 0.05\) 、Eve 錯誤率 \(p_E = 0.15\) ：

以 \(R < 0.324\) 的速率可同時給 Bob 零錯誤與 Eve 零資訊。若 \(p_E \ge p_B\) （Eve 更好）， \(C_s = 0\) ——物理層安全需要通道優勢。無線環境中由於衰落差異、定向天線、波束成形，通道優勢可工程化——5G/6G 的物理層安全研究即基於此（10.3 節）。

量子密碼的一瞥#

BB84 協議（Bennett–Brassard 1984）：以量子態（偏振基）傳送金鑰，量子不可克隆定理保證竊聽必然擾動 → 以錯誤率偵測 Eve → 剩餘位元經資訊協調（糾錯碼）與隱私放大（通用雜湊，Shannon 熵的工具）後得資訊論安全金鑰。量子 QKD 的後處理完全建立在資訊理論（第 2–5 章）之上：Slepian–Wolf 協調、互資訊分析、左-右安全不等式。2020s 京滬幹線與衛星墨子號是工程實現。

歷史前因後果#

誰、何時、為什麼#

• 1949 Shannon：完美保密理論（戰時工作的解密發表）。
• 1975 Wyner：竊聽通道。
• 1976 Diffie–Hellman：公鑰革命（計算範式）。
• 1977 RSA；1978 McEliece：碼基公鑰。
• 1979 Shamir：秘密共享。
• 1984 BB84：量子密鑰分發。
• 1997–2005 AES、格密碼 LWE：有限體與格的時代。
• 2016–2024 NIST 後量子標準化：格（Kyber 為 ML-KEM）與碼（HQC 入選 2025、Classic McEliece 候補）並立。

解決了什麼問題#

1. 保密的定義：從「看不懂」升級為可度量的資訊量（ \(I(M;C) = 0\) ）。
2. 安全的兩軸：資訊論（無條件）與計算（有條件）的清晰分野。
3. 無金鑰保密：Wyner 通道與 QKD 證明「物理差異」本身可以承載安全。

引發什麼新問題#

1. 量子威脅：Shor 演算法瓦解 RSA/ECC，後量子遷移是當代工程大事——碼與格乘勢而起。
2. 計算互資訊：如何精確定義「多項式限制下的資訊洩漏」（模擬範式、不可區分性）仍是理論活躍區。
3. AI 安全：側信道與模型竊取的資訊量分析（10.3 節）。

與其他領域的關聯#

數論與代數#

RSA（ \(\mathbb{Z}/N\) 、尤拉定理）、ECC（ \(\mathbb{F}_p\) 橢圓曲線群，9.1 節）、離散對數——公鑰密碼是數論的工程化身；格密碼是代數數論/幾何的新戰場。

編碼理論#

McEliece（碼的難解碼性）、秘密共享（RS 內插）、QKD 後處理（Slepian–Wolf、糾錯）、物理層安全（竊聽通道的隨機編碼，4.3 節技術的保密版）——編碼理論同時是除錯與保密的數學。

機率與資訊論#

完美保密 = 互資訊為零（3.3 節）；隱私放大的剩餘熵 = 熵與 Renyi 熵的工具；計算安全的優勢界 = 統計距離與假設檢定（3.3 節 Stein 引理的密碼版）。

電腦科學#

複雜度類（P/NP、交互證明）、零知識（PCP，7.3 節）、以及密碼學定義的形式化（遊戲式安全、可組合安全）——密碼學是複雜度理論最大的應用輸出。

小結與思考題#

Shannon 的兩面（通訊 + 保密）共用熵與互資訊；完美保密需 \(H(K) \ge H(M)\) ，計算安全以複雜度換取短金鑰；糾錯碼以 NP-hard 解碼性成為後量子候選；物理層安全把「通道優勢」變成資源。資訊理論與密碼學是一體兩面的同一數學。

思考題

1. 證明 OTP 的 \(H(K) \ge H(M)\) 等號情形：若 \(H(K) > H(M)\) 會浪費什麼？
2. 兩次使用同一 OTP 流 \(K\) ：以互資訊量化洩漏 \(I(M_1 M_2; C_1 C_2)\) 與單次使用的差。
3. McEliece 中為什麼要對生成矩陣做置換與擾動（而非直接公開 Goppa 碼）？
4. 竊聽通道例中若 Eve 的通道改進為 \(p_E = 0.04\) ， \(C_s\) 為何？工程上如何恢復正的 \(C_s\) ？（波束成形、開關式發射等。）
5. 對比資訊論安全與 256 位元 AES 的計算安全：什麼場景必須用前者？（政府級長期機密、QKD、秘密共享託管。）

第 9 章完成。最後一章：現代編碼——Turbo、LDPC 與資訊理論的無限擴張。