2001 - AES#

案件摘要#

1997 年 NIST 公開徵求 AES（Advanced Encryption Standard）取代 DES——史上第一次公開的密碼競賽：任何人都能提交方案，全世界密碼學家公開攻擊。2001 年，比利時 Joan Daemen 與 Vincent Rijmen 的 Rijndael 勝出：128 位元區塊、128/192/256 位元金鑰、SPN 結構（不是 Feistel）。AES 至今是全球加密的預設——AES-256 是美國國防級標準，而它的兩位設計者親手破解了 DES 的 S-Box（見 1977-DES.md）。

前因 -- 為什麼會有這個案子#

三重危機逼得 NIST 換掉 DES：

金鑰太短：56 位元被 Deep Crack 一天內窮舉（見 1977-DES.md）
3DES 太慢：三次加密，速度瓶頸
自由軟體的政策衝突：1997 年 Bernstein v. US 政府案——美國出口管制把「符合 40 位元出口限制的加密」視為言論自由；需要國產的、不受出口管制的演算法（AES 不受出口限制）

NIST 的決策：公開競賽。這是 Kerckhoffs 原則（見 1883-Kerckhoffs原則.md）的制度化極致——最好的方案經由全世界的攻擊篩選出來。

線索與推理 -- 數學式、程式、理論#

SPN 結構（非 Feistel）#

Rijndael 是 Substitution-Permutation Network（不是 Feistel，見 1970-Lucifer.md）：

\[ \text{AddRoundKey} \to \text{SubBytes} \to \text{ShiftRows} \to \text{MixColumns} \to \text{AddRoundKey} \to \dots \]

三個操作的分工（Shannon 的擴散/混淆，見 1949-Shannon保密理論.md）：

SubBytes：S-Box 代換（混淆）——AES 的 S-Box 用有限域 \(GF(2^8)\) 的反演 + 仿射變換：

\[ S(x) = \text{Aff}(x^{-1} \bmod \text{irreducible poly}) \]

為何用反演： \(GF(2^8)\) 中的反演有嚴格的代數性質（Davey–Hsu–Shih），非線性度最高，且能給出抵抗差分與線性攻擊的保證（Rijndael 的設計證明：差分均勻性 4、線性相關 0）。

ShiftRows：行內位元循環移位（擴散，跨列）
MixColumns：每列乘以固定矩陣（擴散，跨行）：

\[ M = \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \]

（02、03 是 \(GF(2^8)\) 的元素；矩陣有逆、可逆。）

安全性：可證明的部分#

Rijndael 的設計有代數證明支撐（不像 DES 的 S-Box 是「測試出來的」）：

S-Box 的差分均勻性 = 4、線性相關 = 0：給出對差分與線性分析的下界
MixColumns 的分支數（branch number）= 5：每列擴散最快（4 位元欄的資訊至少 5 輪才完全擴散）
結合 → 差分/線性攻擊需要至少 \(2^{126}\) 選擇明文（128 位元金鑰）

偵探筆記：AES 與 DES 的對比是密碼學設計方法的演進：從「試驗式安全」（DES S-Box）到「可證明安全」（AES 的代數保證）。Rijndael 是第一個設計時就用代數證明其攻擊下界的標準密碼——把密碼設計從工藝推向科學。

程式碼：AES 的 MixColumns 與擴散#

# GF(2^8) 乘法（模 x^8+x^4+x^3+x+1 = 0x11B）
def gf_mul(a, b):
    p = 0
    for _ in range(8):
        if b & 1: p ^= a
        hi = a & 0x80
        a = (a << 1) & 0xFF
        if hi: a ^= 0x1B
        b >>= 1
    return p

# MixColumns：列乘以 M（在 GF(2^8) 上）
def mix_column(col):
    t = col[:]
    for i in range(4):
        col[i] = gf_mul(2, t[i]) ^ gf_mul(3, t[(i+1) % 4]) ^ t[(i+2) % 4] ^ t[(i+3) % 4]
    return col

import random
random.seed(42)
col = [random.randint(0, 255) for _ in range(4)]
print(f"MixColumns: {col} -> {mix_column(col[:])}")

# 雪崩效應：一位元差異經多輪擴散
def one_bit_diffusion(state, rounds=3):
    """概念示範：SubBytes+ShiftRows+MixColumns 後的差異位元數"""
    s = state[:]
    for _ in range(rounds):
        s = [gf_mul(2, b) for b in s]     # 簡化為 MixColumns 的效應
    return bin(s[0] ^ state[0]).count('1')

print("AES-256：128 位元金鑰、10/12/14 輪，差分攻擊需 2^126 選擇明文")

競賽的歷史#

15 個提案進入第一輪，5 個進入決賽（Twofish、Serpent、MARS、RC6、Rijndael）。最終得票：Rijndael 51、Serpent 6、Twofish 7、MARS 29、RC6 0。勝出原因：安全性、性能（軟體與硬體都快：x86 用 AES-NI 指令）、設計的清晰與可證明性。

現況#

AES-128：TLS、磁碟加密、密碼庫的預設
AES-256：美國國防級、對稱加密的終極推薦
AES-NI（2008）：x86 硬體指令，AES 加解密速度達數 GB/s——軟體實作曾被硬體超越的罕例
AES-GCM：TLS 的標準 AEAD 模式（見 1979-CarterWegman通用雜湊.md 的 GHASH）

結案 -- 後果與影響#

公開競賽模式：AES 的公開徵求 → 公開攻擊 → 公開評選——成為密碼標準化的範本（後量子競賽完全照抄，見 2017-後量子密碼學.md）。
全球預設：AES 是互聯網、銀行、政府、軍方的預設對稱加密。
可證明的設計：Rijndael 的代數安全保證——密碼設計從工藝到科學。
硬體加速：AES-NI 讓對稱加密快到不再是瓶頸——公鑰（RSA/ECC）成為新瓶頸。
AES 的攻防：2023 年以來的「AES 側通道」研究（快取時序攻擊）——AES-128 的實作細節仍被研究（軟體 AES 的 cache timing）。

關鍵人物與文獻#

Joan Daemen（1965–）與 Vincent Rijmen（1970–）：比利時 KU Leuven；Rijndael
NIST：AES 競賽 (1997–2001)、FIPS 197
Rijmen & Daemen: AES Submission (1998)
Daemen & Rijmen：The Design of Rijndael (2002)
Bernstein：AES 對攻擊的理論回應（1998 差分分析、1999 線性分析）
交叉參照：1977-DES.md、1970-Lucifer.md、1949-Shannon保密理論.md、2017-後量子密碼學.md