2.2 頻率分析與破密#

概念說明#

頻率分析（frequency analysis）是密碼分析最早的系統性方法，由 9 世紀的 Al-Kindi 提出。核心想法極簡單：自然語言不是隨機的。英文中 E 出現頻率約 12.7%，T 約 9.1%，而 Z 只有 0.07%；更重要的是，只要替代是一對一的（單表替代），這些頻率特徵就會原樣轉移到密文上——密文中最常見的字母，多半就是 E 的化身。

頻率分析是「唯密文攻擊」的典範，其破密流程是所有密碼分析的原型：

1. 統計：計算密文中每個字母（或二元組 bigram、三元組 trigram）的出現次數。
2. 假設：把密文最高頻字母猜為 E、次高頻猜為 T……先猜出 2~3 個高頻字母。
3. 代入：把猜測的對應代入密文，觀察是否出現可辨認的片段（如 TH_、_HE）。
4. 迭代：根據可讀片段推測更多字母（常見字如 THE、AND、THAT 極易確認），反覆修正。
5. 驗證：全文可讀即完成。

英文頻率速查#

常見 trigram：THE（約 3.5%）、AND、ING、ION；常見 bigram：TH、HE、IN、ER。

Python 實作：自動破解單表替代密碼#

以下示範對「移位密碼」做全自動頻率破解（單表替代的一般破解需搜尋置換空間，通常用 hill climbing，見練習 3）：

ENG_FREQ = "ETAOINSHRDLCUMWFGYPBVKJXQZ"  # 由高到低

def score(text: str) -> float:
    """以英文字母頻率排序的相關度為候選明文打分。"""
    from collections import Counter
    letters = [c for c in text.upper() if c.isalpha()]
    if not letters:
        return -1e9
    common = Counter(letters).most_common(6)
    guess = ''.join(c for c, _ in common)
    # 統計猜出字母在 ETAOIN 中的個數（粗略但有效的啟發式）
    return sum(1 for c in guess if c in "ETAOIN")

def crack_shift(ciphertext: str) -> tuple[int, str]:
    best = (-1e9, None, "")
    for k in range(26):
        pt = ''.join(chr((ord(c) - 65 - k) % 26 + 65)
                     if c.isalpha() else c for c in ciphertext.upper())
        s = score(pt)
        if s > best[0]:
            best = (s, k, pt)
    return best[1], best[2]

cipher = "YMJ QFBJW YMJ BJYYJW"
k, pt = crack_shift(cipher)
print(f"金鑰 = {k}, 明文 = {pt}")  # THE LATER THE WETTER

安全性分析#

• 單表替代在長文本下必死：只要密文夠長（數十字母以上），頻率特徵無法掩蓋。理論上，一個 n 個字母的單表替代密文平均只需約 28 個字母就能唯一確定金鑰（香農的唯一解距離概念）。
• 防禦之道是多表與平滑頻率：維吉尼亞密碼（2.3 節）用多張替代表循環，把單一字母的高峰抹平；而第 3 章的完美保密則要求金鑰與明文等長且隨機，讓密文頻率完全均匀、攜帶零資訊——頻率分析正是理解「完美保密到底難在哪裡」的最好對照。
• 現代啟示：頻率分析的精神——「尋找密文中未被隨機性掩蓋的統計規律」——至今仍是密碼分析的主軸，只是對象從字母頻率換成差分特性、側頻道洩漏等。

練習#

1. 統計一段你選的英文文章（至少 500 字母）的字母頻率，與 ETAOIN 順序比較，列出前 6 名是否吻合。
2. 以下密文由移位密碼產生，用上面的 crack_shift 破解：BLTF DPLZ（提示：答案不是英文也別意外，短文可能有多個候選——這說明唯一解距離的意義）。
3. 進階：寫一個 hill climbing 破解器攻擊一般單表替代（金鑰是 26 字母的置換）：隨機起始金鑰 → 以 trigram 頻率表為評分函數 → 每輪隨機對調兩個字母，分數變高就接受。上網找一份英文 trigram 頻率表配合使用。