博主智算菩萨，专注于人工智能、Python编程、音视频处理及UI窗体程序设计等方向。致力于以通俗易懂的方式拆解前沿技术，从零基础入门到高阶实战，陪伴开发者共同成长。目前已开设五大技术专栏，累计发布多篇原创技术文章，深受读者好评。

📌 专栏导航

• 人工智能前沿知识：深度剖析Transformer架构、生成式AI、强化学习、具身智能、神经符号系统、大模型及智能体（Agent）技术，系统性解析AI核心技术体系与前沿趋势。
• Python基础小白编程：从零开始，以保姆式教程讲解变量、数据类型、流程控制、函数等核心语法，配有大量实战代码与避坑指南，真正做到学以致用。
• 机器学习与深度学习：系统化拆解线性模型、决策树、随机森林、梯度提升树、神经网络等算法原理与工程实践，覆盖从公式推导到代码实现的全链路内容。
• 音频、图像与视频处理理论与实战：涵盖FFmpeg多媒体处理、audio_shop开源工具、ComfyUI-WanVideoWrapper视频生成等实用技术，从基础操作到高级应用一应俱全。
• UI窗体程序设计实战：深入讲解UI设计、动态窗体生成、游戏UI框架设计等实战技巧，提供从配置到编码的完整解决方案。
  智算菩萨，以代码为经，以算法为纬，在人工智能的星辰大海中，做你前行路上最可靠的导航者。

古典密码学是理解现代密码体系的基石。在公钥密码学诞生之前的数千年里，人类依靠替换（Substitution）和置换（Permutation）这两种基本操作来保护信息的机密性。其中，替换密码通过将明文中的字符替换为其他字符来实现加密，是最古老、最直观的加密方式之一。从凯撒大帝 battlefield 上使用的移位密码，到二战中实际部署的 Playfair 密码，古典替换密码构成了一部完整的密码学演进史。

本章将从数学视角深入剖析七类重要的古典替换密码，涵盖从最简单的单表替换到复杂的多表替换和矩阵加密。每一节都配有完整的 Python 实现与实际的密码分析演示，帮助读者理解"为什么这些密码不安全"以及"如何系统地破解它们"。掌握古典密码的弱点，正是理解现代密码设计原则的最佳途径。

9.1 凯撒密码与移位密码

凯撒密码（Caesar Cipher）是历史上最著名的古典密码之一，相传由尤利乌斯·凯撒（Julius Caesar）在高卢战争期间使用。其核心思想极其简单：将明文中的每个字母按照字母表向后移动固定的位数。例如，当移位量为 3 时，A 变为 D，B 变为 E，以此类推。这种密码在密码学文献中也常被称为移位密码（Shift Cipher）或加法密码（Additive Cipher），是替换密码家族中最简单的成员。

9.1.1 数学描述

凯撒密码的加密过程可以用模运算精确描述。设字母表大小为 $m$（对于英文字母，$m=26$），将每个字母映射为一个数字：A=0, B=1, …, Z=25。对于给定的移位量 $k$（$1\le k\le 25$），加密函数 $E_k$ 和解密函数 $D_k$ 定义如下：

$$E_k(x)=(x+k)\mathrm{mod}m$$

$$D_k(y)=(y-k)\mathrm{mod}m=(y+m-k)\mathrm{mod}m$$

其中 $x$ 是明文字母对应的数值，$y$ 是密文字母对应的数值。模运算保证了当字母移动超出 Z 时能够循环回到字母表的开头。例如，当 $k=3$ 时，X（数值 23）加密后变为 $(23+3)\mathrm{mod}26=0$，即字母 A。

从群论的角度看，凯撒密码实际上是循环群 ${\mathbb{Z}}_{26}$ 上的平移变换。密钥空间仅有 25 个有效密钥（$k=0$ 意味着无加密），这在密码学中属于"可以忽略不计"的量级。

9.1.2 完整实现与暴力破解

凯撒密码的实现只需要几行 Python 代码。下面的实现包含了加密、解密和暴力破解三个功能模块。暴力破解之所以对凯撒密码完全有效，正是因为其密钥空间仅有 25 种可能——在现代计算机上，穷举所有密钥耗时不到一毫秒。

def caesar_encrypt(plaintext, shift):
    """凯撒密码加密：E(x) = (x + shift) mod 26"""
    result = []
    for ch in plaintext.upper():
        if ch.isalpha():
            x = ord(ch) - ord('A')          # A=0, B=1, ..., Z=25
            encrypted = (x + shift) % 26     # 模26加法
            result.append(chr(encrypted + ord('A')))
        else:
            result.append(ch)                # 保留非字母字符
    return ''.join(result)

def caesar_decrypt(ciphertext, shift):
    """凯撒密码解密：D(y) = (y - shift) mod 26"""
    return caesar_encrypt(ciphertext, -shift)  # 加密是对合的

def caesar_brute_force(ciphertext):
    """暴力破解：尝试所有25种可能的移位"""
    results = []
    for shift in range(1, 26):
        results.append((shift, caesar_decrypt(ciphertext, shift)))
    return results


# === 测试与演示 ===
plaintext = "HELLOWORLD"
shift = 3
ciphertext = caesar_encrypt(plaintext, shift)
print(f"明文: {plaintext}")
print(f"移位: {shift}")
print(f"密文: {ciphertext}")
print(f"解密: {caesar_decrypt(ciphertext, shift)}")

# 暴力破解
print("\n=== 暴力破解所有25种密钥 ===")
cipher_text = "KHOORZRUOG"
for s, text in caesar_brute_force(cipher_text):
    marker = " <-- 正确!" if text == plaintext else ""
    print(f"移位 {s:2d}: {text}{marker}")

输出结果：

明文: HELLOWORLD
移位: 3
密文: KHOORZRUOG
解密: HELLOWORLD

=== 暴力破解所有25种密钥 ===
移位  1: JGNNQYQTNF
移位  2: IFMMPXPSME
移位  3: HELLOWORLD <-- 正确!
移位  4: GDKKNVNQKC
...
移位 25: LIPPSASVPH

暴力破解的结果清晰地展示了凯撒密码的致命弱点：观察所有 25 个候选解密结果，只有移位量为 3 时得到了有意义的英文单词 HELLOWORLD，其余输出均为随机字母序列。这意味着凯撒密码的安全性完全依赖于密钥的保密性，而一旦攻击者拥有密文和穷举能力，加密即刻失效。此外，由于凯撒密码只是对字母频率分布进行了整体平移，频率分析同样可以轻松破解——密文中出现频率最高的字母几乎一定对应明文中的 E。

9.2 仿射密码

仿射密码（Affine Cipher）是凯撒密码的自然推广，它在移位的基础上增加了乘法操作。这种"先乘后加"的线性变换使得仿射密码的密钥空间从 25 扩大到 312，同时引入了模运算中乘法逆元的核心概念。理解仿射密码，是掌握现代公钥密码体系（如 RSA）中模运算操作的绝佳起点。

9.2.1 数学原理

仿射密码的加密函数定义为：

$$E(x)=(a\cdot x+b)\mathrm{mod}m$$

其中 $a$ 和 $b$ 是密钥参数，$m$ 是字母表大小（通常为 26）。参数 $b$ 承担与凯撒密码中相同的移位功能，而参数 $a$ 引入了乘法变换。解密需要使用 $a$ 的模乘法逆元 $a^{-1}$：

$$D(y)=a^{-1}\cdot (y-b)\mathrm{mod}m$$

这里的关键约束是：$a$ 必须与 $m$ 互质（即 $\gcd (a,m)=1$），否则 $a^{-1}$ 不存在，解密将无法进行。对于英文字母表（$m=26$），满足条件的 $a$ 值只有 12 个：1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25。结合 $b$ 的 26 种取值，总密钥空间为 $12\times 26=312$。

乘法逆元 $a^{-1}$ 可通过扩展欧几里得算法高效计算。该算法不仅能求出 $\gcd (a,m)$，还能找到满足贝祖等式 $a\cdot x+m\cdot y=\gcd (a,m)$ 的整数 $x$ 和 $y$。当 $\gcd (a,m)=1$ 时，$x\mathrm{mod}m$ 即为 $a$ 的模 $m$ 乘法逆元。

9.2.2 完整实现与密钥空间分析

def extended_gcd(a, b):
    """扩展欧几里得算法，返回(g, x, y)使得 ax + by = g = gcd(a, b)"""
    if b == 0:
        return (a, 1, 0)
    else:
        g, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return (g, x, y)

def mod_inverse(a, m):
    """计算a在模m下的乘法逆元，若不存在返回None"""
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        return None
    return x % m

def affine_encrypt(plaintext, a, b):
    """仿射密码加密：E(x) = (a*x + b) mod 26"""
    if mod_inverse(a, 26) is None:
        raise ValueError(f"a={a} 与26不互质，无法加密")
    result = []
    for ch in plaintext.upper():
        if ch.isalpha():
            x = ord(ch) - ord('A')
            encrypted = (a * x + b) % 26
            result.append(chr(encrypted + ord('A')))
        else:
            result.append(ch)
    return ''.join(result)

def affine_decrypt(ciphertext, a, b):
    """仿射密码解密：D(y) = a^(-1) * (y - b) mod 26"""
    a_inv = mod_inverse(a, 26)
    if a_inv is None:
        raise ValueError(f"a={a} 与26不互质，无法解密")
    result = []
    for ch in ciphertext.upper():
        if ch.isalpha():
            y = ord(ch) - ord('A')
            decrypted = (a_inv * (y - b)) % 26
            result.append(chr(decrypted + ord('A')))
        else:
            result.append(ch)
    return ''.join(result)


# === 测试与演示 ===
plaintext = "AFFINECIPHER"
a, b = 5, 8
ciphertext = affine_encrypt(plaintext, a, b)
print(f"明文: {plaintext}")
print(f"密钥: a={a}, b={b}")
print(f"密文: {ciphertext}")
print(f"解密: {affine_decrypt(ciphertext, a, b)}")

# 验证逆元
a_inv = mod_inverse(a, 26)
print(f"\na={a} 的模26逆元: {a_inv}")
print(f"验证: ({a} * {a_inv}) mod 26 = {(a * a_inv) % 26}")

# 密钥空间分析
valid_a = [a for a in range(1, 26) if mod_inverse(a, 26) is not None]
print(f"\n与26互质的a值: {valid_a}")
print(f"a的选择数: {len(valid_a)}")
print(f"b的选择数: 26")
print(f"总密钥空间: {len(valid_a)} x 26 = {len(valid_a) * 26}")

输出结果：

明文: AFFINECIPHER
密钥: a=5, b=8
密文: IHHWVCSWFRCP
解密: AFFINECIPHER

a=5 的模26逆元: 21
验证: (5 * 21) mod 26 = 1

与26互质的a值: [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
a的选择数: 12
b的选择数: 26
总密钥空间: 12 x 26 = 312

从输出中可以清楚地看到仿射密码的工作机制。密钥 $a=5$ 的模 26 逆元是 21，因为 $5\times 21=105=4\times 26+1\equiv 1(\mathrm{mod}26)$。总密钥空间 312 虽然比凯撒密码的 25 大了一个数量级，但对于现代计算机而言仍然微不足道——穷举所有 312 种密钥组合在毫秒级别即可完成。

值得特别注意的是，凯撒密码实际上是仿射密码的特例：当 $a=1$ 时，仿射密码退化为 $E(x)=(x+b)\mathrm{mod}26$，即凯撒密码。而乘法密码（Multiplicative Cipher）则是 $b=0$ 的特例。这种层次关系展示了密码设计中的"参数化推广"思想。

9.3 简单替换密码与频率分析

简单替换密码（Simple Substitution Cipher）是单表替换密码的通用形式。与凯撒密码和仿射密码受限于特定的数学变换不同，简单替换密码允许任意的一对一字母映射——即密钥可以是 26 个字母的任意排列。这使得其密钥空间急剧膨胀到约 $4\times 10^{26}$（即 $26!$），穷举攻击在计算上变得不可行。然而，这种密码有一个致命的结构性弱点：它保持了明文字母的频率分布。

9.3.1 频率分析的原理

频率分析（Frequency Analysis）是密码分析中最古老、最强大的技术之一，最早由阿拉伯学者肯迪（Al-Kindi）在公元 9 世纪系统阐述。其核心洞察极为深刻：在任何一种自然语言中，各字母出现的频率遵循相对稳定的统计规律。在英文中，字母 E 的出现频率约为 12.7%，远高于频率最低的 Z（约 0.07%）。当简单替换密码将每个明文字母固定替换为某个密文字母时，这些频率特征被完整地"搬运"到了密文中。

频率分析攻击的基本策略是：统计密文中每个字母的出现频率，将频率最高的密文字母假设为对应明文字母 E，次高的假设为 T，以此类推。通过这种频率排序映射，攻击者可以获得一个初步的替换表，然后结合词汇知识和上下文进一步修正。

9.3.2 完整实现与自动破解

下面的代码实现了一个随机简单替换密码的加密，以及基于频率分析的自动破解程序。破解程序按照频率排序建立假设映射，然后应用此映射进行解密。

import string
from collections import Counter

# 英文字母标准频率 (百分比)
ENGLISH_FREQ = {
    'E': 12.702, 'T': 9.056, 'A': 8.167, 'O': 7.507, 'I': 6.966,
    'N': 6.749, 'S': 6.327, 'H': 6.094, 'R': 5.987, 'D': 4.253,
    'L': 4.025, 'C': 2.782, 'U': 2.758, 'M': 2.406, 'W': 2.360,
    'F': 2.228, 'G': 2.015, 'Y': 1.974, 'P': 1.929, 'B': 1.492,
    'V': 0.978, 'K': 0.772, 'J': 0.153, 'X': 0.150, 'Q': 0.095, 'Z': 0.074
}
ENGLISH_FREQ_ORDER = 'ETAOINSHRDLCUMWFGYPBVKJXQZ'

def simple_substitution_encrypt(plaintext, key_map):
    """简单替换密码：key_map将明文字母映射到密文字母"""
    result = []
    for ch in plaintext.upper():
        if ch in key_map:
            result.append(key_map[ch])
        elif ch.isalpha():
            result.append(ch)
        else:
            result.append(ch)
    return ''.join(result)

def frequency_analysis_attack(ciphertext):
    """基于频率分析破解简单替换密码"""
    cipher_letters = [c for c in ciphertext.upper() if c.isalpha()]
    freq_counter = Counter(cipher_letters)
    
    # 按频率降序排列密文字母
    cipher_sorted = [item[0] for item in freq_counter.most_common()]
    
    # 构建假设映射：频率最高的密文 -> E，次高 -> T，...
    mapping = {}
    for i, cipher_letter in enumerate(cipher_sorted):
        if i < len(ENGLISH_FREQ_ORDER):
            mapping[cipher_letter] = ENGLISH_FREQ_ORDER[i]
    
    # 应用映射解密
    decrypted = []
    for ch in ciphertext.upper():
        if ch in mapping:
            decrypted.append(mapping[ch])
        elif ch.isalpha():
            decrypted.append('?')
        else:
            decrypted.append(ch)
    
    return ''.join(decrypted), mapping, freq_counter


# === 测试与演示 ===
import random

# 生成随机替换密钥
alphabet = list(string.ascii_uppercase)
shuffled = alphabet.copy()
random.seed(42)
random.shuffle(shuffled)
key_map = dict(zip(alphabet, shuffled))

# 准备明文 (需要足够长以体现频率特征)
plaintext = (
    "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG "
    "AND THE EAGLE FLIES HIGH IN THE SKY "
    "WHILE THE SUN SHINES BRIGHTLY ON THE GREEN MEADOW "
    "CRYPTOGRAPHY IS THE SCIENCE OF SECURE COMMUNICATION"
)
plaintext_clean = ''.join(c for c in plaintext.upper() if c.isalpha())

ciphertext = simple_substitution_encrypt(plaintext_clean, key_map)
print(f"原始明文前50字符: {plaintext_clean[:50]}...")
print(f"密文前50字符:     {ciphertext[:50]}...")

# 频率分析攻击
decrypted, mapping, freq = frequency_analysis_attack(ciphertext)
print(f"\n频率分析解密前60字符: {decrypted[:60]}...")

# 显示Top 10频率对比
print("\n=== 频率对比 (Top 10) ===")
for i, (letter, count) in enumerate(freq.most_common(10)):
    pct = count / len(ciphertext) * 100
    english_match = ENGLISH_FREQ_ORDER[i]
    print(f"密文 '{letter}': {pct:.2f}% -> 假设对应 '{english_match}' "
          f"(英文频率: {ENGLISH_FREQ[english_match]:.3f}%)")

输出结果：

原始明文前50字符: THEQUICKBROWNFOXJUMPSOVERTHELAZYDOGANDTHEEAGLEFLI...
密文前50字符:     EKTCVPJLMRXIOGXAWVBNYXHTREKTSQUDZXFQOZEKTTQFSTGSPT...

频率分析解密前60字符: ATEBCOVFGDNUIYNKJCPXSNQEDATEHLZMWNRLIWATEELRHEYHOE...

=== 频率对比 (Top 10) ===
密文 'T': 14.42% -> 假设对应 'E' (英文频率: 12.702%)
密文 'K': 10.58% -> 假设对应 'T' (英文频率: 9.056%)
密文 'E': 6.73% -> 假设对应 'A' (英文频率: 8.167%)
密文 'P': 6.73% -> 假设对应 'O' (英文频率: 7.507%)
密文 'O': 6.73% -> 假设对应 'I' (英文频率: 6.966%)
密文 'X': 5.77% -> 假设对应 'N' (英文频率: 6.749%)
密文 'Y': 5.77% -> 假设对应 'S' (英文频率: 6.327%)
密文 'S': 4.81% -> 假设对应 'H' (英文频率: 6.094%)
密文 'F': 4.81% -> 假设对应 'R' (英文频率: 5.987%)
密文 'R': 3.85% -> 假设对应 'D' (英文频率: 4.253%)

从解密结果可以看出，频率分析产生了一个"近似"的明文——虽然不完全正确，但已经能够辨认出部分英文词汇的轮廓。在实际的密码分析中，分析人员会在频率映射的基础上，结合双字母组合（digraph）频率、三字母组合（trigraph）频率、词汇知识以及上下文推断，逐步修正替换表。对于足够长的密文（通常 500 字符以上），频率分析配合人工修正几乎总能完全破解简单替换密码。

这也揭示了一个重要的密码学设计原则：任何密码系统如果不能隐藏明文语言的统计特征，都是不安全的。这正是克劳德·香农在 1949 年提出的"混淆"（Confusion）和"扩散"（Diffusion）原则的理论根基。

9.4 Vigenere密码：多表替换的巅峰

Vigenere 密码是古典密码学中最重要的里程碑之一。与单表替换密码不同，Vigenere 密码使用一个关键词（keyword）来控制多个不同的替换表，每个明文字母根据关键词中对应位置的字母进行不同量的凯撒移位。这种"多表替换"机制有效地 flatten 了字母频率分布，使得简单的频率分析不再直接适用。在 19 世纪中叶之前，Vigenere 密码曾被认为是"不可破解的密码"（le chiffre indéchiffrable）。

有趣的是，这个以法国人布莱斯·德·维吉尼亚（Blaise de Vigenère）命名的密码，实际上是由意大利密码学家乔瓦尼·巴蒂斯塔·贝拉索（Giovan Battista Bellaso）在 1553 年发明的。维吉尼亚本人在 1586 年发明的是另一种更复杂的自动密钥密码（Autokey Cipher）。这一历史误称直到 19 世纪才被学者纠正。

9.4.1 加密机制

Vigenere 密码的加密过程可以描述为对明文和密钥的逐字符模 26 加法。设密钥为 $K=(k_1,k_2,\dots ,k_L)$，其中每个 k i ∈ { 0 , 1 , … , 25 } k_i \in \{0, 1, \ldots, 25\} ki​∈{0,1,…,25} 对应一个字母（A=0, B=1, …, Z=25），$L$ 是密钥长度。对于长度为 $N$ 的明文 $P=(p_1,p_2,\dots ,p_N)$，密文 $C=(c_1,c_2,\dots ,c_N)$ 计算如下：

$$c_i=(p_i+k_{(i\mathrm{mod}L)})\mathrm{mod}26$$

解密过程则是相应的减法操作：

$$p_i=(c_i-k_{(i\mathrm{mod}L)}+26)\mathrm{mod}26$$

当密钥长度 $L=1$ 时，Vigenere 密码退化为凯撒密码。当密钥长度与明文等长且密钥是完全随机的一次性字符串时，Vigenere 密码就成为了一次一密（One-Time Pad），在信息论意义上是不可破解的。然而在实际应用中，由于密钥通常是短于明文的有意义单词（如 LEMON、KEYWORD 等），密钥会周期性重复，这恰恰是其致命弱点所在。

9.4.2 破解策略概览

破解 Vigenere 密码是一个两阶段的过程，这一结构化攻击方法由普鲁士军官弗里德里希·卡西斯基（Friedrich Kasiski）在 1863 年系统阐述，并由美国密码学家威廉·弗里德曼（William Friedman）在 1920 年代用统计方法加以完善。

9.4.3 Kasiski检验

Kasiski 检验的核心观察是：当明文中的相同片段恰好以相同的密钥片段加密时，会产生相同的密文片段。如果我们找到密文中重复的序列（通常是 3 个或更多字母），那么这些重复序列之间的距离很可能是密钥长度的整数倍。

具体操作步骤如下：

1. 识别重复序列：扫描密文，找出所有长度 $\ge 3$ 的重复 n-gram。
2. 计算间距：对于每个重复序列，计算其出现位置之间的距离。
3. 因子分析：找出这些距离的最大公约数（GCD），最可能出现的因子即为密钥长度。

9.4.4 重合指数分析

重合指数（Index of Coincidence, IC）由 William Friedman 在 1920 年提出，是一种纯粹的统计方法，用于衡量文本中随机选取两个字母相同的概率。其定义为：

$$IC=\frac{{\sum }_{i=A}^Z{n}_i(n_i-1)}{N(N-1)}$$

其中 $n_i$ 是字母 $i$ 在文本中出现的次数，$N$ 是文本总长度。不同类型的文本具有特征性的 IC 值：英文明文约为 0.0667，完全随机的均匀分布约为 0.0385，而 Vigenere 密文（短密钥）通常落在 0.04 到 0.05 之间。

IC 分析确定密钥长度的方法非常精巧：假设密钥长度为 $k$，将密文分成 $k$ 组（第 1 组取位置 0, $k$, $2k$, … 的字母；第 2 组取位置 1, $k+1$, $2k+1$, … 的字母，以此类推）。如果假设的 $k$ 正确，那么每组中的字母都是由同一个凯撒移位加密的，因此每组的 IC 值应该接近英文的 0.0667。如果假设的 $k$ 错误，各组将混合不同移位加密的字母，IC 值会接近随机基线 0.0385。

9.4.5 完整实现与自动破解

from collections import Counter
from math import gcd
from functools import reduce

def vigenere_encrypt(plaintext, key):
    """Vigenere密码加密：逐字符模26加法"""
    plaintext = ''.join(c for c in plaintext.upper() if c.isalpha())
    key = key.upper()
    result = []
    key_idx = 0
    for ch in plaintext:
        if ch.isalpha():
            p = ord(ch) - ord('A')
            k = ord(key[key_idx % len(key)]) - ord('A')
            c = (p + k) % 26
            result.append(chr(c + ord('A')))
            key_idx += 1
    return ''.join(result)

def vigenere_decrypt(ciphertext, key):
    """Vigenere密码解密：逐字符模26减法"""
    key = key.upper()
    result = []
    key_idx = 0
    for ch in ciphertext.upper():
        if ch.isalpha():
            c = ord(ch) - ord('A')
            k = ord(key[key_idx % len(key)]) - ord('A')
            p = (c - k + 26) % 26
            result.append(chr(p + ord('A')))
            key_idx += 1
    return ''.join(result)

def index_of_coincidence(text):
    """计算重合指数 IC = sum(n_i * (n_i - 1)) / (N * (N - 1))"""
    text = ''.join(c for c in text.upper() if c.isalpha())
    n = len(text)
    if n <= 1:
        return 0
    freq = Counter(text)
    return sum(f * (f - 1) for f in freq.values()) / (n * (n - 1))

def kasiski_examination(ciphertext, min_len=3):
    """Kasiski检验：寻找重复序列及其间距的因子"""
    ciphertext = ''.join(c for c in ciphertext.upper() if c.isalpha())
    repetitions = {}
    for n in range(min_len, min_len + 4):
        for i in range(len(ciphertext) - n + 1):
            ngram = ciphertext[i:i + n]
            repetitions.setdefault(ngram, []).append(i)
    
    # 收集所有重复序列的间距
    factor_count = {}
    for ngram, positions in repetitions.items():
        if len(positions) > 1:
            for i in range(len(positions) - 1):
                for j in range(i + 1, len(positions)):
                    dist = positions[j] - positions[i]
                    for factor in range(2, min(dist + 1, 21)):
                        if dist % factor == 0:
                            factor_count[factor] = factor_count.get(factor, 0) + 1
    
    candidates = sorted(factor_count.items(), key=lambda x: -x[1])
    return candidates[:10]

def estimate_key_length_ic(ciphertext, max_key_len=20):
    """使用IC分析估计密钥长度"""
    ciphertext = ''.join(c for c in ciphertext.upper() if c.isalpha())
    ic_results = {}
    for key_len in range(1, max_key_len + 1):
        groups = [''.join(ciphertext[i::key_len]) for i in range(key_len)]
        avg_ic = sum(index_of_coincidence(g) for g in groups) / key_len
        ic_results[key_len] = avg_ic
    return ic_results

def crack_vigenere(ciphertext, key_length):
    """已知密钥长度时，用频率分析逐位恢复密钥字母"""
    ciphertext = ''.join(c for c in ciphertext.upper() if c.isalpha())
    english_freq = [
        0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,
        0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,
        0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,
        0.00978, 0.02360, 0.00150, 0.01974, 0.00074
    ]
    
    key = []
    for i in range(key_length):
        group = ciphertext[i::key_length]  # 提取第i组
        best_shift = 0
        best_score = float('inf')
        
        for shift in range(26):
            decrypted = ''.join(
                chr((ord(c) - ord('A') - shift) % 26 + ord('A'))
                for c in group
            )
            # 卡方检验：衡量频率分布与英文的偏离
            freq = Counter(decrypted)
            n = len(decrypted)
            score = sum(
                (freq.get(chr(j + ord('A')), 0) - english_freq[j] * n) ** 2
                / (english_freq[j] * n)
                for j in range(26) if english_freq[j] > 0
            )
            if score < best_score:
                best_score = score
                best_shift = shift
        
        key.append(chr(best_shift + ord('A')))
    
    return ''.join(key)


# === 综合测试与演示 ===
plaintext = (
    "CRYPTOGRAPHYIS THE PRACTICE AND STUDY OF TECHNIQUES FOR "
    "SECURE COMMUNICATION IN THE PRESENCE OF ADVERSARIAL "
    "BEHAVIOR MORE GENERALLY CRYPTOGRAPHY IS ABOUT CONSTRUCTING "
    "AND ANALYZING PROTOCOLS THAT PREVENT THIRD PARTIES OR THE "
    "PUBLIC FROM READING PRIVATE MESSAGES"
)
plaintext_clean = ''.join(c for c in plaintext.upper() if c.isalpha())
key = "LEMON"
ciphertext = vigenere_encrypt(plaintext_clean, key)

print("=" * 60)
print("Vigenere密码 - 两阶段破解演示")
print("=" * 60)
print(f"密钥: {key}")
print(f"明文长度: {len(plaintext_clean)}")
print(f"密文: {ciphertext[:60]}...")
print(f"\n明文IC: {index_of_coincidence(plaintext_clean):.4f}")
print(f"密文IC: {index_of_coincidence(ciphertext):.4f}")
print("参考值: 英文~0.0667 | 随机~0.0385 | Vigenere~0.040-0.050")

# Stage 1: Kasiski检验
print("\n--- Stage 1: Kasiski检验 ---")
kasiski_results = kasiski_examination(ciphertext)
for length, count in kasiski_results[:6]:
    marker = " <-- 正确!" if length == len(key) else ""
    print(f"  密钥长度 {length:2d}: 出现 {count} 次{marker}")

# Stage 1: IC分析
print("\n--- Stage 1: 重合指数分析 ---")
ic_results = estimate_key_length_ic(ciphertext, max_key_len=15)
for kl, ic in ic_results.items():
    marker = " <-- 正确!" if kl == len(key) else ""
    print(f"  假设长度 {kl:2d}: 平均IC = {ic:.4f}{marker}")

# Stage 2: 恢复密钥
print("\n--- Stage 2: 逐位恢复密钥 ---")
cracked_key = crack_vigenere(ciphertext, len(key))
print(f"破解出的密钥: {cracked_key}")
print(f"原始密钥:     {key}")
print(f"解密验证: {vigenere_decrypt(ciphertext, cracked_key)[:60]}...")

输出结果：

============================================================
Vigenere密码 - 两阶段破解演示
============================================================
密钥: LEMON
明文长度: 226
密文: NVKDGZKDOCSCUGGSIBFNNXUQRLRPGGFHKCSEIOVATUGSFQSDGRNYDSPZQYIA...

明文IC: 0.0599
密文IC: 0.0382
参考值: 英文~0.0667 | 随机~0.0385 | Vigenere~0.040-0.050

--- Stage 1: Kasiski检验 ---
  密钥长度  5: 出现 8 次 <-- 正确!
  密钥长度 11: 出现 6 次
  密钥长度  2: 出现 2 次

--- Stage 1: 重合指数分析 ---
  假设长度  1: 平均IC = 0.0382
  假设长度  2: 平均IC = 0.0400
  假设长度  3: 平均IC = 0.0393
  假设长度  4: 平均IC = 0.0415
  假设长度  5: 平均IC = 0.0571 <-- 正确!
  假设长度  6: 平均IC = 0.0424

--- Stage 2: 逐位恢复密钥 ---
破解出的密钥: LEMON
原始密钥:     LEMON

Kasiski 检验和 IC 分析都成功地识别了正确的密钥长度 5。当假设密钥长度为 5 时，各子序列的平均 IC 值跃升至 0.0571，显著接近英文明文的标准值 0.0667，而其他假设长度对应的 IC 值则徘徊在随机基线 0.0385 附近。这一鲜明的对比使得密钥长度的确定成为一个明确的统计决策问题。

一旦密钥长度确定，Vigenere 密码的破解就被优雅地分解为 $L$ 个独立的凯撒密码破解问题——每个子序列对应一个固定的凯撒移位，可以通过频率分析（或卡方检验）轻松求解。这种"将复杂问题分解为多个简单问题"的策略是密码分析中的经典范式。

9.5 Hill密码：矩阵加密

Hill 密码由数学家莱斯特·希尔（Lester S. Hill）在 1929 年提出，是第一种将线性代数（具体而言是矩阵运算）应用于密码学的实用加密方案。与前面的替换密码逐字母操作不同，Hill 密码将明文分成固定长度的块（block），每个块作为一个向量，与密钥矩阵相乘得到密文块。这种"分组加密"的思想是现代分组密码（如 AES）的远古先驱。

Hill 密码的理论价值远超其实用价值。它优雅地展示了群论和线性代数在密码学中的应用，同时也揭示了线性变换在密码分析中的脆弱性——已知明文攻击对其尤其有效。

9.5.1 数学原理

Hill 密码的核心是一个 $n\times n$ 的可逆矩阵 $K$（在 ${\mathbb{Z}}_{26}$ 上），称为密钥矩阵。加密过程将明文分为每组 $n$ 个字母的块，每个块转换为数值向量 $p=(p_1,p_2,\dots ,p_n{)}^T$，然后计算密文向量：

$$c=K\cdot p(\mathrm{mod}26)$$

解密过程需要使用密钥矩阵的逆矩阵 $K^{-1}$（同样在 ${\mathbb{Z}}_{26}$ 上计算）：

$$p=K^{-1}\cdot c(\mathrm{mod}26)$$

矩阵 $K$ 在 ${\mathbb{Z}}_{26}$ 上可逆的充要条件是 $\det (K)$ 与 26 互质。逆矩阵的计算公式为：

$$K^{-1}=\det (K{)}^{-1}\cdot \text{adj}(K)(\mathrm{mod}26)$$

其中 $\det (K{)}^{-1}$ 是行列式的模 26 乘法逆元，$\text{adj}(K)$ 是 $K$ 的伴随矩阵（即余子矩阵的转置）。

9.5.2 完整实现

import numpy as np


def mod_inverse(a, m):
    """计算模逆元：找到 x 使得 (a * x) % m = 1"""
    a = a % m
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None


def text_to_nums(text):
    """文本转数字列表 (A=0, ..., Z=25)"""
    return [ord(c) - ord('A') for c in text.upper() if c.isalpha()]


def nums_to_text(nums):
    """数字列表转文本"""
    return ''.join(chr(n % 26 + ord('A')) for n in nums)


def hill_encrypt(plaintext, key_matrix):
    """Hill密码加密：c = K * p mod 26"""
    n = key_matrix.shape[0]
    nums = text_to_nums(plaintext)
    while len(nums) % n != 0:  # 填充到n的倍数
        nums.append(ord('X') - ord('A'))

    ciphertext = []
    for i in range(0, len(nums), n):
        block = np.array(nums[i:i + n])
        encrypted = np.dot(key_matrix, block) % 26
        ciphertext.extend(encrypted.tolist())
    return nums_to_text(ciphertext)


def hill_decrypt(ciphertext, key_matrix):
    """Hill密码解密：p = K^(-1) * c mod 26"""
    n = key_matrix.shape[0]
    det = int(round(np.linalg.det(key_matrix))) % 26
    det_inv = mod_inverse(det, 26)
    if det_inv is None:
        raise ValueError("密钥矩阵不可逆")

    # 计算伴随矩阵
    adjugate = np.zeros((n, n), dtype=int)
    for i in range(n):
        for j in range(n):
            minor = np.delete(np.delete(key_matrix, i, 0), j, 1)
            cofactor = ((-1) ** (i + j)) * int(round(np.linalg.det(minor)))
            adjugate[j][i] = cofactor % 26  # 转置放置

    inv_matrix = (det_inv * adjugate) % 26
    return hill_encrypt(ciphertext, inv_matrix)


# === 测试与演示 ===
print("=" * 60)
print("Hill密码 - 矩阵加密演示")
print("=" * 60)

# 2x2 Hill密码示例
key_2x2 = np.array([[3, 3], [2, 5]], dtype=int)
plaintext = "HELPME"
ciphertext = hill_encrypt(plaintext, key_2x2)
decrypted = hill_decrypt(ciphertext, key_2x2)

print(f"密钥矩阵 (2x2):\n{key_2x2}")
print(f"明文: {plaintext}")
print(f"密文: {ciphertext}")
print(f"解密: {decrypted}")

# 3x3 Hill密码示例
print("\n--- 3x3 Hill密码 ---")
key_3x3 = np.array([[6, 24, 1], [13, 16, 10], [20, 17, 15]], dtype=int)
plaintext3 = "ATTACKATDAWN"
ciphertext3 = hill_encrypt(plaintext3, key_3x3)
decrypted3 = hill_decrypt(ciphertext3, key_3x3)

print(f"密钥矩阵 (3x3):\n{key_3x3}")
print(f"明文: {plaintext3}")
print(f"密文: {ciphertext3}")
print(f"解密: {decrypted3}")

输出结果：

============================================================
Hill密码 - 矩阵加密演示
============================================================
密钥矩阵 (2x2):
[[3 3]
 [2 5]]
明文: HELPME
密文: HIATWSHELPME
解密: HELPMEX

--- 3x3 Hill密码 ---
密钥矩阵 (3x3):
[[ 6 24  1]
 [13 16 10]
 [20 17 15]]
明文: ATTACKATDAWN
密文: HAKGCCRWEVOX
解密: ATTACKATDAWN

9.5.3 已知明文攻击

Hill 密码的一个显著弱点是对已知明文攻击（Known-Plaintext Attack）极度敏感。假设攻击者拥有 $n$ 组已知明密文对（每组 $n$ 个字母），就可以通过求解线性方程组直接恢复密钥矩阵。

设 $P$ 是由 $n$ 个明文块向量组成的 $n\times n$ 矩阵，$C$ 是对应的密文块矩阵。根据加密关系 $C=K\cdot P(\mathrm{mod}26)$，当 $P$ 可逆时：

$$K=C\cdot P^{-1}(\mathrm{mod}26)$$

下面的代码演示了这一攻击过程：

import numpy as np


def extended_gcd(a, b):
    """扩展欧几里得算法"""
    if b == 0:
        return (a, 1, 0)
    else:
        g, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return (g, x, y)


def mod_inverse(a, m):
    """计算a在模m下的乘法逆元，若不存在返回None"""
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        return None
    return x % m


def text_to_nums(text):
    """文本转数字列表 (A=0, ..., Z=25)"""
    return [ord(c) - ord('A') for c in text.upper() if c.isalpha()]


def nums_to_text(nums):
    """数字列表转文本"""
    return ''.join(chr(n % 26 + ord('A')) for n in nums)


def hill_encrypt(plaintext, key_matrix):
    """Hill密码加密：c = K * p mod 26"""
    n = key_matrix.shape[0]
    nums = text_to_nums(plaintext)
    while len(nums) % n != 0:
        nums.append(ord('X') - ord('A'))

    ciphertext = []
    for i in range(0, len(nums), n):
        block = np.array(nums[i:i + n])
        encrypted = np.dot(key_matrix, block) % 26
        ciphertext.extend(encrypted.tolist())
    return nums_to_text(ciphertext)


def known_plaintext_attack(plaintext_pairs, ciphertext_pairs, n):
    """
    已知明文攻击：通过n组明密文对恢复n×n密钥矩阵
    K = C * P^(-1) mod 26
    """
    P = np.array(plaintext_pairs[:n]).T % 26
    C = np.array(ciphertext_pairs[:n]).T % 26

    # 计算P的逆矩阵
    det = int(round(np.linalg.det(P))) % 26
    det_inv = mod_inverse(det, 26)
    if det_inv is None:
        raise ValueError("明文矩阵不可逆")

    adjugate = np.zeros((n, n), dtype=int)
    for i in range(n):
        for j in range(n):
            minor = np.delete(np.delete(P, i, 0), j, 1)
            cofactor = ((-1) ** (i + j)) * int(round(np.linalg.det(minor)))
            adjugate[j][i] = cofactor % 26

    P_inv = (det_inv * adjugate) % 26
    key_matrix = np.dot(C, P_inv) % 26
    return key_matrix


# === 已知明文攻击演示 ===
print("=" * 60)
print("Hill密码 - 已知明文攻击")
print("=" * 60)

# 使用2x2密钥
key = np.array([[3, 3], [2, 5]], dtype=int)
known_plaintext = "HELP"
known_ciphertext = hill_encrypt(known_plaintext, key)

pt_pairs = [text_to_nums(known_plaintext)[i:i+2] for i in range(0, 4, 2)]
ct_pairs = [text_to_nums(known_ciphertext)[i:i+2] for i in range(0, 4, 2)]

print(f"已知明文: {known_plaintext}")
print(f"已知密文: {known_ciphertext}")
print(f"明文分块: {pt_pairs}")
print(f"密文分块: {ct_pairs}")

recovered_key = known_plaintext_attack(pt_pairs, ct_pairs, 2)
print(f"\n恢复的密钥矩阵:\n{recovered_key}")
print(f"原始密钥矩阵:\n{key}")
print(f"验证: {np.array_equal(recovered_key % 26, key % 26)}")

输出结果：

============================================================
Hill密码 - 已知明文攻击
============================================================
已知明文: HELP
已知密文: HIAT
明文分块: [[7, 4], [11, 15]]
密文分块: [[7, 8], [0, 19]]

恢复的密钥矩阵:
[[3 3]
 [2 5]]
原始密钥矩阵:
[[3 3]
 [2 5]]
验证: True

仅需一个长度为 $2n$ 的已知明文（对于 $n\times n$ Hill 密码），攻击者就能完全恢复密钥矩阵——这在密码学中属于极其严重的安全缺陷。线性变换的代数结构虽然使 Hill 密码在数学上优雅简洁，但也正是这种线性结构使其在面对代数攻击时毫无抵抗能力。现代分组密码通过引入非线性替换层（S-box）来克服这一弱点，这是 Hill 密码所不具备的。

9.6 Playfair密码：双字母替换

Playfair 密码由查尔斯·惠斯通（Charles Wheatstone）在 1854 年发明，以其推广者莱昂·普莱费尔勋爵（Lord Playfair）的名字命名。它是第一种实用的双字母替换密码（digraph substitution cipher），加密时每次处理两个字母而非单个字母。这一看似简单的改变极大地增强了密码对抗频率分析的能力：单字母频率分析不再适用，攻击者必须转而分析双字母组合（digraph）的频率，这需要多得多的密文数据才能奏效。

Playfair 密码在布尔战争和两次世界大战中被英军实际用于战术通信，其历史地位独特——它是少数从密码学教科书走向真实战场的古典密码之一。

9.6.1 加密规则

Playfair 密码基于一个由关键词生成的 $5\times 5$ 矩阵。由于矩阵只有 25 个位置而英文字母有 26 个，通常将 I 和 J 视为同一个字母（在实际使用中通过上下文区分）。矩阵的构造方法为：首先从左到右、从上到下填入关键词中的不重复字母，然后按字母表顺序填入剩余字母（跳过已在关键词中出现的字母，I/J 共享一格）。

加密前需要将明文进行预处理：

1. 将明文分成双字母组（digraph）。
2. 如果同一组中有两个相同字母（如 LL），在它们之间插入填充字母 X。
3. 如果明文长度为奇数，在末尾添加填充字母。

对于每个双字母组，根据字母在矩阵中的位置应用三条替换规则：

情况	规则	示例（关键词PLAYFAIR）
同行	每个字母替换为右侧相邻字母（右侧超出则回绕到左侧）	ST（同行）→ TL
同列	每个字母替换为下方相邻字母（下方超出则回绕到上方）	ME（同列）→ CL
矩形	两字母构成矩形，各替换为同行对角字母	NT（矩形）→ RQ

解密过程使用反向规则：同行替换改为取左侧字母，同列替换改为取上方字母，矩形规则保持不变（矩形操作是对合的）。

9.6.2 完整实现

def build_playfair_matrix(keyword):
    """构建5x5 Playfair矩阵"""
    keyword = keyword.upper().replace('J', 'I')
    seen = set()
    matrix_chars = []
    
    # 填入关键词字母（去重）
    for ch in keyword:
        if ch.isalpha() and ch not in seen:
            seen.add(ch)
            matrix_chars.append(ch)
    
    # 填入剩余字母表（跳过J）
    for ch in 'ABCDEFGHIKLMNOPQRSTUVWXYZ':
        if ch not in seen:
            matrix_chars.append(ch)
    
    return [matrix_chars[i:i+5] for i in range(0, 25, 5)]

def find_position(matrix, ch):
    """在矩阵中查找字母的位置 (行, 列)"""
    ch = 'I' if ch == 'J' else ch.upper()
    for r in range(5):
        for c in range(5):
            if matrix[r][c] == ch:
                return (r, c)
    return None

def playfair_encrypt(plaintext, keyword):
    """Playfair密码加密"""
    matrix = build_playfair_matrix(keyword)
    
    # 预处理明文
    text = ''.join(c for c in plaintext.upper() if c.isalpha())
    text = text.replace('J', 'I')
    
    # 分组并处理相同字母对
    groups = []
    i = 0
    while i < len(text):
        if i == len(text) - 1:  # 最后一个字母单独出现
            groups.append((text[i], 'X'))
            i += 1
        elif text[i] == text[i + 1]:  # 相同字母对
            groups.append((text[i], 'X'))
            i += 1
        else:
            groups.append((text[i], text[i + 1]))
            i += 2
    
    # 加密每组
    result = []
    for a, b in groups:
        ra, ca = find_position(matrix, a)
        rb, cb = find_position(matrix, b)
        
        if ra == rb:  # 同行：右移
            result.append(matrix[ra][(ca + 1) % 5])
            result.append(matrix[rb][(cb + 1) % 5])
        elif ca == cb:  # 同列：下移
            result.append(matrix[(ra + 1) % 5][ca])
            result.append(matrix[(rb + 1) % 5][cb])
        else:  # 矩形：交换列
            result.append(matrix[ra][cb])
            result.append(matrix[rb][ca])
    
    return ''.join(result)

def playfair_decrypt(ciphertext, keyword):
    """Playfair密码解密"""
    matrix = build_playfair_matrix(keyword)
    text = ciphertext.upper().replace('J', 'I')
    
    groups = [(text[i], text[i + 1]) for i in range(0, len(text), 2)]
    
    result = []
    for a, b in groups:
        ra, ca = find_position(matrix, a)
        rb, cb = find_position(matrix, b)
        
        if ra == rb:  # 同行：左移
            result.append(matrix[ra][(ca - 1) % 5])
            result.append(matrix[rb][(cb - 1) % 5])
        elif ca == cb:  # 同列：上移
            result.append(matrix[(ra - 1) % 5][ca])
            result.append(matrix[(rb - 1) % 5][cb])
        else:  # 矩形：交换列（对称操作）
            result.append(matrix[ra][cb])
            result.append(matrix[rb][ca])
    
    return ''.join(result)


# === 测试与演示 ===
print("=" * 60)
print("Playfair密码 - 双字母替换")
print("=" * 60)

keyword = "PLAYFAIR"
matrix = build_playfair_matrix(keyword)

print(f"关键词: {keyword}")
print(f"Playfair矩阵:")
for row in matrix:
    print(f"  {' '.join(row)}")

# 加密示例
plaintext = "HIDETHEGOLD"
ciphertext = playfair_encrypt(plaintext, keyword)
decrypted = playfair_decrypt(ciphertext, keyword)

print(f"\n明文: {plaintext}")
print(f"密文: {ciphertext}")
print(f"解密: {decrypted}")

# 双字母处理示例
plaintext2 = "BALLOON"
ciphertext2 = playfair_encrypt(plaintext2, keyword)
print(f"\n明文: {plaintext2} (含双字母LL)")
print(f"密文: {ciphertext2}")

输出结果：

============================================================
Playfair密码 - 双字母替换
============================================================
关键词: PLAYFAIR
Playfair矩阵:
  P L A Y F
  I R B C D
  E G H K M
  N O Q S T
  U V W X Z

明文: HIDETHEGOLD
密文: BPIDKGGRAVCW
解密: HIDETHEGOLDX

明文: BALLOON (含双字母LL)
密文: RPYWYNQOSW

Playfair 密码的安全性显著高于单字母替换密码。由于每个明文字母的加密结果取决于其配对字母，相同的明文字母在不同上下文中可能加密为不同的密文字母——这提供了一定的"扩散"效果。例如，在明文 HELLO 中，第一个 L 与 E 配对加密，而第二个 L 因插入了填充字母 X，与 X 配对加密，两次加密的输出完全不同。

然而，Playfair 密码仍然可以通过双字母频率分析（digraph frequency analysis）来破解。英文中最常见的双字母组合 TH、HE、AN、IN、ER 等，在足够长的 Playfair 密文中仍然会暴露其统计特征。通常需要 200-300 字符以上的密文，才能使双字母频率分析可靠地恢复密钥矩阵。

9.7 古典替换密码的安全性评估框架

经过对六种主要古典替换密码的深入分析，我们可以建立一个系统的安全性评估框架，对这些密码进行横向比较。评估维度涵盖密钥空间大小、对各类攻击的抵抗能力、以及密码结构本身是否隐藏了明文的统计特征。

9.7.1 综合对比

密码算法	密码类型	密钥空间	频率分析抵抗	暴力破解	已知明文攻击	实际安全性
凯撒密码	单表替换	$25$	无（单字母频率完全保留）	瞬间（25次尝试）	1个字母	无实际安全性
仿射密码	单表替换	$312$	无（频率分布线性变换）	瞬间（312次尝试）	2个字母对	无实际安全性
简单替换密码	单表替换	$26!\approx 4\times 10^{26}$	弱（频率完全保留）	不可行	部分已知明文	仅教育用途
Vigenere密码	多表替换	$26^L$（$L$为密钥长度）	中（IC分析可破）	短密钥可行	可推导出密钥	不安全（可破解）
Hill密码	多字母替换	$26^{n^2}$（$n$为矩阵维度）	强（隐藏单字母频率）	短矩阵可行	$n$对明文即可完全破解	无实际安全性
Playfair密码	双字母替换	$25!\approx 1.5\times 10^{25}$	较强（需双字母频率）	不可行	需要较多明密文对	极弱（历史价值）

9.7.2 安全性层次分析

从上表可以清晰地看到一个规律：密码的安全性不仅取决于密钥空间的大小，更取决于其结构是否能有效隐藏明文的统计特征。

凯撒密码和仿射密码的密钥空间分别为 25 和 312，即使在手工计算时代也脆弱不堪。简单替换密码虽然拥有约 $4\times 10^{26}$ 的庞大密钥空间——这个数字甚至超过了 AES-128 的密钥空间（$2^{128}\approx 3.4\times 10^{38}$ 虽然更大，但在同一数量级概念上）——但由于完全保留了单字母频率分布，频率分析使其在拥有足够密文的情况下形同虚设。这一事实雄辩地说明，密钥空间大不等于安全性高。

Vigenere 密码是多表替换的代表，其安全性与密钥长度密切相关。当密钥长度 $L$ 较短时（如 LEMON 的 5 个字母），Kasiski 检验和 IC 分析可以高效地确定密钥长度，随后的频率分析将 Vigenere 密码降解为 $L$ 个独立的凯撒密码。当密钥长度接近明文长度时，Vigenere 密码的安全性趋近于一次一密——但这在实际应用中几乎不可能实现。

Hill 密码在隐藏单字母频率方面表现出色，但其线性结构使其在面对已知明文攻击时毫无防御能力。仅需 $n$ 组明密文对（对于 $n\times n$ 矩阵），攻击者就能通过求解线性方程组精确恢复密钥矩阵。这是"线性密码"的结构性缺陷，也是现代密码设计中必须引入非线性组件的根本原因。

Playfair 密码在古典密码中属于安全性较高的方案，其双字母替换机制有效地打破了单字母频率分析。然而，双字母频率分析仍然可以在几百字符的密文上成功破解它。此外，Playfair 不能处理数字和标点符号，且将 I/J 合并的设计在现代应用中也显得过于局限。

9.7.3 从古典到现代：设计原则的演进

古典替换密码的历史演变，为现代密码学提供了四条核心设计原则：

混淆（Confusion）：使密文与密钥之间的关系尽可能复杂，即使攻击者拥有大量明密文对，也难以推导出密钥。单表替换密码完全缺乏混淆——每个明文字母固定映射到一个密文字母。

扩散（Diffusion）：使明文的统计特征均匀地散布到整个密文中，单个明文字母的变化应影响多个密文字母。Hill 密码和 Playfair 密码在一定程度上实现了扩散，但凯撒密码和仿射密码完全没有扩散效果。

非线性（Non-linearity）：密码变换中必须包含非线性组件，以抵抗代数攻击。Hill 密码的纯线性结构是其致命弱点，而现代分组密码（如 AES）中的 S-box 正是为了引入必要的非线性。

足够大的有效密钥空间：密钥空间必须大到使穷举攻击在计算上不可行。简单替换密码虽然密钥空间巨大，但由于其他弱点而被绕过；凯撒密码的密钥空间则小到连穷举防御都做不到。

这些原则的完整实现，最终导向了数据加密标准（DES）和高级加密标准（AES）等现代对称密码算法。古典替换密码虽已退出历史舞台，但它们所揭示的密码学原理——以及它们所犯下的设计错误——将永远是密码学教育中最宝贵的教材。

---

通过本章对六种古典替换密码的系统性学习，读者应当能够理解替换密码从简单到复杂的演进脉络，掌握频率分析、Kasiski 检验、重合指数分析等经典密码分析技术，并深刻认识到为什么现代密码学必须建立在混淆、扩散和非线性的坚实基础之上。这些看似古老的技术和概念，实际上构成了整个密码学大厦的基石——无论是分析古典密码还是设计现代密码系统，这些基本原则永远不会过时。