密码学导论：概念、历史与安全范式 / Introduction: Concepts, History, and Security Paradigms

密码学是一门关于信息保密、完整与认证的科学与艺术，其核心在于通过数学与工程手段，在对抗性环境中保护数据。本章将系统性地建立密码学的概念框架，追溯其历史演进，并引入现代密码学的核心安全范式与理论基础。

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

现代密码学旨在实现四大核心安全目标，这些目标共同构成了信息安全的基石。

机密性 确保信息仅能被授权方访问。其经典实现是加密：将明文通过算法与密钥变换为不可读的密文。解密则需持有正确密钥。例如，对称加密算法AES-256在理论上，即使攻击者拥有无限计算资源，其暴力搜索密钥空间（$2^{256}$）所需时间也远超宇宙年龄，从而提供了计算意义上的机密性。

完整性 保证信息在传输或存储过程中未被篡改。消息认证码（MAC）和密码散列函数是实现完整性的主要工具。例如，SHA-256散列函数能为任意长度数据生成固定256位“指纹”。即使原始数据仅改变一个比特，输出散列值也会以高概率（$1 - 2^{-128}$）完全不同，这种“雪崩效应”是检测篡改的关键。

认证 确认通信实体的身份。这包括数据源认证（验证消息确实来自声称的发送方）和实体认证（验证参与会话的实体身份）。数字签名（如ECDSA）同时提供认证与不可否认性；而基于共享密钥的MAC（如HMAC）则提供对称环境下的数据源认证。

不可否认性 防止通信一方事后否认其行为。数字签名是实现不可否认性的核心技术，其法律效力在许多司法管辖区已被认可。例如，一份使用签名者私钥签署的电子合同，签名者无法声称该签名是伪造的，因为只有其持有对应的私钥。

这四大目标并非孤立。一个安全的通信协议（如TLS 1.3）通常需要组合多种密码学原语：非对称加密（如ECDH）用于密钥交换以保障机密性，对称加密（如AES-GCM）用于 bulk 加密同时提供机密性与完整性，数字签名（如ECDSA）用于服务器认证。

**1.2 历史演进：从古典密码到机械密码**

密码学历史是攻击者与防御者之间持续军备竞赛的缩影。

古典密码时代 主要依赖替换与换位。

• **凯撒密码** 是最简单的替换密码，将字母表循环移位固定位数（如3位）。其加密函数可形式化为 $E(x) = (x + k) \mod 26$，其中 $x$ 为明文字母的数值表示（A=0, B=1…），$k$ 为密钥。其安全性完全依赖于攻击者不知道移位值 $k$。然而，由于语言字母频率分布不变（如英语中‘E’最常见），**频率分析**攻击可轻易破解。例如，截获密文“KHOOR ZRUOG”中，出现最频繁的字母‘K’和‘R’很可能对应明文的‘E’和‘T’，从而推断出密钥 $k=3$。

• **维吉尼亚密码** 通过使用多表替换（关键词循环）试图抵御频率分析。设关键词为“KEY”，则加密过程为：明文“HELLO” -> 密钥流“KEYKE” -> 各字母分别进行凯撒移位（H+K, E+E, L+Y, L+K, O+E）。其数学表示为 $E(m_i) = (m_i + k_{i \mod l}) \mod 26$，其中 $l$ 为关键词长度。虽然单表频率分析失效，但**卡西斯基试验**和**重合指数法**可发现密钥长度 $l$。一旦 $l$ 确定，密文被分解为 $l$ 个单表替换密码，即可用频率分析破解。这揭示了**密钥重复使用**的灾难性后果。

机械密码时代 以恩尼格玛密码机为代表，实现了复杂的自动加密。 恩尼格玛的核心是转子机械。每台机器包含多个（通常3-5个）可旋转的转子，每个转子内部有复杂的交叉接线。每次按键，电流穿过转子网络，实现一个字母到另一个字母的替换，同时至少一个转子会转动一步，导致下一次加密的替换表发生变化。这种设计产生了巨大的周期（约 $26^3 = 17576$ 对于3转子），远超手工计算。

其安全依赖于初始转子设置（包括转子顺序、环位设置、插板接线）作为密钥，密钥空间极大（约 $10^{23}$）。然而，波兰数学家雷耶夫斯基、佐加尔斯基和罗佐基在1932年通过已知明文攻击（利用德军重复发送的天气报告开头“WETTER”），结合 permutation group 理论，首次破译了恩尼格玛。英国布莱切利园的马修·图灵等人进一步改进，设计了Bombe机电设备，自动化地测试所有可能的转子设置，利用“ crib ”（已知或猜测的明文-密文对）来排除错误设置。恩尼格玛的破译凸显了系统设计缺陷（如不允许字母加密为自身、消息密钥重复发送）在强大系统被削弱中的关键作用。

**1.3 现代密码学基本原则**

现代密码学建立在几个核心原则之上，这些原则将古典密码的“秘密算法”思维彻底扭转。

柯克霍夫斯原则（Auguste Kerckhoffs, 1883）断言：一个密码系统的安全性应仅依赖于密钥的保密，而非算法的保密。即系统即使被攻击者完全了解（算法公开、设备缴获），只要密钥保密，仍应保持安全。这与“安全通过保密”（Security through obscurity）截然相反。DES的设计遵循此原则，其算法完全公开，安全性争议集中于密钥长度（56位）是否足够。这一原则催生了公开的密码分析文化：任何新算法都应接受全球密码学界的严格审查， survived scrutiny 的算法才值得信赖。RSA、AES、SHA-3等均经历此过程。

攻击模型 定义了攻击者拥有的能力，是安全证明的基石。其强度依次递增： 1. 唯密文攻击：攻击者仅拥有一些密文。 2. 已知明文攻击：攻击者拥有若干（明文，密文）对。 3. 选择明文攻击：攻击者可选择任意明文并获取其密文（如访问加密 oracle）。 4. 选择密文攻击：攻击者可选择任意密文并获取其解密结果（如访问解密 oracle）。CCA2（自适应选择密文攻击）是实际中要求最高的模型，TLS等协议必须抵抗此类攻击。

安全定义 需精确且可证明。主流定义包括：

• **IND-CPA**：语义安全或不可区分性。挑战者选择两个明文 $m_0, m_1$，攻击者选择其一让其加密，攻击者无法区分返回的密文对应哪个明文。这抵抗CPA攻击。例如，使用ECB模式加密的图片会保留轮廓，显然不满足IND-CPA；而使用CBC或CTR模式（需随机IV）则满足。
• **IND-CCA**：抵抗选择密文攻击的不可区分性。更严格，要求即使攻击者能解密任意非挑战密文，也无法区分挑战密文。许多最初满足IND-CPA的模式（如未认证的CBC）易受CCA攻击（如填充 oracle 攻击，BEAST, POODLE）。
• **EUF-CMA**：存在性不可伪造性，针对数字签名。攻击者即使能获取对任意消息的签名，也无法伪造一个全新消息的有效签名。

**1.4 数学与计算复杂性理论框架**

现代密码学的安全声明最终都锚定在计算复杂性理论上，核心问题是：是否存在某些问题，易于验证（给定一个解，快速检查其正确性），但难以求解？

P vs NP 问题：P类问题指存在多项式时间算法解决的问题。NP类问题指给定一个“证书”（解），能在多项式时间内验证其正确性的问题。P=NP? 是计算机科学最大未解之谜。若P=NP，则几乎所有基于“难问题”的密码学将崩溃。目前广泛相信P≠NP。

密码学依赖的“难问题”属于NP，但未必是NP完全。关键要求是：平均困难，而非仅存在最坏情况困难实例。重要的数论难题包括：

• **整数分解问题**：给定合数 $N = p \cdot q$（$p, q$ 为大素数），求 $p, q$。RSA的安全性基于此。对于$n$位$N$，已知最好的通用算法（数域筛）运行时间为亚指数级 $L_N[1/3, (64/9)^{1/3}]$。
• **离散对数问题**：在循环群 $G$ 中，给定生成元 $g$ 和元素 $h = g^x$，求 $x$。Diffie-Hellman密钥交换和DSA的安全性基于此。在适当群（如大素数域或椭圆曲线群）中，最好的算法（指数积分法）运行时间同样为亚指数级。
• **椭圆曲线离散对数问题**：在椭圆曲线群 $E(\mathbb{F}_p)$ 上，已知 $P, Q = xP$，求 $x$。目前最好的算法（Pollard's rho）是指数级时间 $\mathcal{O}(\sqrt{q})$，其中 $q$ 是子群阶。这使得在相同安全强度下，ECC密钥长度远短于RSA/DSA（如256位ECC ≈ 3072位RSA）。

单向函数 是密码学的基石。形式化定义：函数 $f$ 是单向的，如果（1）对任意输入$x$，计算 $f(x)$ 是容易的（多项式时间）；（2）对任意 $y$ 在 $f$ 的值域中，找到满足 $f(x)=y$ 的 $x$ 是困难的（非均匀概率多项式时间算法成功概率可忽略）。上述数论难题的“求逆”形式可视为单向函数候选。而陷门单向函数（如RSA函数：$f(x) = x^e \mod N$，已知陷门 $d$ 可轻松求逆）是公钥密码学的基础。

**1.5 后量子时代的先声**

当前广泛使用的公钥密码（RSA、ECC、DH）的安全性均基于数论难题。Shor算法（1994）表明，在足够大规模的量子计算机上，整数分解和离散对数问题可在多项式时间内解决。这构成了对现有公钥基础设施的生存性威胁。

格密码学 作为后量子密码的主要候选，其安全性基于最短向量问题或学习带错误问题。这些问题即使在量子计算机上也被认为是困难的。例如，NIST后量子密码标准化进程最终入选的CRYSTALS-Kyber（密钥封装）和CRYSTALS-Dilithium（签名）均基于格问题。其优势在于：计算效率高，密钥尺寸相对较小，且已有坚实的数学理论支撑。

**1.6 实践案例：TLS 1.3 中的安全范式体现**

TLS 1.3（RFC 8446）是当代密码学工程实践的典范，集中体现了本章所述原则。 1. 协议设计遵循柯克霍夫斯原则：所有算法公开，安全仅依赖密钥。 2. 攻击模型防御：协议设计明确抵抗被动监听（IND-CPA）和主动中间人攻击（IND-CCA、认证）。移除了不安全的特性（如静态RSA、CBC模式、重新协商），默认使用前向安全的临时Diffie-Hellman（ECDHE）密钥交换。 3. 安全原语组合：握手阶段使用（EC）DH提供前向安全的共享密钥，使用数字签名（ECDSA/EdDSA）进行服务器（及可选的客户端）认证。记录层使用AEAD密码（如AES-GCM、ChaCha20-Poly1305）同时保障机密性、完整性与认证。 4. 抵抗量子计算威胁的考量：虽然TLS 1.3本身未集成后量子算法，但其设计框架（如支持多个密钥交换算法组）为未来平滑过渡到后量子密码（如集成KEM）预留了空间。NIST已启动在TLS中集成后量子密钥交换的标准化工作。

**1.7 总结与展望**

本章建立了密码学的核心四目标（机密性、完整性、认证、不可否认性），通过历史案例（凯撒、维吉尼亚、恩尼格玛）揭示了安全设计的永恒教训：任何可预测的模式、密钥复用或系统缺陷都可能被利用。现代密码学以柯克霍夫斯原则为纲，通过形式化的攻击模型（CPA/CCA）与安全定义（IND、EUF）进行精确安全评估，其根基深植于计算复杂性理论，特别是基于单向函数与特定数论难题的假设。

然而，Shor算法带来的量子威胁迫使我们展望后量子密码学。格、编码、多变量、哈希等数学路径正在从理论走向标准化与工程化。未来的密码学不仅需要抵御经典与量子计算攻击，还需在资源受限环境（物联网、区块链）、隐私增强技术（零知识证明、同态加密）中不断演进。本书后续章节将深入探讨这些领域的数学原理、算法设计与工程实践。

--- 侧边栏提示（电子版）：“柯克霍夫斯原则 vs 安全通过保密”

• **柯克霍夫斯原则**：算法公开，密钥保密。如AES。安全基于密钥空间与算法强度。
• **安全通过保密**：算法保密。如某些专有加密芯片。风险：一旦算法泄露，系统全盘崩溃；无法获得公众审查。

结论：现代密码学坚定站在柯克霍夫斯原则一边。

脚注： 1. 恩尼格玛的“反射器”设计导致一个关键弱点：一个字母永远不会被加密为自身。这被波兰和英国密码学家利用。 2. IND-CCA安全是许多实际协议（如TLS 1.3的记录层）的最低要求，因为它能抵御重放、密文修改等主动攻击。 3. “可忽略”在密码学中有精确定义：一个函数 $\epsilon(\lambda)$ 是可忽略的，如果对任意多项式 $p(\lambda)$，存在 $\lambda_0$ 使得对所有 $\lambda > \lambda_0$，有 $\epsilon(\lambda) < 1/p(\lambda)$，其中 $\lambda$ 为安全参数（如密钥长度）。 4. Shor算法需要容错量子计算机，其构建仍是巨大工程挑战，但标准化机构（NIST, ETSI）已基于“先存储，后破解”的威胁模型，要求规划迁移路径。

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

现代密码学的四大核心安全目标——机密性（Confidentiality）、完整性（Integrity）、认证（Authentication）与不可否认性（Non-repudiation）——并非孤立存在，而是通过精心设计的密码学原语（primitives）与协议（protocols）相互交织，共同构建起复杂系统的安全基石。这些目标的精确定义与实现方式，直接决定了系统在对抗性环境中的鲁棒性。

机密性 的经典实现是加密（Encryption），其形式化定义为：对于明文空间 $\mathcal{M}$、密钥空间 $\mathcal{K}$ 和密文空间 $\mathcal{C}$，加密算法 $Enc: \mathcal{M} \times \mathcal{K} \rightarrow \mathcal{C}$ 和解密算法 $Dec: \mathcal{C} \times \mathcal{K} \rightarrow \mathcal{M}$ 满足 $Dec(Enc(m,k), k) = m$ 对所有 $m \in \mathcal{M}, k \in \mathcal{K}$ 成立。然而，现代密码学对机密性的要求远超“无法直接读取”。语义安全（Semantic Security）——由Goldwasser和Micali于1984年提出——要求：对于任何两个长度相同的明文 $m_0, m_1$，攻击者无法区分加密 $m_0$ 还是 $m_1$。这通过不可区分性实验（Indistinguishability Experiment）来定义，即IND-CPA安全。一个违反语义安全的典型例子是电子密码本（ECB）模式：相同明文块加密后产生相同密文块。1999年，研究人员用ECB模式加密一张Linux内核logo的图片，密文图片仍清晰可见原始轮廓，暴露了结构信息。这证明ECB模式完全不满足语义安全。

完整性 与认证 常通过消息认证码（MAC） 和认证加密（AEAD） 实现。MAC $Mac: \mathcal{M} \times \mathcal{K} \rightarrow \mathcal{T}$ 生成一个认证标签 $t$，接收方验证 $Verify(m, t, k)$。HMAC（基于散列函数的MAC）是互联网安全基石（如TLS、IPsec）。一个关键区别在于：仅提供完整性的MAC（如HMAC-SHA256）不提供机密性，而AEAD（如AES-GCM、ChaCha20-Poly1305）同时提供机密性、完整性与认证。例如，AES-GCM模式将CTR加密与GHASH认证结合，一个标签同时保证未授权修改可被检测（完整性）与消息来自持有密钥的实体（认证）。2013年发现的Lucky Thirteen攻击针对TLS中的CBC模式，利用计时差异区分填充错误与MAC错误，进而解密部分数据，这凸显了认证必须与加密紧密耦合，分离的设计易产生安全漏洞。

不可否认性 是数字签名的核心属性，与MAC形成鲜明对比。MAC使用共享密钥，发送方与接收方均可生成有效MAC，故发送方可以否认“此MAC可能是接收方自己生成的”。而数字签名（如RSA-PSS、ECDSA、EdDSA）使用私钥签名、公钥验证，只有私钥持有者能生成有效签名，提供可公开验证的不可否认性。1997年，美国数字签名标准（DSS/DSA）因随机数$k$的生成要求过于严格，导致实际实现中多次出现$k$重用（如索尼PS3漏洞、Sony ECDSA实现缺陷），攻击者通过两个签名恢复私钥，直接破坏了不可否认性。这揭示了实现细节对理论安全属性的决定性影响。

这四大目标在协议中的组合是工程艺术。例如，一个安全文件传输协议可能：使用RSA-OAEP或ECDH-ECIES实现机密性；使用HMAC-SHA256或AEAD实现完整性与认证；使用RSA-PSS或ECDSA实现发送方不可否认性。但过度设计或组合不当会引入漏洞。TLS 1.2中，若使用未认证的CBC加密加独立HMAC，易受BEAST、Lucky Thirteen等攻击；而TLS 1.3强制使用AEAD，从根本上消除了此类组合风险。

---

**1.2 历史演进：从古典密码到机械密码的范式转变**

密码学历史是一部攻击者与防御者持续博弈的史诗，每一次技术飞跃都源于对旧有缺陷的深刻反思。

古典密码时代（公元前~19世纪） 的核心是手工操作，安全依赖于算法保密（与柯克霍夫斯原则背道而驰）和语言特征。

• **凯撒密码**（公元前1世纪）：单表替换，密钥空间仅25（忽略恒等映射）。其脆弱性源于**字母频率分布不变**。英语中字母E出现频率约11%，攻击者统计密文频率，最高频字母很可能对应E，从而破解。这催生了**频率分析**——密码分析的第一种系统性方法。
• **维吉尼亚密码**（1586年）：多表替换，使用关键词循环生成密钥流。其密钥空间为 $26^l$（$l$ 为关键词长度）。当 $l$ 足够大时，频率分析失效。但**卡西斯基试验**（1863年）通过寻找密文中重复的字母组合（如“ABC”出现两次），计算其距离，取最大公约数，可推断密钥长度 $l$。例如，密文“VHVSSF”中“VH”重复出现，距离为18，若密钥长度整除18，则可能为3、6、9等。一旦 $l$ 确定，密文被分解为 $l$ 个单表替换，即可用频率分析破解。这揭示了**密钥流周期性**的