密码学简史与核心范式

密码学作为信息安全的核心支柱，其发展历程是一部人类与信息保护需求不断博弈的史诗。从古罗马军团的简单移位加密到现代互联网的复杂安全协议，密码学始终在攻击与防御的动态平衡中演进。本章将系统梳理密码学从古典时代到量子前沿的历史脉络，揭示其核心安全目标的演变，剖析密码分析学的攻击范式，并引入现代密码学的三大基础原则：柯克霍夫原则、计算安全性假设与随机预言模型。通过历史案例与理论分析的结合，读者将理解密码学如何从一门“艺术”逐步转变为基于数学的“科学”，并为后续章节中对称密码、非对称密码、哈希函数及量子密码等专题奠定坚实的概念基础。

---

古代密码：移位与替换的智慧

密码学的起源可追溯到古文明时期，早期密码主要依赖语言的物理隐藏（如 tattooing slaves' heads）或简单替换。其中，凯撒密码（Caesar Cipher） 作为历史上最早记载的替换密码之一，体现了古典密码的核心思想：通过字母表的固定偏移实现加密。其加密过程可形式化为：设明文字母 $p_i$ 在字母表中的位置为 $0$ 到 $25$（A=0, B=1, ..., Z=25），密钥为偏移量 $k$（通常 $k=3$），则密文字母 $c_i$ 满足： $$ c_i = (p_i + k) \mod 26 $$ 例如，明文 "HELLO" 经偏移 3 后变为 "KHOOR"。解密只需反向偏移：$p_i = (c_i - k) \mod 26$。凯撒密码的密钥空间仅有 25 种可能（$k=1$ 到 $25$），极易通过穷举攻击（Brute-force Attack） 破解。更本质的弱点在于其单表替换特性：每个明文字母始终映射到同一密文字母，导致字母频率分布被保留。英语中字母 E 的出现频率约为 12.7%，攻击者只需分析密文中频率最高的字母，即可推测其对应 E，进而推断密钥。这种频率分析（Frequency Analysis） technique 由阿拉伯学者阿尔·卡利勒（Al-Kindi）于 9 世纪系统阐述，成为破解古典替换密码的通用方法。

为应对频率分析，维吉尼亚密码（Vigenère Cipher） 于 16 世纪由法国密码学家布莱斯·德·维吉尼亚（Blaise de Vigenère）推广，其核心创新是多表替换：使用一个关键词重复作为位移表序列。设关键词长度为 $m$，关键词字母对应位移 $k_0, k_1, ..., k_{m-1}$，则第 $i$ 个明文字母的加密为： $$ c_i = (p_i + k_{i \mod m}) \mod 26 $$ 例如，关键词 "KEY"（位移分别为 10, 4, 24）加密 "ATTACK"：

• A (0) + K (10) → K (10)
• T (19) + E (4) → X (23)
• T (19) + Y (24) → R (17) （循环）

以此类推。维吉尼亚密码显著增强了安全性：相同明文字母可能被加密为不同密文字母，破坏了单一频率分布。然而，其安全性仍依赖于关键词的保密性与长度。若关键词过短（如小于密文长度），攻击者可利用卡西斯基试验（Kasiski Examination） 或弗里德曼测试（Friedman Test） 推断关键词长度。卡西斯基试验通过寻找密文中重复的字符串，计算其间距的公约数以估计关键词长度；弗里德曼测试则基于重合指数（Index of Coincidence） 统计，通过比较密文字母随机分布与自然语言分布的差异来估计关键词长度。一旦关键词长度确定，密文可按位置拆分为 $m$ 个单表替换密码，再应用频率分析逐个破解。维吉尼亚密码曾被誉为“不可破译的密码”，但 19 世纪普鲁士密码学家弗里德里希·卡西斯基（Friedrich Kasiski）的破解方法彻底打破了其神话，揭示了密钥管理与算法设计的同等重要性。

---

近代密码：机械加密与战争催化

19 世纪末至 20 世纪中叶，机械与电子技术的进步催生了更复杂的密码设备，其中以二战时期的恩尼格玛机（Enigma Machine） 最为著名。恩尼格玛由德国工程师阿瑟·谢尔比乌斯（Arthur Scherbius）于 1918 年发明，最初用于商业通信，后被德军广泛用于军事加密。其核心结构包含：

• **键盘**：输入明文字母。
• **转子（Rotors）**：通常 3 至 4 个，每个转子内部有 26 个交叉接线，实现字母的 substitutions。每按一次键，最右侧转子转动一格，带动其他转子在特定位置（如 26 次）时发生连锁转动，形成类似汽车里程表的进位机制。
• **反射器（Reflector）**：位于转子组左侧，将电流反射回转子组，确保加密解密对称（即同一设置下加密和解密使用相同过程）。
• **插板（Plugboard）**：位于键盘和转子之间，允许操作员额外交换若干对字母（最多 10 对），增加密钥空间。

加密过程：当按下明文字母键（如 'A'），电流经插板、转子组（从右至左）、反射器、转子组（从左至右）返回，最终点亮一个密文字母灯（如 'G'）。由于反射器设计，同一按键不会映射到自身，且转子转动使每次按键的替换表动态变化，理论上形成多表替换的无限循环。

恩尼格玛的密钥空间极为庞大：假设 3 个转子从 5 个中选 3 个排列（$P(5,3)=60$），转子初始位置（$26^3=17576$），插板配对（约 $1.5 \times 10^{14}$ 种），总密钥空间超过 $10^{20}$，远超当时暴力破解能力。然而，其安全性存在致命缺陷： 1. 反射器导致映射无不动点：密文不可能等于明文，这一可预测特性被盟军利用。 2. 密钥分发与操作失误：德军密钥手册被缴获，且部分消息包含可预测的格式（如每日天气报告、标准问候语），提供已知明文（Known Plaintext）。 3. 机械限制：转子转动规律固定，且同一日密钥下消息密钥（Message Key）的重复发送形成模式。

波兰密码学家马里安·雷耶夫斯基（Marian Rejewski）于 1932 年利用数学组理论与缴获的密钥材料，首次破译恩尼格玛。他通过分析大量已知明文-密文对，推导出转子内部接线，并发明了炸弹（Bomba） 机电设备自动化测试密钥。1940 年，英国布莱切利园（Bletchley Park）在图灵（Alan Turing）领导下改进为巨人（Colossus） 电子计算机，专门破解德军高级密码。图灵的关键贡献包括：设计更高效的banburismus统计方法减少候选密钥，并利用德军操作习惯（如 "HEIL HITLER" 结尾）作为已知明文。恩尼格玛的破译被广泛认为缩短二战至少两年，凸显了密码分析学在信息战中的决定性作用，也印证了柯克霍夫原则的雏形：即使设备部分原理保密，系统性弱点仍可被利用。

---

现代密码：算法公开与数学基石

二战后，密码学从军事领域转向民用，随着计算机与通信网络的发展，数据加密标准（Data Encryption Standard, DES） 于 1977 年由美国国家标准局（NBS，现 NIST）正式发布，标志着现代对称密码的诞生。DES 采用 Feistel 网络结构，将 64 位明文分为左右两半，经过 16 轮迭代处理，每轮使用 48 位子密钥。其核心组件包括：

• **扩展置换（Expansion Permutation）**：将 32 位右半部分扩展为 48 位，增加扩散性。
• **S 盒（Substitution Boxes）**：8 个非线性替换表，将 6 位输入映射为 4 位输出，提供混淆（Confusion）。
• **P 置换（Permutation）**：对 S 盒输出进行位置换，增强扩散（Diffusion）。

DES 的密钥长度为 56 位（外加 8 位奇偶校验），当时足以抵抗暴力破解（$2^{56} \approx 7.2 \times 10^{16}$ 次运算）。然而，1970 年代已有人质疑其密钥过短。1998 年，电子前沿基金会（EFF）建造的 Deep Crack 机器在 56 小时内穷举破解 DES，宣告其实际不安全。更深层威胁来自差分密码分析（Differential Cryptanalysis） 与线性密码分析（Linear Cryptanalysis）：前者由 Biham 和 Shamir 于 1990 年公开，通过分析明文对差异如何传播至密文对，推断密钥；后者利用线性近似方程进行统计攻击。有趣的是，IBM 在 DES 设计时已知晓差分攻击，但未公开，后成为柯克霍夫原则的经典案例：算法保密仅能提供“隐蔽安全（Security by Obscurity）”，而公开审查才能发现深层弱点。

为替代 DES，NIST 于 2001 年选定 高级加密标准（Advanced Encryption Standard, AES），其候选算法 Rijndael 由比利时学者 Daemen 和 Rijmen 设计。AES 支持 128/192/256 位密钥，采用代换-置换网络（Substitution-Permutation Network, SPN） 而非 Feistel 结构，每轮包括字节代换（SubBytes）、行移位（ShiftRows）、列混淆（MixColumns）和轮密钥加（AddRoundKey）。AES 的设计哲学是宽轨迹策略（Wide Trail Strategy），确保每轮变换提供最大扩散与混淆，抵抗差分与线性攻击。AES 的公开评审过程（1997-2000）汇集全球密码学家，最终算法经受住严格考验，成为当前对称加密的黄金标准。

非对称密码（公钥密码） 的诞生彻底改变了密钥分发困境。1976 年，Diffie 与 Hellman 在论文《密码学的新方向》中提出密钥交换协议（Diffie-Hellman Key Exchange），基于离散对数问题（Discrete Logarithm Problem, DLP） 的困难性：在有限域 $G$ 中，给定 $g$ 和 $g^a \mod p$，计算 $a$ 是计算上不可行的。双方可通过公开交换 $g^a$ 和 $g^b$ 计算共享密钥 $g^{ab}$，而窃听者无法从 $g^a$ 和 $g^b$ 推导 $g^{ab}$。1977 年，Rivest、Shamir 和 Adleman 提出 RSA 算法，基于大整数分解问题（Integer Factorization Problem）：给定大合数 $n = pq$（$p,q$ 为大素数），分解 $n$ 是困难的。RSA 密钥生成如下： 1. 随机选择两个大素数 $p, q$，计算 $n = pq$ 和 $\phi(n) = (p-1)(q-1)$。 2. 选择公钥指数 $e$ 满足 $1 < e < \phi(n)$ 且 $\gcd(e, \phi(n)) = 1$。 3. 计算私钥 $d \equiv e^{-1} \mod \phi(n)$。 加密：$c = m^e \mod n$；解密：$m = c^d \mod n$，其中 $m$ 为明文分组的整数表示（需 $m < n$）。

RSA 的安全性依赖于从公钥 $(e,n)$ 推导私钥 $d$ 的困难性，这等价于分解 $n$。例如，取小素数 $p=61, q=53$，则 $n=3233, \phi(n)=3120$，选 $e=17$，计算得 $d=2753$。明文 "HELLO" 可转换为数字序列（如 ASCII），分段加密。RSA 不仅用于加密，还可构造数字签名：签名 $s = m^d \mod n$，验证 $m = s^e \mod n$，实现不可否认性。RSA 与 Diffie-Hellman 共同奠定了公钥基础设施（Public Key Infrastructure, PKI） 的基础，使安全通信在开放网络中成为可能。

---

核心安全目标：机密性、完整性、认证性与不可否认性

现代密码学的目标已从单一保密性扩展为四大支柱，共同构成信息安全的 CIA+ triad（机密性、完整性、可用性）在密码学层面的细化：

1. 机密性（Confidentiality） 确保信息仅被授权方访问，核心手段是加密。对称加密（如 AES）提供高效 bulk 数据加密，非对称加密（如 RSA）用于密钥交换或小数据加密。例如，TLS 协议中，客户端用服务器公钥加密预主密钥，实现安全密钥协商。

2. 完整性（Integrity） 保证信息在传输或存储中未被篡改，主要通过消息认证码（Message Authentication Code, MAC） 或密码学哈希函数（Cryptographic Hash Function） 实现。MAC（如 HMAC）使用共享密钥生成短标签，接收方验证标签一致性；哈希函数（如 SHA-256）将任意长度输入映射为固定长度摘要，具有抗碰撞性（Collision Resistance）（难以找到 $x \neq y$ 使得 $H(x)=H(y)$）与第二预像抗性（Second Preimage Resistance）（给定 $x$，难找 $y \neq x$ 使 $H(y)=H(x)$）。例如，软件下载时提供 SHA-256 哈希值，用户可验证文件完整性。

3. 认证性（Authentication） 确认通信方身份的真实性，常结合数字证书与公钥密码。在 TLS 握手，服务器向客户端提供由可信证书颁发机构（CA）签名的数字证书，客户端验证证书链以确认服务器身份，防止中间人攻击。

4. 不可否认性（Non-repudiation） 防止发送方事后否认其行为，通过数字签名实现。签名使用发送方私钥生成，任何人均可用其公钥验证，且私钥仅由发送方持有，提供法律证据。例如，电子合同采用数字签名，确保签署方无法抵赖。

这四大目标相互关联：机密性保护内容隐私，完整性确保内容未被修改，认证性验证来源，不可否认性提供证据。实际协议（如 PGP、S/MIME）通常组合使用这些原语。例如，PGP 对邮件执行：哈希生成摘要 → 用发件人私钥签名摘要 → 用收件人公钥加密邮件与签名。收件人先解密，再验证签名，同时实现机密性、完整性、认证性与不可否认性。

---

密码分析学：攻击模型与实战案例

密码分析学（Cryptanalysis）是研究如何破解密码系统的学科，其攻击模型按攻击者掌握的信息量分级，形成攻击强度递增的体系：

| 攻击类型 | 攻击者掌握信息 | 实际案例 | |----------|----------------|----------| | 唯密文攻击（Ciphertext-only Attack） | 仅知若干密文 | 频率分析破解凯撒密码、维吉尼亚密码 | | 已知明文攻击（Known Plaintext Attack） | 知部分明文-密文对 | 二战中盟军利用德军固定消息头（如 "WETTER" 天气报告）破解恩尼格玛 | | 选择明文攻击（Chosen Plaintext Attack） | 可自选明文并获取对应密文 | 对 WEP 协议的攻击：攻击者注入特定数据包，分析 RC4 密钥流弱点 | | 选择密文攻击（Chosen Ciphertext Attack） | 可自选密文并获取对应明文 | 对 RSA 填充不当的 Bleichenbacher 攻击，针对 PKCS#1 v1.5 的 Oracle 攻击 |

唯密文攻击是最弱模型，古典密码多因此被破。已知明文攻击在实战中常见：军事通信常有标准格式，商业协议可能有固定报头。选择明文攻击是现代密码的基准安全要求：一个安全的加密方案应能抵抗此攻击。例如，AES 在选择明文攻击下仍保持安全，而早期 RC4 因密钥流偏斜被选择明文攻击破解，导致 WEP 协议全面废弃。

一个经典案例是对 DES 的差分密码分析：Biham 和 Shamir 通过精心选择明文对，分析 S 盒输出差异的概率分布，最终在 $2^{47}$ 个已知明文下恢复密钥。这揭示了 DES 设计时未公开的弱点，也推动了 AES 设计中对差分特性的严格评估。

---

现代密码学基础范式

柯克霍夫原则（Kerckhoffs's Principle）

19 世纪荷兰语言学家、密码学家奥古斯特·柯克霍夫（Auguste Kerckhoffs）在 1883 年论文《军事密码学》中提出六条密码系统设计准则，其中核心为：密码系统的安全性应仅依赖于密钥的保密，而非算法本身的保密。即，即使攻击者完全知晓算法细节（除密钥外），系统仍应安全。

这一原则与现代密码学实践深度契合：

• **AES 公开评审**：NIST 向全球征集算法，经过多年公开分析才选定 Rijndael，确保无隐藏弱点。
• **开源软件优势**：OpenSSL 等开源库允许全球专家审计，比“秘密算法”更可靠。
• **历史反例**：恩尼格玛的保密依赖于机器结构秘密，一旦被缴获即被破解；而现代算法即使泄露实现代码，只要密钥安全，系统仍安全。

柯克霍夫原则的深层含义是：算法公开促进安全生态。秘密算法可能因设计者水平有限而含未发现漏洞；公开算法则经集体智慧检验，且“设计者无法假设攻击者不知算法”。然而，该原则在侧信道攻击（Side-channel Attack） 场景下需修正：即使算法数学上安全，实现中的时序、功耗、电磁泄漏可能暴露密钥，故实现安全同样关键。

计算安全性（Computational Security）

古典密码（如凯撒）在理论上可被穷举破解，但现代密码的安全性基于计算困难性假设（Computational Hardness Assumption）：某些数学问题在合理时间内无法解决。形式化地，一个密码方案是计算安全的，若对任何概率多项式时间（Probabilistic Polynomial Time, PPT） 攻击者，其成功概率是可忽略的（negligible），即小于所有多项式 $1/\text{poly}(n)$ 的倒数，其中 $n$ 为安全参数（如密钥长度）。

关键困难问题包括：

• **大整数分解（Integer Factorization）**：RSA 基础。给定 $n=pq$，分解 $n$ 的最优算法（普通数域筛法，GNFS）时间复杂度

计算安全性假设：困难问题与形式化定义

现代密码学的安全性基石是**计算困难性假设（Comp