古典密码的黎明：凯撒与替换密码的千年博弈

公元前50年，高卢战争的白热化阶段，罗马军团的行军速度被一封加密信件彻底改变。这不是普通的军情文书，而是盖乌斯·尤利乌斯·凯撒亲自设计的密码——每个字母被向后移动三个位置。当一名高卢间谍截获这封以“KHOOR”开头的信件时，他面对的是人类历史上第一次有明确记载的军事密码应用。这个简单的移位规则，如同投入静湖的石子，激荡出跨越两千年的密码学涟漪。从古罗马的沙场到阿拉伯帝国的智慧宫，从文艺复兴的意大利城邦到现代数字世界的比特流，一场关于信息保密与破译的永恒博弈就此展开。本章将带您回到这场博弈的起点，揭示替换密码的数学内核，并展示如何用现代计算工具瞬间击穿那些曾被视为铜墙铁壁的古典防线。

一、沙场密语：凯撒密码的军事起源与移位原理

公元前1世纪的罗马共和国，军事征服的版图不断扩张，但信息传递的脆弱性始终是凯撒的心病。投石机可以摧毁城墙，但无法确保军令在途中不被敌方截获。根据历史学家苏埃托尼乌斯在《罗马十二帝王传》中的记载，凯撒发明了一种“简单且极易掌握”的加密方法：将明文中的每个字母替换为字母表中其后第三位的字母。这种现在被称为“凯撒密码”（Caesar cipher）的移位密码（shift cipher），其核心是单表替换密码（monoalphabetic substitution cipher）的最简形式——字母表的一个固定置换。

其数学表达极为简洁。设字母表 $\Sigma = \{A, B, C, ..., Z\}$，对应数值 $0$ 到 $25$。加密函数 $E$ 由密钥 $k \in \{0,1,...,25\}$ 定义： $$E_k(x) = (x + k) \mod 26$$ 其中 $x$ 是明文字母的数值。解密函数 $D$ 则为： $$D_k(y) = (y - k) \mod 26$$ 以凯撒最常用的密钥 $k=3$ 为例，明文“ATTACK”转换为密文“DWWDFK”的过程如下：

• A (0) → D (3)
• T (19) → W (22)
• T (19) → W (22)
• A (0) → D (3)
• C (2) → F (5)
• K (10) → N (13)

```mermaid graph LR A[明文: ATTACK] --> B[字母转数值<br/>0,19,19,0,2,10] B --> C[应用密钥k=3<br/>(x+3) mod 26] C --> D[数值: 3,22,22,3,5,13] D --> E[转回字母<br/>DWWDFK] E --> F[密文: DWWDFK] ```

凯撒密码的军事价值在于其速度与简易性。在缺乏复杂计算设备的古代，士兵只需记住一个简单的移位规则，就能在几分钟内完成加密。然而，其安全性也极其脆弱。字母频率特征被完整保留——英语中字母‘E’的出现频率约为11.16%，在密文中，‘E’的加密形式（若 $k=3$ 则为‘H’）必然成为最高频字母。这种统计特性，如同指纹般印在密文上，等待被敏锐的眼睛发现。

二、智慧宫的突破：阿尔·肯迪与频率分析的诞生

凯撒密码的“铜墙铁壁”在8世纪被一位巴格达的学者彻底粉碎。阿尔·肯迪（Al-Kindi，约801–873），这位被称为“阿拉伯的亚里士多德”的博学家，在著作《破译加密信息手稿》（Risalah fi Istikhraj al-Mu'amma）中，首次系统阐述了频率分析（frequency analysis）的原理。他敏锐地指出：“语言中字母的使用频率各不相同，这种差异是破译替换密码的关键。”

阿尔·肯迪的突破在于将密码学从艺术转变为科学。他提出了一个普适性的攻击模型：对于未知密钥的密文，统计各符号的出现频率，并与目标语言的典型字母频率表进行比对。例如，在阿拉伯语中，字母‘ا’（alif）的频率最高；在英语中，则是‘E’。通过匹配最高频密文字母与最高频明文字母，可以推测密钥 $k$ 的值。若密文中‘X’出现最频繁，而英语‘E’（4）最频繁，则猜测 $k = (x(E) - x(X)) \mod 26$。

这一方法的威力在以下Python模拟中展露无遗。假设我们截获一段使用凯撒密码加密的英文密文：

```python def caesar_encrypt(plaintext, k): ciphertext = "" for char in plaintext.upper(): if char.isalpha(): x = ord(char) - ord('A') y = (x + k) % 26 ciphertext += chr(y + ord('A')) else: ciphertext += char return ciphertext

def frequency_attack(ciphertext, language_freq):

计算密文字母频率

freq = [0] * 26 total = 0 for char in ciphertext: if char.isalpha(): idx = ord(char) - ord('A') freq[idx] += 1 total += 1 if total == 0: return None freq = [f / total for f in freq]

寻找最可能的密钥：使密文频率与语言频率相关性最大

best_k = 0 best_corr = -1 for k in range(26): corr = 0 for i in range(26):

将密文字母i反向移位k，对应明文字母

plain_idx = (i - k) % 26 corr += freq[i] * language_freq[plain_idx] if corr > best_corr: best_corr = corr best_k = k return best_k

英语字母标准频率（基于大文本语料库）

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]

示例明文与加密

plaintext = "The eagle has landed." k = 7 # 随机密钥 ciphertext = caesar_encrypt(plaintext, k) print(f"密文: {ciphertext}")

频率攻击

guessed_k = frequency_attack(ciphertext, english_freq) print(f"推测密钥: {guessed_k} (真实密钥: {k})") print(f"解密结果: {caesar_encrypt(ciphertext, -guessed_k % 26)}") ```

运行此代码，即使面对数千字的密文，频率分析也能在毫秒级时间内准确恢复密钥。阿尔·肯迪的智慧，如同在混沌中建立了第一个秩序——密码学的分析学基石就此奠定。他不仅提出了方法，还给出了处理更复杂替换密码（如多表替换）的初步思路，预示了未来密码学的发展方向。

三、数学的凝视：替换密码的群论建模

凯撒密码只是单表替换密码的一个特例。更一般的替换密码，可以定义为字母表 $\Sigma$ 上的一个置换（permutation）$\pi$。加密过程即应用 $\pi$：$E(x) = \pi(x)$；解密则是其逆置换 $\pi^{-1}$。从代数角度看，所有可能的单表替换构成一个对称群 $S_{26}$，其阶数为 $26! \approx 4.03 \times 10^{26}$——这个数字如此巨大，以至于在16世纪前，人们误认为暴力破解（brute-force attack）不可行。

然而，阿尔·肯迪的频率分析揭示了群论结构下的致命弱点：置换不改变符号的频率分布。设 $f_{\text{plain}}(a)$ 为明文字母 $a$ 的频率，则密文字母 $b = \pi(a)$ 的频率 $f_{\text{cipher}}(b) = f_{\text{plain}}(a)$。因此，密文的频率直方图只是明文频率直方图的一个重标记。只要目标语言的频率分布足够有特征（如英语中‘E’的突出地位），攻击者就能通过统计匹配推断 $\pi$。

这种“统计不变性”是单表替换密码的阿克琉斯之踵。为了对抗频率分析，密码设计者必须设法破坏字母与频率的固定对应关系。这引出了多表替换密码（polyalphabetic cipher）的思想：使用多个替换表，根据某种规则循环切换。16世纪意大利学者吉罗拉莫·卡达诺（Gerolamo Cardano）提出了卡达诺方阵（Cardan grille），但真正革命性的突破属于法国外交官布莱斯·德·维吉尼亚（Blaise de Vigenère）。

四、维吉尼亚的防御：多表替换与“不可破”的幻觉

1586年，维吉尼亚在《密码论》（Traicté des Chiffres）中公布了一种看似完美的密码系统。维吉尼亚密码使用一个关键词（如“KEY”）来决定每个明文字母的移位量：关键词字母循环对应移位值（A=0, B=1, ...），然后对每个明文字母应用对应的移位。例如，明文“HELLO”与密钥“KEY”加密过程：

• H (7) + K (10) → R (17)
• E (4) + E (4) → I (8)
• L (11) + Y (24) → J (9) [ (11+24) mod 26 = 9 ]
• L (11) + K (10) → V (21)
• O (14) + E (4) → S (18)

密文：“RIJVS”

```mermaid graph TD A[明文: HELLO] --> B[密钥: KEYKEY] B --> C[对应移位值<br/>10,4,24,10,4] C --> D[逐字母加密<br/>(x + k_i) mod 26] D --> E[密文: RIJVS] ```

维吉尼亚密码的威力在于它隐藏了单字母频率。在密文中，同一个明文字母‘L’被加密为‘J’和‘V’，其频率被分散到多个密文字母上。反之，同一个密文字母‘I’可能来自不同的明文字母（如‘E’和‘X’）。这种“频率平滑”效果使得传统的单字母频率分析失效。在19世纪以前，维吉尼亚密码被誉为“le chiffre indéchiffrable”（不可破的密码）。

然而，幻觉终将破灭。1863年，普鲁士军官弗里德里希·卡西斯基（Friedrich Kasiski）在《破译密码与密码的 secret 方法》中揭示了关键弱点：当密钥重复使用时，密文中会暴露出密钥长度的周期性。如果密钥长度为 $l$，则位置 $i$ 和 $i+l$ 的明文字母使用相同的密钥字母加密，因此对应的密文字母对满足 $c_i - c_{i+l} \equiv m_i - m_{i+l} \pmod{26}$。通过寻找密文中相同连续密文块（如“XYZ”出现两次）之间的距离，可以推测密钥长度的公约数。重复多次后，取所有距离的公约数，即可锁定密钥长度 $l$。

一旦 $l$ 已知，问题就退化为 $l$ 个独立的凯撒密码：将密文按位置模 $l$ 分组，每组对应一个固定的密钥字母。对每组应用频率分析，即可逐字母破解密钥。卡西斯基攻击（Kasiski examination）与19世纪中期查尔斯·巴贝奇（Charles Babbage）独立发现的重合指数法（index of coincidence）共同宣告了维吉尼亚密码的终结。后者通过计算密文中随机选取两个字母相等的概率，来统计区分单表与多表替换，从而估计密钥长度。

五、Python实战：从凯撒到维吉尼亚的自动破解

现代计算能力使得古典密码的破解自动化成为可能。以下Python脚本整合了凯撒密码的频率攻击与维吉尼亚密码的卡西斯基-重合指数联合攻击：

```python import re from collections import Counter import math

def clean_text(text): """移除非字母字符并转为大写""" return re.sub(r'[^A-Z]', '', text.upper())

def caesar_crack(ciphertext): """基于频率分析的凯撒密码破解""" 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] ciphertext = clean_text(ciphertext) if len(ciphertext) == 0: return None, None

freq = [0] * 26 for c in ciphertext: freq[ord(c) - ord('A')] += 1 freq = [f / len(ciphertext) for f in freq]

best_k = 0 best_corr = -1 for k in range(26): corr = sum(freq[i] * english_freq[(i - k) % 26] for i in range(26)) if corr > best_corr: best_corr = corr best_k = k return best_k, best_corr

def find_repeated_sequences(ciphertext, min_length=3): """寻找重复的密文块及其间隔""" ciphertext = clean_text(ciphertext) repeats = {} for length in range(min_length, min(10, len(ciphertext)//2)): for i in range(len(ciphertext) - length): seq = ciphertext[i:i+length] for j in range(i+length, len(ciphertext) - length): if ciphertext[j:j+length] == seq: if seq not in repeats: repeats[seq] = [] repeats[seq].append(j - i) return repeats

def gcd(a, b): while b: a, b = b, a % b return a

def get_key_lengths_from_gcds(spacings): """从间隔的GCD推测密钥长度""" if not spacings: return []

计算所有间隔对的GCD

gcds = [] for i in range(len(spacings)): for j in range(i+1, len(spacings)): gcds.append(gcd(spacings[i], spacings[j]))

统计GCD频率，取最常见的作为候选长度

counter = Counter(gcds)

过滤掉1和过大的值

candidates = [k for k, v in counter.most_common(5) if k > 1 and k < 20] return candidates

def index_of_coincidence(ciphertext): """计算重合指数""" ciphertext = clean_text(ciphertext) n = len(ciphertext) if n <= 1: return 0 freq = Counter(ciphertext) ic = sum(f * (f-1) for f in freq.values()) / (n * (n-1)) return ic

def vigenere_crack(ciphertext, max_key_len=20): """维吉尼亚密码自动破解""" ciphertext_clean