📚 课程目录第2章古典密码算法

2. 古典密码算法：原理与破译方法

古典密码算法是密码学的基石，尽管在现代计算能力面前已不再安全，但其设计思想——替换与换位——至今仍是所有对称密码的核心。本章深入剖析四种最具代表性的古典密码：凯撒密码、维吉尼亚密码、仿射密码和 Playfair 密码，并系统讲解其破译方法。

2.1 凯撒密码 (Caesar Cipher)

2.1.1 原理

凯撒密码是最古老的替换密码之一，属于单表替换密码。其加密过程是将明文中的每个字母在字母表上向后（或向前）移动一个固定的位数 k（密钥）。解密时则反向移动相同的位数。

  数学定义： 设字母 A-Z 对应数字 0-25，密钥为 k (0 ≤ k ≤ 25)。

  加密：E(x) = (x + k) mod 26

  解密：D(y) = (y - k) mod 26

2.1.2 破译方法

凯撒密码的密钥空间极小（仅有 26 种可能），破译方法非常直接：

暴力穷举法：尝试所有 26 种可能的偏移量，观察解密结果中是否有可读的英文文本。
频率分析法：统计密文中字母出现的频率，与英文自然语言中字母的标准频率（如 E、T、A、O 等高频字母）进行比对，快速定位偏移量。

实战技巧： 在英文中，字母 'E' 的出现频率约为 12.7%。如果密文中某个字母的出现频率最高，它极有可能对应明文中的 'E'。计算该字母与 'E' 的差值，即可得到密钥 k。

2.2 维吉尼亚密码 (Vigenère Cipher)

2.2.1 原理

维吉尼亚密码是凯撒密码的升级版，属于多表替换密码。它使用一个关键词作为密钥，根据关键词中每个字母对应的偏移量，对明文中对应位置的字母进行凯撒式移位，从而有效抵抗简单的频率分析。

  加密过程：

  1. 将关键词重复书写，使其长度与明文相同。

  2. 对于明文的第 i 个字母，使用关键词第 i 个字母对应的数字作为偏移量进行凯撒加密。

  公式： E(xi) = (xi + ki) mod 26

2.2.2 破译方法

破译维吉尼亚密码的关键在于确定密钥长度，然后将其分解为多个独立的凯撒密码进行破解。

卡西斯基测试 (Kasiski Examination)：寻找密文中重复出现的字母组，计算它们之间的距离。这些距离的最大公约数（GCD）很可能是密钥长度的整数倍。
重合指数法 (Index of Coincidence, IC)：计算密文的重合指数。对于随机文本，IC ≈ 0.038；对于英文文本，IC ≈ 0.065。通过尝试不同的密钥长度，当分组后的 IC 值接近 0.065 时，该长度即为正确的密钥长度。
频率分析：确定密钥长度后，将密文按密钥长度分成若干组，每组对应一个凯撒密码，分别进行频率分析即可破解。

安全警示： 维吉尼亚密码曾被认为是“不可破译的”，但卡西斯基测试和重合指数法的出现彻底终结了这一神话。现代密码学中，任何依赖固定密钥重复使用的密码都是不安全的。

2.3 仿射密码 (Affine Cipher)

2.3.1 原理

仿射密码是凯撒密码的推广，也是一种单表替换密码。其加密函数采用线性变换的形式：E(x) = (a * x + b) mod 26。其中，a 和 b 是密钥，且 a 必须与 26 互质（即 gcd(a, 26) = 1），以保证加密函数是双射的，从而能够唯一解密。

  数学定义：

  加密：E(x) = (a * x + b) mod 26

  解密：D(y) = a-1 * (y - b) mod 26

  其中 a-1 是 a 在模 26 下的乘法逆元。

2.3.2 破译方法

仿射密码的密钥空间为 φ(26) * 26 = 12 * 26 = 312 种，虽然比凯撒密码大，但仍可通过暴力穷举或已知明文攻击轻松破解。

暴力穷举法：尝试所有 312 种可能的 (a, b) 组合，检查解密结果是否为有意义的英文。
已知明文攻击：如果已知两个字母的对应关系，可以列出两个线性方程，直接解出 a 和 b。
频率分析：与凯撒密码类似，但需要先确定 a 的值。可以通过分析高频字母的对应关系来缩小 a 的范围。

关键点： 仿射密码的安全性依赖于 a 与 26 互质。如果 a 不与 26 互质，则加密函数不是一一映射，会导致多个明文对应同一个密文，无法正确解密。

2.4 Playfair 密码 (Playfair Cipher)

2.4.1 原理

Playfair 密码是第一种实用的双字母替换密码（Digraph Substitution Cipher）。它使用一个 5x5 的密钥矩阵（由关键词生成，合并 I 和 J），将明文按双字母分组进行加密。

  加密规则（基于 5x5 矩阵）：

如果两个字母在同一行，则分别替换为各自右侧的字母（循环）。

如果两个字母在同一列，则分别替换为各自下方的字母（循环）。

如果两个字母不在同一行也不在同一列，则替换为以它们为顶点的矩形的另外两个角上的字母（同行交换）。

2.4.2 破译方法

Playfair 密码比单表替换密码更难破解，但仍有多种有效的攻击方法：

频率分析（双字母频率）：统计密文中双字母组合（Digraph）的频率，与英文中常见的双字母（如 TH、HE、IN、ER）进行比对。
已知明文攻击：如果已知部分明文-密文对，可以反向推导出密钥矩阵的结构。
猜测关键词：Playfair 密码的安全性完全依赖于密钥矩阵的保密性。如果攻击者能猜出或通过社会工程学获取关键词，即可轻松解密。

局限性： Playfair 密码无法加密双字母重复出现的模式（如 LL），且加密后的密文仍然保留了明文的某些统计特征，因此对于现代计算能力来说是不安全的。

2.5 四种古典密码对比总结

密码算法	类型	密钥空间	主要破译方法	安全性评价
凯撒密码	单表替换	26	暴力穷举、频率分析	极低，可瞬间破译
维吉尼亚密码	多表替换	26^L (L 为密钥长度)	卡西斯基测试、重合指数法	低，可被系统化破译
仿射密码	单表替换	312	暴力穷举、已知明文攻击	极低，密钥空间过小
Playfair 密码	双字母替换	25! ≈ 2⁸⁴ (理论)	双字母频率分析、已知明文攻击	中等，可被频率分析削弱

2.6 本章小结

古典密码算法虽然简单，但它们是理解现代密码学中混淆与扩散概念的绝佳起点。凯撒密码和仿射密码展示了单表替换的脆弱性；维吉尼亚密码引入了多表替换的思想，但未能解决密钥重复使用的根本问题；Playfair 密码则通过双字母加密提高了安全性，但仍无法抵抗基于统计的攻击。这些算法的破译方法——尤其是频率分析——是密码分析学的基石，至今仍在许多现代密码攻击中发挥着重要作用。