3.3 DES 的歷史與弱點#

概念說明#

DES（Data Encryption Standard）是 1977 年由美國 NBS（今 NIST）公布的聯邦資料加密標準，源自 IBM 的 Lucifer 演算法修改版。它是史上第一個公開、標準化的加密演算法：規格完全公開，任何人都可以實作與分析——Kerckhoffs 原則第一次在國家標準層級被落實。DES 是 64 位元區塊、56 位元金鑰、16 輪 Feistel 網路。

結構概要#

初始排列 IP（一組固定的位元重排，無密碼學意義，純為硬體佈線方便）。
16 輪 Feistel：
每輪把 32 位元右半擴張成 48 位元（E 擴張），與 48 位元輪金鑰 XOR。
通過 8 個 S-box：每個 S-box 把 6 位元壓縮替換為 4 位元——DES 的心臟，唯一引入非線性的元件。
P 排列打亂位元位置，再與左半 XOR。
金鑰排程：56 位元主金鑰經循環位移與壓縮排列產生 16 把 48 位元輪金鑰。
尾端 IP⁻¹（IP 的逆）輸出。

歷史懸案與貢獻#

56 位元金鑰之爭：IBM 原案 128 位元，被 NSA 縮短為 56。動機至今有爭論：1970 年代 NSA 也同時要求（IBM 隨後證實）加強 S-box 的設計以抵禦差分分析——此攻擊 1990 年才被 Biham 與 Shamir 公開，比 NSA 晚了十五年。可見 NSA 當年的密碼分析能力領先公開學界，但他們沒有在演算法裡埋後門，這是「公開受檢驗」模式的第一個成功案例。
窮舉的必然結局：1977 年 Diffie 與 Hellman 即警告 56 位元會被專用硬體窮舉。1998 年 EFF 的 Deep Crack 機器以約 25 萬美元成本、56 小時破解 DES 挑戰賽；今日普通顯示卡分鐘級即可窮舉。56 位元在 1990 年代末已不足夠。

弱點清單#

弱點	說明
金鑰太短（56 位元）	可窮舉，2^56 ≈ 7×10^16 對現代硬體微不足道
區塊太短（64 位元）	生日攻擊：約 32 GB 資料後碰撞洩漏（Sweet32 攻擊）
半位元弱金鑰	4 把弱金鑰加密兩次即還原明文
互補性弱點	金鑰取補數時密文整體取補，可省一半窮舉
ECB 模式	分塊獨立加密洩漏圖案（4.2 節著名的「ECB 企鵝」）

3DES 與退場#

為延續舊系統，業界發明 3DES：C = E_K3(D_K2(E_K1(M)))，有效安全度約 112 位元。但它繼承 64 位元區塊的 Sweet32 弱點、速度慢，NIST 已於 2023 年正式停用（SP 800-131A），2023 年後新系統一律使用 AES。

Python 觀察 ECB 的弱點（用 pycryptodome）#

# pip install pycryptodome
from Crypto.Cipher import DES
from PIL import Image  # pip install pillow
import os

def ecb_encrypt_image(path_in, path_out):
    img = Image.open(path_in).convert("L")
    data = img.tobytes()
    # 補齊到 8 位元組倍數
    data += b"\x00" * (-len(data) % 8)
    key = os.urandom(8)
    ct = DES.new(key, DES.MODE_ECB).encrypt(data)
    Image.frombytes("L", img.size, ct[:img.size[0]*img.size[1]]).save(path_out)
# 對「人像」類圖片，ECB 輸出仍隱約可見輪廓——機密性形同虛設

安全性分析與教訓#

DES 的遺產是雙面的：它證明了「公開標準 + 全球密碼學家攻擊」能產生極耐用的設計（S-box 至今未見實質弱點），同時也示範了標準會被時間打敗——金鑰長度必須為未來算力留餘裕。這兩課直接塑造了 AES 的選拔方式（公開競賽、128 位元起跳，見 4.1 節）與今日的密碼敏捷性（crypto-agility）觀念。

練習#

說明為什麼 3DES 用「E-D-E」而不是「E-E-E」？（提示：K1=K2 時 E-D-E 退化为什麼反而是相容性優點？）
用 pycryptodome 對一段含重複字樣的明文（如 ABCD×8）做 DES-ECB 加密，觀察相同明文區塊產生相同密文區塊的現象，並解釋它如何洩漏資訊。
估算：假設一台機器每秒可比對 10^12 把 DES 金鑰，窮舉 2^56 平均需多久？把答案與「一天」比較，說明為什麼 56 位元已死。