密码学演进史：从凯撒密码到信息论安全

密码学的发展史，实质上是一部保密需求与攻击技术之间永恒博弈的编年史。从古罗马军团的简单移位到二战时期恩尼格玛机电机的复杂转子系统，再到20世纪70年代公钥密码学的革命性突破，每一次安全边界的拓展都伴随着密码分析技术的相应演进。这一演进历程不仅映射了数学、工程与计算科学的交叉融合，更深刻地揭示了安全概念本身从经验性艺术向理论性科学的范式转变。本章将系统追溯密码学两千余年的发展脉络，聚焦于关键的历史节点与理论转折，深入剖析古典密码机制的内在缺陷、恩尼格玛密码机的工程原理与图灵破解的划时代意义，进而论述20世纪70年代密码学范式转变的核心——公钥密码思想的提出、数据加密标准（DES）的标准化及其引发的密码学与密码分析的军备竞赛。最终，本章将引出信息论安全与计算安全这一核心理论分野，为全书奠定坚实的历史与理论基础，并指向后量子时代的安全挑战。

古典密码学：替换与置换的脆弱性

古典密码学主要活跃于20世纪中期以前，其设计理念基于简单的字符替换与位置置换，安全性高度依赖算法的保密性（security through obscurity）以及攻击者认知的局限性。这一时期的密码系统缺乏严格的数学基础，其安全性往往在未被公开分析时被高估，一旦机制暴露，便极易被系统性攻破。以下将选取最具代表性的凯撒密码与维吉尼亚密码进行深入机制分析与缺陷剖析。

凯撒密码：单表替换的典范及其致命弱点

凯撒密码是历史上最早有记载的替换密码之一，据传由古罗马的盖乌斯·尤利乌斯·凯撒用于军事通信。其加密机制极为简单：将明文字母表按照固定位数进行循环移位，通常为3位（在罗马字母表中）。设字母集为 $\mathcal{A} = \{A, B, ..., Z\}$，模26运算，密钥 $k \in \{1, 2, ..., 25\}$，则加密函数为： $$c = (p + k) \mod 26$$ 其中 $p$ 和 $c$ 分别表示明文字母和密文字母对应的数值（如A=0, B=1, ...）。解密则为 $p = (c - k) \mod 26$。

凯撒密码的密钥空间仅为25（忽略 $k=0$ 的平凡情况），这意味着即使不借助任何密码分析技术，仅通过穷举搜索即可在极短时间内完成破译。然而，其真正的致命缺陷在于单表替换的固有性质：明文中的每一个字母被唯一、固定地映射为密文字母。这种映射的单调性直接保留了明文字母的统计特征。在自然语言中，字母频率分布呈现显著的非均匀性，例如在英语文本中，字母 'E' 的出现频率约为12.7%，'T' 约为9.1%，而 'Z' 不足0.1%。攻击者只需对一段足够长的密文进行频率统计，将最高频的密文字母对应到明文中最高频的字母（如 'E'），即可快速推断出密钥或建立完整的替换映射表。这种攻击方法被称为频率分析，其有效性不依赖于对加密算法的任何先验知识，仅基于语言统计特性。公元9世纪，阿拉伯学者阿尔·金迪（Al-Kindi）在其著作《破译加密信息》中系统阐述了这一方法，标志着密码分析作为一门独立学科的萌芽。

频率分析的威力迫使密码设计者寻求更复杂的方案，即引入多表替换机制，试图打乱字母频率的单一对应关系。

维吉尼亚密码：多表替换的演进与卡西斯基试验的突破

16世纪，意大利密码学家吉奥万·巴蒂斯塔·贝尔索（Giovan Battista Bellaso）提出了维吉尼亚密码（以布莱斯·德·维吉尼亚的名字推广），它被认为是古典密码学中“不可破”的巅峰。其核心思想是使用一个关键词作为可变密钥，对明文字母进行循环的多表替换加密。设关键词为 $K = k_1 k_2 ... k_m$（长度 $m$），明文分组为 $P = p_1 p_2 ... p_n$，则第 $i$ 个明文字母 $p_i$ 使用第 $j = ((i-1) \mod m) + 1$ 个密钥字母 $k_j$ 进行凯撒式移位加密： $$c_i = (p_i + k_j) \mod 26$$

维吉尼亚密码相较于凯撒密码，密钥空间急剧扩大至 $26^m$（对于长度 $m$ 的关键词）。更重要的是，同一明文字母 $p$ 在不同位置可能被映射为不同的密文字母（取决于对应的密钥字母），从而在表面上消除了单表替换的固定频率映射。一段密文可以看作 $m$ 个独立的凯撒密码交叠而成。因此，如果攻击者不知道关键词长度 $m$，频率分析似乎失效。

然而，维吉尼亚密码的设计者忽略了一个关键点：关键词的周期性重复。虽然单次出现的字母频率被扰乱，但整个密文序列中，当明文字母序列与密钥序列保持相同相对位置时，加密所使用的偏移量是固定的。这导致密文序列中隐含了与明文频率相关的周期性模式。19世纪，普鲁士军官弗里德里希·卡西斯基（Friedrich Kasiski）在1863年提出了一种革命性的攻击方法，称为卡西斯基试验。其核心思想是：在密文中寻找重复出现的密文片段（长度至少为3）。如果两个相同的密文片段出现，则它们对应的明文片段很可能相同（在自然语言中，常见单词或短语如“the”、“and”会重复出现），且加密时使用了相同的密钥序列。因此，这两个重复片段起始位置之间的距离，极有可能是关键词长度 $m$ 的整数倍。通过收集多个这样的距离，并计算它们的最大公约数（GCD），即可高概率地确定关键词长度 $m$。

一旦 $m$ 被确定，攻击者便将密文字母按位置模 $m$ 分成 $m$ 组，每组对应一个固定的凯撒密码（使用同一个密钥字母）。对每一组独立进行频率分析，即可依次恢复每个密钥字母，最终破解整个系统。例如，若 $m=5$，则第1、6、11、...位构成第一组，进行频率分析得到第一个密钥字母；第2、7、12、...位构成第二组，得到第二个密钥字母，依此类推。

维吉尼亚密码的破解具有里程碑意义：它首次展示了如何通过统计冗余和周期性结构分析来攻破看似复杂的多表替换系统。其核心漏洞在于密钥流的周期性——一个真正随机的、非周期且长度至少与明文相同的密钥流（即一次一密）才能抵御此类攻击。这一洞见直接导向了信息论安全的核心概念。

古典密码学的共性缺陷与理论缺失

综合凯撒密码与维吉尼亚密码的案例分析，古典密码学体系存在以下根本性缺陷： 1. 缺乏数学基础：安全性论证依赖直觉与经验，而非严格的数学证明。设计者无法量化其系统抵抗攻击的能力。 2. 密钥管理困境：在大量通信场景中，通信双方必须预先共享密钥，且密钥需定期更换以防泄露。这一“密钥分发问题”在广域网络中几乎无法解决。 3. 静态结构：加密算法通常为静态的确定性变换，不随加密过程动态演化（维吉尼亚的密钥重复除外），导致统计特征易于累积和分析。 4. 混淆与扩散不足：现代密码学两大设计原则——混淆（confusion，使密钥与密文关系复杂化）与扩散（diffusion，使明文统计特性扩散到密文的大部分）——在古典系统中体现得极为原始。例如，凯撒密码仅实现线性混淆，且无扩散；维吉尼亚通过多表引入了部分扩散，但周期性破坏了其效果。

这些缺陷在恩尼格玛密码机这样的机电设备上得到了部分克服，但其内在局限性最终仍被图灵等密码分析家以更精巧的数学与工程方法所击破。

机电密码的巅峰：恩尼格玛与图灵突破

20世纪上半叶，机电技术的进步催生了以恩尼格玛（Enigma）为代表的高度复杂的密码设备。恩尼格玛由德国工程师亚瑟·谢尔比乌斯（Arthur Scherbius）于1918年发明，1920年代开始商用，后被德国国防军、海军等广泛采用，在二战期间成为德军主要通信加密工具。其设计之精妙、密钥空间之巨大，曾使盟军密码分析者一度绝望。然而，正是对恩尼格玛的成功破译，成为二战转折的关键因素之一，并催生了现代计算机科学的诞生。

恩尼格玛密码机的工程原理

恩尼格玛的核心是一个由多个可旋转的转子（rotor）组成的机电置换网络，辅以反射器（reflector）和插接板（plugboard）。其加密过程完全机械化：操作者通过键盘输入一个明文字母，电流依次经过插接板、一系列转子、反射器，再反向经过同一系列转子，最后通过插接板点亮一个密文字母对应的灯。每次按键，最右侧转子会向前转动一步，当转子上的凹槽（notch）与特定位置对齐时，会通过机械联动使左侧转子也转动，形成“进位”效应。这种转子步进机制确保了每次按键后，整个加密置换都会发生改变，从而产生极其复杂的多表替换效果。

从密码学角度，恩尼格玛实现了一个自逆（self-inverse）的置换：由于反射器的存在，加密路径与解密路径完全对称。若使用完全相同的初始转子位置和插接板设置，对密文进行加密操作即可得到明文。这简化了操作，但也是其潜在弱点之一。

其安全强度来源于巨大的密钥空间，由以下几个因素组合而成：

• **转子选择与排列**：从5种（或更多）不同内部布线（wiring）的转子中选取3个（或更多），并决定其在转子组中的顺序。选择与排列数可达 $P(5,3) = 60$ 种。
• **插接板接线**：在26个字母中两两配对交换，通常连接6对（早期）至10对（后期）。可能的接线方式约为 $10^{14}$ 数量级。
• **转子初始位置**：每个转子有26个可能起始位置，共 $26^3 = 17,576$ 种。
• **环位设置**（ring setting）：调整转子内部 wiring 相对于外壳刻度盘的偏移，影响步进触发点，共 $26^3$ 种。

总密钥空间粗略估计超过 $10^{23}$，在1940年代的技术条件下，即使使用当时最快的继电器计算机进行穷举，也需要数百万年。因此，德军高层坚信恩尼格玛是“不可破”的。

图灵的突破：数学、工程与情报的融合

然而，恩尼格玛并非完美无缺。其设计者为了操作便利和机械可靠性，引入了几个关键的结构性弱点： 1. 固定点自由：由于反射器的设计，任何字母经过加密后，绝不会映射为自身（即 $E(x) \neq x$）。这意味着，如果密文字母与明文字母相同，则该密钥设置

固定点自由：反射器设计中的致命对称性

恩尼格玛密码机的反射器（Umkehrwalze）设计是其自逆特性的核心，却也是其最根本的结构性弱点。反射器将经过转子组的所有电流反向反射，使电流再次通过同一组转子（反向顺序），最终从不同字母口输出。这种设计意味着，对于任何输入字母 $x$，其输出字母 $y$ 满足 $y \neq x$。因为反射器由固定接线实现，电流必须从一根线切换到另一根不同的线，从而强制排除固定点（即 $E(x) \neq x$ 对所有 $x$ 成立）。

这一看似 innocuous 的设计约束，在已知明文攻击（known-plaintext attack）场景下成为致命漏洞。假设攻击者截获了一段密文 $C = c_1 c_2 ... c_n$，并合理推测密文对应的明文中包含某个常见短语（称为 crib），例如德语中的 "WETTER"（天气）。设 crib 在位置 $i$ 开始，则对于 $j = 0$ 到 $5$，有 $p_{i+j} = W, E, T, T, E, R$ 而 $c_{i+j}$ 为对应密文字母。由于恩尼格玛的自逆性，加密过程可视为：$c = E(p, K)$，其中 $K$ 为密钥（转子顺序、初始位置、插接板等）。但自逆性还意味着 $E(K, p) = c$ 且 $E(K, c) = p$。更重要的是，对于任意字母对 $(p, c)$，如果 $p = c$，则不可能，因为固定点自由。因此，攻击者可立即排除任何 crib 假设中导致 $p_j = c_j$ 的偏移位置 $i$。

更强大的攻击利用了 互斥对 性质：由于自逆和固定点自由，对于任何密钥设置，字母对 $(p, c)$ 满足 $p \neq c$，且映射是双射。如果 crib 中某位置 $j$ 有 $p_j$ 和 $c_j$，则 $p_j$ 不可能映射到 $c_j$（因为那意味着 $E(p_j) = c_j$ 且 $E(c_j) = p_j$，但反射器强制 $E(x) \neq x$，且自逆性下 $E(p_j)=c_j$ 蕴含 $E(c_j)=p_j$，这并不直接矛盾，但结合固定点自由，实际上允许 $p_j \neq c_j$ 且 $E(p_j)=c_j$，$E(c_j)=p_j$，这是可能的。等等，我可能混淆了。

重新澄清：自逆性意味着加密函数 $E$ 是对合（involution），即 $E(E(x)) = x$ 对所有 $x$。固定点自由意味着 $E(x) \neq x$。因此，$E$ 将字母集划分为若干个 2-循环（2-cycles）：$x \leftrightarrow y$，其中 $x \neq y$。因此，如果 $E(p) = c$，则必然 $E(c) = p$，且 $p \neq c$。这意味着，在 crib 攻击中，如果假设 crib 在位置 $i$ 对齐，则对于每个 $j$，必须有 $p_{i+j} \neq c_{i+j}$，这总是成立因为固定点自由，所以这个条件不提供排除。真正的排除来自：如果 $E(p) = c$，则 $E(c) = p$，但攻击者不知道 $E$，所以crib攻击中，攻击者测试一个假设的密钥设置 $K$，计算 $E_K(p_{i+j})$ 是否等于 $c_{i+j}$。但图灵的 bombe 机器利用的是：对于给定的转子设置（不考虑插接板），可以推导出一些字母必须互斥或必须配对。

实际上，bombe 的核心是利用 crib 和已知的恩尼格玛结构（特别是反射器导致的固定点自由）来推导转子步进状态下的矛盾。更准确地说：假设 crib 的明文 $P_{crib}$ 和密文 $C_{crib}$ 对齐，对于每个位置，如果 $E_K(p) = c$，则由于反射器，$p$ 和 $c$ 必须通过转子组的置换连接，且 $p \neq c$。但关键是，对于一组转子设置，如果某个字母 $a$ 被映射到 $b$，则 $b$ 必须被映射回 $a$。因此，如果 crib 中同时出现 $p_1 \to c_1$ 和 $p_2 \to c_2$，且这些映射在转子组中产生矛盾（例如，要求同一个转子位置同时将 $a$ 映到 $b$ 和到 $c$），则该转子设置被排除。

图灵的 bombe 本质上是一个高速逻辑推理机器，它枚举可能的转子顺序和环位设置，对于每个假设，利用 crib 和固定点自由约束，检查是否存在矛盾。如果无矛盾，则该设置可能是正确的，需要进一步人工分析。Bombe 不直接破解密钥，而是大幅缩小搜索空间（从 $10^{23}$ 降到可管理的几百个可能设置），然后由密码分析员用其他方法（如利用消息密钥重复）最终确定。

消息密钥重复：人为失误导致的灾难性漏洞

德军在操作恩尼格玛时引入了一个致命的程序错误：为了确保收报方能正确设置转子初始位置，发报方在加密真正消息前，会先选择三个字母作为消息密钥（Message Key），然后用当日的主密钥（Grundstellung）加密该消息密钥两次（例如，如果消息密钥是 "ABL"，则发送 "ABLABL" 的密文）。这一重复发送看似冗余，却为波兰和英国密码分析家提供了黄金 crib。

设消息密钥为 $K_{msg} = k_1 k_2 k_3$，主密钥位置为 $G$。则发送的密文为 $C = E_G(k_1) E_G(k_2) E_G(k_3) E_G(k_1) E_G(k_2) E_G(k_3)$。由于主密钥 $G$ 是固定的（每日更换），攻击者知道这一格式。因此，截获的六字母密文 $C_1 C_2 C_3 C_4 C_5 C_6$ 满足：$C_1$ 和 $C_4$ 是同一明文字母 $k_1$ 在相同转子设置 $G$ 下的加密；$C_2$ 和 $C_5$ 对应 $k_2$；$C_3$ 和 $C_6$ 对应 $k_3$。因此，有 $C_1 \neq C_4$（因为固定点自由，且 $k_1 \neq E_G(k_1)$ 一般成立），但更重要的是，$C_1$ 和 $C_4$ 是同一字母的两次加密，在相同转子位置下，这意味着转子位置没有变化（因为消息密钥加密时转子不步进？实际上，加密消息密钥时，转子从 $G$ 开始，每按一次键转子步进一次，所以加密第一个 $k_1$ 时转子位置为 $G$，加密第二个 $k_2$ 时转子步进一次，加密第三个 $k_3$ 时再步进一次，然后加密第四个 $k_1$ 时转子又步进一次，所以位置已不同。等等，德军操作：设置转子到主密钥 $G$，然后输入消息密钥三个字母，每输入一个字母转子步进一次，然后重新设置转子到 $G$，再输入消息密钥三个字母（第二次）。所以第一次加密 $k_1$ 时转子位置为 $G$，加密 $k_2$ 时为 $G$ 步进一次，加密 $k_3$ 时为 $G$ 步进两次；第二次加密 $k_1$ 时转子又重置到 $G$，所以位置相同。因此，$C_1$ 和 $C_4$ 确实是在相同转子设置 $G$ 下对同一明文字母 $k_1$ 的加密，所以 $C_1 = C_4$？不，因为自逆性，$E_G(k_1) = c$，则 $E_G(c) = k_1$，但 $c$ 是输出，所以 $C_1 = E_G(k_1)$，$C_4 = E_G(k_1)$，所以 $C_1 = C_4$。但固定点自由只要求 $k_1 \neq E_G(k_1)$，不要求 $E_G(k_1)$ 在不同加密中不同？实际上，如果转子设置完全相同，加密同一明文字母应产生相同密文。但德军重复发送消息密钥，正是为了验证收报方正确设置了主密钥，所以 $C_1$ 应该等于 $C_4$？但历史记录中，德军确实重复发送，而波兰/英国利用了这一重复。我可能记错了。

查证历史：德军恩尼格玛操作：选择消息密钥（如 "ABL"），设置转子到主密钥（如 "KLT"），然后依次按 A、B、L，得到三个密文字母（如 "XJZ"）；然后重新设置转子到主密钥 "KLT"，再次依次按 A、B、L，得到另外三个密文字母（如 "XJZ" 相同？）。实际上，由于转子在每次按键后步进，第一次加密 A 时转子位置为 KLT，加密 B 时转子步进一次（比如 KLT -> KLU），加密 L 时再步进。第二次加密时先重置到 KLT，所以加密第一个 A 时位置又是 KLT。因此，两次加密的 A 都在相同转子设置下，应产生相同密文。所以 $C_1 = C_4$，$C_2 = C_5$，$C_3 = C_6$。但历史资料显示，德军有时会犯错误，或者我混淆了。

实际上，标准历史：德军在1938年之前，消息密钥是用主密钥加密两次，但两次加密之间转子不重置？等等，更准确：1938年9月15日前，消息密钥加密方式：选择消息密钥（三个字母），设置转子到主密钥，然后输入消息密钥一次，得到三字母密文；然后不改变转子位置（即转子已步进三次），再输入消息密钥一次，得到第二个三字母密文。所以总密文六字母，但两次加密的转子起始位置不同（第一次从主密钥开始，第二次从主密钥步进三次后的位置开始）。因此，$C_1$