跳轉到

4.1 AES 的結構與運作#

概念說明#

AES（Advanced Encryption Standard）原名 Rijndael，由比利時學者 Daemen 與 Rijmen 設計，2001 年經 NIST 公開競賽（15 個候選、全球密碼學界數年分析）選為標準。它是 128 位元區塊的 SPN（Substitution–Permutation Network）結構，金鑰長度 128/192/256 位元，對應 10/12/14 輪。

SPN 與 Feistel 的差別：SPN 的每一輪整個區塊都同時經過替換與混合（而非只動半區），因此同樣安全性下輪數更少、速度更快；代價是解密需要逆元件（Feistel 只需逆序金鑰）。

每一輪的四個步驟#

狀態（state）是 4×4 的位元組矩陣。每一輪（除最後一輪略去 MixColumns）：

  1. SubBytes（位元組替換）：每個位元組經 16×16 的 S-box 查表替換。S-box 基於 GF(2^8) 的乘法反元素加仿射變換，是數學上可論證的非線性，非任意挑選。提供混淆（confusion）。
  2. ShiftRows（列移位）：第 i 列循環左移 i 個位元組。讓同一列的位元組在下一輪分散到不同欄。提供擴散（diffusion）的第一半。
  3. MixColumns（欄混合）：每欄（4 位元組）視為 GF(2^8) 多項式，乘上一個固定多項式。使輸入的一個位元組變化影響整欄。擴散的第二半——連續兩輪後，一個位元組的改變影響全部 16 位元組（雪崩效應）。
  4. AddRoundKey（輪金鑰 XOR）：與擴張金鑰（key expansion 由主金鑰產生 4×(輪數+1) 個字）做 XOR，這是唯一引入金鑰的步驟。

設計哲學即 Shannon 的 confusion + diffusion：SubBytes 混淆（金鑰與密文的複雜關係），ShiftRows/MixColumns 擴散（單位元變化快速散開），多輪疊代後達到偽隨機外觀。

Python 實作（三種層次）#

# 1) 最低層：用 pycryptodome（實務推薦）
from Crypto.Cipher import AES
import os

key = os.urandom(16)                     # AES-128
cipher = AES.new(key, AES.MODE_GCM)
ct, tag = cipher.encrypt_and_digest(b"attack at dawn")
print(ct, tag)                           # AEAD：密文 + 認證標籤

# 2) 教學：真實 S-box 的前 16 項（完整 S-box 見 FIPS-197）
SBOX = bytes.fromhex(
    "637c777bf26b6fc53001672bfed7ab76")  # 節錄前16項
def sub_byte(b: int) -> int:
    return SBOX[b]  # 完整版應為 SBOX[b] 查 256 項表

# 3) 觀察雪崩效應：改變金鑰 1 個位元，密文大幅改變
c1 = AES.new(key, AES.MODE_ECB).encrypt(b"A" * 16)
key2 = bytes([key[0] ^ 1]) + key[1:]
c2 = AES.new(key2, AES.MODE_ECB).encrypt(b"A" * 16)
diff = sum(bin(a ^ b).count("1") for a, b in zip(c1, c2))
print(f"改變金鑰 1 bit → 密文改變 {diff}/128 bits")  # 通常接近 64±15

（完整手寫 AES 約需 200 行，含 S-box 生成、GF(2^8) 乘法與金鑰擴張；教材建議先讀規格、再對照 pycryptodome 原始碼。）

安全性分析#

  • 最佳公開攻擊僅能縮減約 2~4 輪（相關金鑰攻擊對 AES-256 減少數輪），對實際輪數完全不構成威脅；AES-128 的 2^128 窮舉在任何可預見的古典算力下不可行（2^128 ≈ 3.4×10^38）。
  • 量子威脅：Grover 演算法（10.2 節）可將窮舉降至約 2^64 次查詢——AES-128 的安全餘裕減半，故後量子時代建議至少使用 AES-256。
  • 實務風險全在周邊：側頻道（時間、電力、快取洩漏）需要常數時間實作；模式選用錯誤（ECB、IV 重用）是真實世界 AES 破解案例的絕大多數來源。這正是下一節的主題。

練習#

  1. 解釋為什麼 AES 只需要 SubBytes 一個非線性元件，而 Feistel（如 DES）需要 8 個 S-box？
  2. 用程式驗證雪崩效應：固定金鑰，改變明文 1 個位元，統計 10 次實驗密文平均改變的位元數，是否接近理論值 64。
  3. 查閱 NIST FIPS-197 規格書，寫出 MixColumns 中常數 03 乘上一個位元組在 GF(2^8) 的展開式（用 xtime：03·b = b ⊕ xtime(b)）。