跳轉到

3.2 區塊加密的觀念與 Feistel 結構#

概念說明#

區塊加密（block cipher）把固定長度的明文區塊（如 64 或 128 位元）在金鑰控制下映射為同長度的密文區塊。理想的區塊加密是一個偽隨機置換（PRP）：對每把金鑰，加密是全體區塊上的某個「看起來完全隨機」的一對一映射。AES 是 128 位元區塊、10/12/14 輪的置換網路；DES 是 64 位元區塊、16 輪的 Feistel 網路。

區塊加密必須可逆（才能解密），但「構造一個既隨機又可逆的函數」很難。1973 年 Horst Feistel 在 IBM 的 Lucifer 計畫中提出一個天才解法：用任意（可以完全不可逆的）輪函數 F，搭出可逆的加密。

Feistel 結構#

把 n 位元區塊分成左右兩半 L、R。每一輪：

L' = R
R' = L ⊕ F(R, K_i)

解密只需把輪次倒過來做，用同一個 F：因為 R = L'、L = R' ⊕ F(L', K_i)，下一輪狀態完全可還原——F 根本不需要可逆。這意味著我們可以放心使用 S-box、XOR、位移等任何混亂手段，只要求它們「够亂」。

演算法步驟（r 輪 Feistel）#

  1. 金鑰排程（key schedule）由主金鑰產生 r 把輪金鑰 K_1..K_r。
  2. 加密：區塊分成 L_0、R_0；第 i 輪計算 (L_i, R_i) = (R_{i-1}, L_{i-1} ⊕ F(R_{i-1}, K_i))。
  3. 最後一輪後通常不交換左右半（方便用同一電路解密）。
  4. 解密：同樣流程但輪金鑰逆序使用。

Python 教學版 Feistel 實作#

import hashlib

def F(right: bytes, round_key: bytes) -> bytes:
    """輪函數：教學用，取雜湊當偽隨機函數（不可逆也沒關係）。"""
    return hashlib.sha256(right + round_key).digest()[:len(right)]

def feistel(block: bytes, keys: list[bytes], encrypt: bool = True) -> bytes:
    half = len(block) // 2
    L, R = block[:half], block[half:]
    if not encrypt:
        keys = keys[::-1]          # 解密：輪金鑰逆序
    for k in keys:
        L, R = R, bytes(l ^ f for l, f in zip(L, F(R, k)))
    return R + L                    # 交換左右輸出

key = b"secret-key"
keys = [hashlib.sha256(key + bytes([i])).digest()[:8] for i in range(4)]
pt = b"HELLO!!!"                 # 8 bytes 區塊
ct = feistel(pt, keys)
print(ct)                        # 亂碼
print(feistel(ct, keys, False))  # b'HELLO!!!'

安全性分析#

  • 輪數要夠多：單輪 Feistel 可被輕易區分於隨機置換（只改變半區）；實務中 DES 用 16 輪，理論上 3~4 輪後 Feistel 才開始具有偽隨機置換的證明性質（Luby-Rackoff 結果）。
  • 輪函數的品質決定一切：F 若有線性或差分偏誤，攻擊者可用差分分析（觀察輸入差如何在各輪傳播）與線性分析（尋找高偏誤的線性近似）累積弱點。DES 的 S-box 設計恰好事先抵禦了當時未公開的差分分析，是密碼設計史的傳奇（3.3 節）。
  • 區塊大小與生日攻擊：區塊太小則在約 2^(n/2) 個區塊後可能出現密文重複洩漏資訊（生日界）；64 位元區塊（DES）在今日大流量下已不安全，這是 AES 改用 128 位元的理由之一。
  • 模式問題：區塊加密每次只加密一個區塊，多區塊必須搭配工作模式（4.2 節）。直接分塊加密（ECB）會洩漏圖案——教學版程式碼同樣僅示範單區塊原理。

再次強調：本節程式碼用 sha256 當輪函數，僅為展示 Feistel 的可逆性結構，不是安全的區塊加密。

練習#

  1. 手算兩輪 Feistel：區塊 0x1234（L=0x12, R=0x34），F(R,K)=R⊕K，K1=0x05、K2=0x07，求密文；再用逆序金鑰還原驗證。
  2. 修改上面的程式，令 F 恆為 0，觀察加密退化成什麼？（答：只是左右交換——體會「安全性全在輪函數」。）
  3. 為什麼 Feistel 解密不需要 F 的反函數？用代數式一步步推導 L = R' ⊕ F(L', K_i) 的還原過程。