密码学简史与核心概念导论

公元前58年，尤利乌斯·凯撒在高卢战争中运用一种简单的替换密码——后世称为“凯撒密码”——来保护军事指令的机密性。这一古老实践标志着密码学作为一门艺术的萌芽，也揭示了人类对安全通信的不懈追求。时至今日，密码学已从战争工具演变为数字社会的基石，支撑着网上银行、电子商务、即时通讯等现代生活的方方面面。然而，在算法公开、攻击者能力日益强大的数字时代，如何系统性地构建安全通信体系，已成为信息科学的核心挑战。本章将引领读者穿越密码学的千年演进，剖析其核心概念与安全范式，为后续深入技术细节奠定坚实基础。

密码学的历史演变

密码学的发展并非线性进步，而是伴随着通信技术与攻击能力的螺旋式上升。从古典的手工加密到现代的数学理论，再到后量子时代的探索，每个阶段都反映了当时社会对安全需求的极致回应。

古代与中世纪：手工密码的萌芽

古代密码学主要依赖于简单的字符替换与移位操作，其设计哲学是“ obscurity through complexity”——通过精巧的手工操作使密文难以解读。最具代表性的当属凯撒密码，其加密过程可形式化为：设明文为字母表中的一个字母 $m$，密钥为整数 $k \in \{1,2,\dots,25\}$，则密文 $c$ 满足 $c = (m + k) \mod 26$。例如，密钥 $k=3$ 时，字母 `A` 变为 `D`，`B` 变为 `E`，依此类推。这种密码的强度完全依赖于密钥的保密，但因其仅有25种可能密钥，穷举攻击仅需片刻。

公元9世纪，阿拉伯学者阿尔·金迪（Al-Kindi）在其著作《破译加密信息手稿》中首次系统描述了频率分析攻击方法。他观察到，任何自然语言中字母出现的频率分布是相对稳定的（如英语中 `E` 最常见），通过统计密文中字母频率并与语言频率表比对，即可推断出替换映射。这一发现彻底击碎了单纯替换密码的安全性，迫使密码设计者寻求更复杂的方案。

1466年，法国外交官布莱斯·德·维吉尼亚（Blaise de Vigenère）提出维吉尼亚密码，这是一种多表替换密码，使用一个关键词循环来选取不同的凯撒移位。例如，关键词 `KEY` 对应的移位序列为 $[10,4,24]$（`K`=10, `E`=4, `Y`=24），对明文 `HELLO` 加密时，依次用这些移位加密每个字母。维吉尼亚密码在随后300年内被视为“不可破译”，直到19世纪中叶，弗里德里希·卡西斯基（Friedrich Kasiski）和查尔斯·巴贝奇（Charles Babbage）独立发现其周期性的弱点，通过确定关键词长度将问题分解为多个 Caesar 密码，从而成功破解。

这一时期密码学的特点是：算法本身通常保密（“security through obscurity”），攻击者主要依赖语言学和统计知识，密码分析更接近艺术而非科学。

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

19世纪末至20世纪上半叶，工业革命催生了机械密码设备，密码学进入机械化时代。最著名的例子是第一次世界大战期间德国使用的ADFGVX密码，它将字母替换为6个符号（A,D,F,G,V,X），并通过列置换混淆。然而，法国密码军官乔治·佩因（Georges Painvin）通过分析符号频率分布与排列规律，最终在1918年破译该密码，影响了马恩河战役的局势。

第二次世界大战将密码学推向高潮。纳粹德国使用的恩尼格玛（Enigma） 机电转子密码机代表了当时机械加密的巅峰。其加密过程可简述为：用户输入一个明文字母，电流通过三个（后来五个）可配置转子，每个转子实现一个字母替换，同时转子每按一次键旋转一次，产生动态替换表；最后电流通过反射器返回，经过相同转子序列，完成加密。恩尼格玛的密钥空间极大：以三转子机为例，转子选择 $3!$ 种，初始位置 $26^3$ 种，插板设置约 $10^{13}$ 种，总密钥空间超过 $10^{16}$。盟军破译恩尼格玛的努力汇集了波兰密码学家马里安·雷耶夫斯基（Marian Rejewski）的数学突破、英国布莱切利园的图灵团队设计的“炸弹”机电计算机，以及大量情报与人为失误的利用。这一成功不仅缩短了战争，更证明了系统化数学方法在密码分析中的决定性作用。

与此同时，美国陆军使用的SIGABA密码机通过增加步进转子避免周期性，成为二战中未被破译的主要 Allied 密码之一。这些经历揭示了一个关键教训：密码系统的安全性不能依赖于设备的物理保密或操作流程的隐蔽，而应建立在可验证的数学基础之上。

现代密码学：理论与算法的革命

1949年，克劳德·香农（Claude Shannon）发表划时代论文《保密系统的通信理论》，首次将密码学置于严谨的信息论框架。他定义了完美保密（Perfect Secrecy） 概念：一个密码系统是完美保密的，当且仅当密文不提供关于明文的任何信息，即 $I(M;C) = 0$，其中 $I$ 为互信息。香农证明，一次一密（One-Time Pad, OTP） 是唯一能实现完美保密的密码体制：密钥与明文等长、完全随机、且仅使用一次。OTP 的加密为 $c = m \oplus k$，其中 $\oplus$ 表示按位异或。尽管 OTP 在理论上无懈可击，但其密钥分发与存储的 practical 难题使其难以大规模应用。

1970年代，密码学从军事和政府机构走向民用领域，两大里程碑事件奠定了现代密码学的基石。1976年，惠特菲尔德·迪菲（Whitfield Diffie）与马丁·赫尔曼（Martin Hellman）发表《密码学的新方向》，提出了公钥密码学的雏形与数字签名的概念，并引入了计算困难性问题（如离散对数）作为安全基础。1977年，罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）共同提出 RSA 算法，首次实现了实用的公钥加密与数字签名。RSA 的安全性基于大整数分解难题：给定 $n = pq$（$p,q$ 为大素数），求 $p,q$ 在计算上不可行。加密过程为 $c = m^e \mod n$，签名过程为 $s = m^d \mod n$，其中 $(e,d)$ 为密钥对，满足 $ed \equiv 1 \mod \phi(n)$。

同年，美国国家标准局（现 NIST）公开征集数据加密标准（DES），最终 IBM 的 Lucifer 算法经修改后成为 DES。DES 采用 56 位密钥、Feistel 网络结构，在1977年被采纳为联邦标准。尽管 DES 在1990年代因密钥过短而被暴力破解（1997年 EFF 的 Deep Crack 机器仅用56小时），但其设计思想（如混淆与扩散）深刻影响了后续分组密码的发展。

1990年代，密码学研究从“设计-攻击”的循环转向形式化安全证明。1991年，米哈伊尔·加德金（Mihir Bellare）和菲利普·罗戈韦（Phillip Rogaway）提出可证明安全（Provable Security） 范式：将密码方案的安全性归约到某个数学难题的困难性。例如，RSA-OAEP 加密方案在随机预言模型下被证明等同于单向性。同时，椭圆曲线密码学（ECC） 兴起，其基于椭圆曲线上离散对数问题（ECDLP），在相同安全级别下密钥更短，更适合资源受限设备。

后量子密码学：量子威胁与应对

1994年，彼得·肖尔（Peter Shor）提出肖尔算法，该量子算法能在多项式时间内解决大整数分解和离散对数问题，直接威胁 RSA、ECC、Diffie-Hellman 等公钥密码体制。同年，洛夫·格罗弗（Lov Grover）提出格罗弗算法，将对称密码的穷举攻击复杂度从 $O(2^n)$ 降为 $O(2^{n/2})$，即 AES-128 的有效安全强度降至 64 位。

量子计算的潜在威胁催生了后量子密码学（Post-Quantum Cryptography, PQC） 研究，旨在设计能抵抗量子攻击的新算法。2016年，NIST 启动 PQC 标准化进程，最终在2022年选定 CRYSTALS-Kyber（基于格的密钥封装机制）、CRYSTALS-Dilithium（基于格的数字签名）、FALCON（基于格的签名）和 SPHINCS+（基于哈希的签名）为首批标准。这些算法的安全性基于格问题（如 Learning With Errors, LWE）、多变量方程或哈希函数，被认为在经典与量子计算下均困难。与此同时，量子密钥分发（QKD） 利用量子物理原理（如海森堡不确定性原理）实现信息论安全的密钥交换，但其实际部署受限于距离与成本。

密码学的历史演变清晰表明：安全需求的升级推动密码理论的革新，而攻击技术的进步又迫使密码设计者不断突破边界。从手工艺术到数学科学，密码学已形成一套完整的方法论体系，其核心即本章后续阐述的安全目标、基本术语、攻击模型与设计原则。

信息安全的核心目标

现代密码学的应用围绕四大核心安全目标展开，这些目标共同构成了信息安全的基石。任何实用的密码体制都旨在满足一个或多个目标，且往往需要组合多种技术实现。

保密性（Confidentiality）

保密性确保信息仅能被授权方访问，防止未授权方获取信息内容。这是密码学最原始的目标。在军事通信中，保密性意味着敌对方即使截获密文，也无法推断出任何关于明文的有意义信息。在商业场景中，保密性保护用户隐私、商业机密与交易数据。

实现保密性的经典方法是加密（Encryption）。设发送方 A 欲向接收方 B 发送保密消息，A 使用 B 的公钥（或共享密钥）对明文 $m$ 加密得到密文 $c$，B 使用对应私钥（或相同密钥）解密恢复 $m$。敌手 C 截获 $c$ 后，在缺乏密钥的情况下应无法推断 $m$ 的任何信息。

一个实用的案例是 HTTPS 协议。当用户在浏览器访问银行网站时，TLS 握手阶段使用非对称加密（如 RSA 或 ECDHE）协商一个对称会话密钥，随后所有 HTTP 数据均用对称加密（如 AES-GCM）保护。这既利用了非对称加密的安全密钥交换，又发挥了对称加密的高效性，确保了传输层的保密性。

值得注意的是，保密性并不等同于“不可读”。一个加密方案可能被破译，但只要在特定时间范围内（如数据有效期）无法被破译，即可认为满足 practical 保密性。这正是计算安全模型的核心思想。

完整性（Integrity）

完整性确保信息在传输或存储过程中未被篡改、插入或删除。攻击者可能无法读取密文内容，但仍可能修改密文以误导接收方。例如，在电子支付中，攻击者可能将转账金额 `100` 元篡改为 `10000` 元。

实现完整性的主要技术是消息认证码（Message Authentication Code, MAC） 或密码学哈希函数。MAC 使用共享密钥生成一个短标签（tag），附加在消息上。接收方用相同密钥重新计算标签，若与收到的标签一致，则消息未被篡改。例如，HMAC（基于哈希的 MAC）结构为 $\text{HMAC}(K,m) = H((K \oplus \text{opad}) \parallel H((K \oplus \text{ipad}) \parallel m))$，其中 $H$ 为哈希函数（如 SHA-256），`opad` 与 `ipad` 为固定填充常量。

更强大的机制是认证加密（Authenticated Encryption, AE），如 AES-GCM 模式，它同时提供保密性与完整性。GCM 基于 Counter 模式加密，并利用 GHASH 函数计算认证标签。实践中，TLS 1.2 及以后版本强制要求使用 AEAD（认证加密带关联数据）套件，如 `TLS_AES_128_GCM_SHA256`。

完整性目标常与保密性结合，但也可独立存在。例如，软件下载时提供的 SHA-256 校验码仅保证完整性，不涉及保密。

认证性（Authentication）

认证性确保通信实体的身份真实，即确认对方是其声称的身份。认证分为两类：数据源认证（确认消息来自声称的发送方）和实体认证（确认通信对方是真实实体）。数字签名是实现数据源认证的核心技术。

在数字签名方案中，发送方 A 使用自己的私钥对消息（或其哈希）进行签名，生成签名 $s$；接收方 B 使用 A 的公钥验证签名。由于私钥仅 A 持有，成功的验证证明消息确实来自 A。例如，RSA 签名：$s = H(m)^d \mod n$，验证时计算 $s^e \mod n$ 并与 $H(m)$ 比较。

认证性在电子商务中至关重要。当用户向网站提交订单时，网站需验证用户身份（如通过数字证书），用户也需验证网站的真实性（防止钓鱼）。这通常通过公钥基础设施（PKI） 实现：可信证书颁发机构（CA）对网站公钥进行数字签名，浏览器内置 CA 根证书以验证网站证书链。

值得注意的是，认证性与不可否认性密切相关，但二者并不等价。认证性关注“身份真实”，而不可否认性关注“行为不可抵赖”。

不可否认性（Non-repudiation）

不可否认性防止通信一方事后否认其曾经执行的操作或发送的消息。这在法律与商业交易中至关重要，例如电子合同、金融交易记录。

数字签名是提供不可否认性的主要手段。由于签名使用发送方私钥生成，而私钥理论上仅其持有，因此发送方无法否认其签名行为。然而，实际中需考虑密钥管理问题：若私钥被盗用，发送方可辩称签名非其本人所为。因此，不可否认性依赖于严格的私钥保护机制与法律框架对数字签名的认可。

一个典型案例是安全电子交易（SET） 协议，它使用双重签名技术：顾客对订单信息签名，同时对支付信息签名，但将两者分开，确保商家只能看到订单，银行只能看到支付，且顾客无法否认任一交易。这体现了不可否认性与隐私保护的平衡。

四大目标的关系与权衡

四大目标并非孤立，而是相互关联、有时相互制约。例如：

• 加密提供保密性，但可能无法提供完整性（如 ECB 模式易受篡改）。
• 认证加密（如 AES-GCM）同时实现保密性、完整性与数据源认证，但需处理认证标签的存储与传输开销。
• 数字签名提供不可否认性与数据源认证，但不提供保密性（签名本身是公开的）。

在实际系统设计中，需根据应用场景权衡取舍。TLS 1.3 的设计即体现了这种权衡：握手阶段使用（EC)DHE 实现前向保密与实体认证，记录层使用 AEAD 算法同时保障保密性、完整性与数据源认证，而数字证书则提供实体认证与不可否认性的基础。

基本术语与密码体制

在深入技术细节之前，有必要明确定义密码学中的基本术语，这些术语是理解后续内容的基石。

核心术语定义

• **明文（Plaintext）**：原始的可读信息，即加密前的数据。记为 $M$ 或 $m$。
• **密文（Ciphertext）**：明文经过加密变换后的不可读形式。记为 $C$ 或 $c$。
• **密钥（Key）**：控制加密与解密过程的参数。密钥的保密性是现代密码学安全的核心。对称密码中加密密钥与解密密钥相同或可相互推导；非对称密码中则包含公钥（公开）与私钥（保密）。
• **加密算法（Encryption Algorithm）**：将明文与密钥作为输入，输出密文的确定性函数。记为 $E$，即 $c = E_k(m)$。
• **解密算法（Decryption Algorithm）**：将密文与密钥作为输入，输出明明的确定性函数。记为 $D$，即 $m = D_k(c)$。
• **密码体制（Cryptosystem）**：由明文空间、密文空间、密钥空间、加密算法族、解密算法族组成的五元组 $\mathcal{S} = (\mathcal{M}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})$，满足 $\forall k \in \mathcal{K}, \forall m \in \mathcal{M}, D_k(E_k(m)) = m$。
• **敌手（Adversary）**：试图破坏密码系统安全性的攻击者。敌手的能力（如计算资源、访问权限）是安全模型的关键参数。

密码体制的分类

根据密钥使用方式，密码体制主要分为对称密码与非对称密码两大类。

对称密码又称秘密密钥密码，其加密与解密使用相同密钥或易相互推导的密钥。主要分为：

• **分组密码（Block Cipher）**：将明文分成固定长度（如 AES 的 128 位）的分组，逐组加密。代表算法：DES、AES、SM4。分组密码的工作模式（如 ECB、CBC、CTR、GCM）决定了多分组数据的处理方式，直接影响安全性与效率。
• **流密码（Stream Cipher）**：将明文视为连续比特流，与密钥流逐位异或生成密文。密钥流由伪随机数生成器（PRNG）基于初始密钥生成。代表算法：RC4（已不安全）、A5/1（GSM）、ChaCha20。

对称密码的优势在于加解密速度快，适合大量数据加密；但密钥分发是挑战，需通过安全通道或密钥交换协议（如 Diffie-Hellman）解决。

非对称密码又称公钥密码，使用密钥对：公钥可公开分发，用于加密或验证签名；私钥保密，用于解密或生成签名。主要类型包括：

• **公钥加密**：如 RSA、ElGamal、ECC 加密。发送方用接收方公钥加密，仅接收方私钥可解密。
• **数字签名**：如 RSA-PSS、ECDSA、EdDSA。发送方用私钥签名，任何持有公钥者均可验证。
• **密钥交换**：如 Diffie-Hellman（DH）、椭圆曲线 Diffie-Hellman（ECDH）。双方通过交换公开

密码分析的基本方法

密码分析（Cryptanalysis）是研究如何在不掌握密钥的情况下恢复明文或密钥的科学，其方法与攻击者的能力和获取的信息直接相关。现代密码学中，攻击模型根据敌手可获取的数据类型进行形式化分类，这种分类直接影响安全性的定义与证明。

攻击模型的形式化分类

1. 唯密文攻击（Ciphertext-Only Attack, COA） 攻击者仅拥有若干密文 $c_1, c_2, \dots, c_n$，试图推断出对应的明文 $m_1, m_2, \dots, m_n$ 或密钥 $k$。这是能力最弱的攻击模型，但现实中常见（如截获加密通信流）。 *案例*：1940年，美国数学家克劳德·香农分析二战中日本“ PURPLE”密码机时，仅通过密文频率统计与已知日文电报格式，成功推断出密码结构。古典替换密码（如凯撒密码）在唯密文攻击下几乎立即崩溃，因为字母频率分布直接暴露替换映射。

**