1977 - DES 標準化#

案件摘要#

1977 年，美國 NBS（今 NIST）把 IBM 的 Lucifer（見 1970-Lucifer.md）縮短版定為國家標準 DES：64 位元區塊、56 位元金鑰、16 輪 Feistel 結構。這是第一個公開的密碼標準——演算法公開、任何人可檢驗、任何系統可用。DES 統治對稱加密 20 餘年，1998 年被 22 萬美元的機器一天內窮舉破譯（金鑰太短），2001 年由 AES 接任（見 2001-AES.md）——但 DES 的真正遺產是公開標準化這件事本身。

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

1970 年代的商業需求：銀行電子轉帳需要統一的加密標準（每家銀行自己的密碼無法互通）。1973 年 NBS 公開徵求加密標準——第一次政府公開徵求密碼。IBM 提交 Lucifer 縮短版，NSA（國家安全局）介入審查：

金鑰 128 位元 → 縮短為 56 位元（爭議的核心）
S-Box 被秘密修改（設計理由不公開）

1977 年 DES 成為 FIPS 標準。

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

DES 的結構#

16 輪 Feistel（見 1970-Lucifer.md），64 位元區塊、56 位元金鑰：

初始置換 IP：位元重排（無密碼學意義，歷史遺留）
16 輪 Feistel：每輪子金鑰 \(k_i\) （48 位元，由 56 位元主金鑰衍生）
**輪函數 \(F\) **：擴展置換（32→48）→ 與 \(k_i\) XOR → 8 個 S-Box（48→32，6 位元進 4 位元出）→ P 置換
末置換 IP⁻¹

Shannon 的擴散/混淆（見 1949-Shannon保密理論.md）的完整實現：S-Box 混淆、P 置換擴散、16 輪迭代雪崩。

金鑰空間：56 位元的爭議#

\[ 2^{56} \approx 7.2 \times 10^{16} \]

1977 年：不可行（Diffie 與 Hellman 當年即警告「20 年後可窮舉」）
Diffie 的預言（1977）：100 萬美元的機器一天內窮舉
1998 年應驗：EFF 的 Deep Crack 機器（22 萬美元，1536 個晶片）56 小時內窮舉成功
推論：金鑰長度必須預留計算機增長的餘裕——Moore 定律下的密碼學

差分分析的祕密#

1991 年，Biham 與 Shamir 發表差分密碼分析（differential cryptanalysis）：研究「輸入差異 → 輸出差異」的機率傳播：

\[ P(\Delta c = \Delta y \mid \Delta x) = \text{特徵機率（characteristic probability）} \]

選高機率特徵（如 \(2^{-56}\) ），收集明文-密文對，統計過濾出正確金鑰。8 輪 DES 可被 \(2^{14}\) 個選擇明文破。

驚人的發現：NSA 修改後的 DES S-Box 抗差分分析（16 輪需要 \(2^{64}\) 個選擇明文——不可行）——NSA 在 1970 年代就知道差分攻擊，保密了 15 年。縮短金鑰是真的削弱，修改 S-Box 卻是真的強化。

偵探筆記：差分分析的推理是「差異傳播」——不問密文是什麼，只問「輸入差一點時輸出怎麼變」。這個「差異」的思想與 Rejewski 的循環指標（見 1932-Rejewski破譯Enigma.md）、雪崩效應（見 1949-Shannon保密理論.md）同源：密碼的安全性 = 差異的擴散均勻性。

程式碼：DES 的 S-Box 與差分概念#

# DES 的 S-Box（第 1 個，6 位元進 4 位元出）
DES_SBOX = [
    [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
    [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
    [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
    [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13],
]

def sbox(x):
    """6 位元 -> 4 位元：首尾位元選行，中間 4 位元選列"""
    row = ((x >> 5) & 1) << 1 | (x & 1)
    col = (x >> 1) & 0xF
    return DES_SBOX[row][col]

# 差分分析的概念：輸入差異 -> 輸出差異的統計
import collections
def differential_stats(delta_x, trials=100000):
    import random
    stats = collections.Counter()
    for _ in range(trials):
        x = random.getrandbits(6)
        y1, y2 = sbox(x), sbox(x ^ delta_x)
        stats[y1 ^ y2] += 1
    return stats.most_common(3)

random.seed(42)
print(f"Δx=1 的輸出差異分佈：{differential_stats(1)}")
# 差分攻擊找「異常高機率」的輸出差異——NSA 的 S-Box 已將其最小化

3DES：垂死標準的續命#

金鑰太短，對策是三重 DES：

\[ c = E_{k_3}(D_{k_2}(E_{k_1}(m))) \]

有效金鑰 112–168 位元——1990 年代至 2010 年代銀行系統的過渡標準（2023 年 NIST 正式廢止）。

結案 -- 後果與影響#

公開標準化：DES 是第一個公開的密碼標準——Kerckhoffs 原則（見 1883-Kerckhoffs原則.md）的制度化，NIST 的 AES 競賽（見 2001-AES.md）是孫子。
金鑰長度的教訓：Deep Crack 證明 56 位元不夠——Moore 定律下的金鑰預算成為密碼工程的基本功。
差分/線性分析的誕生：1991 差分（Biham–Shamir）、1993 線性（Matsui）——現代密碼分析的兩大支柱，S-Box 設計的科學化。
NSA 的雙面角色：縮短金鑰（削弱）+ 修改 S-Box（強化）——情報機構與密碼學的複雜關係。
密碼戰爭的先聲：DES 的出口管制、Clipper 晶片（1993）——政府 vs 公民的密碼權之爭。

關鍵人物與文獻#

Horst Feistel：Lucifer 原型（見 1970-Lucifer.md）
Walter Tuchman / Carl Meyer：IBM DES 團隊
NSA：金鑰縮短與 S-Box 修改
Whitfield Diffie / Martin Hellman：1977 年的窮舉警告
Biham & Shamir：Differential Cryptanalysis (1991, J. Cryptology)
EFF：Deep Crack (1998)——56 小時破 DES
交叉參照：1970-Lucifer.md、2001-AES.md、1949-Shannon保密理論.md