知识库

The Joy of Cryptography - 密码学的乐趣

20分钟阅读

The Joy of Cryptography 密码学的乐趣

俄勒冈州立大学 Mike Rosulek 编写的本科密码学教材。核心主题是可证明安全性（provable security）——将模糊的”安全”概念拆解为精确定义，并用数学方法证明密码方案满足这些定义。

核心思想

本书不是告诉你”该用哪个加密算法”的手册，而是教你如何思考安全：

  • Security（安全）：密码学是关于控制信息访问的。将”安全”拆解为具体目标：机密性（confidentiality）、真实性（authenticity）、完整性（integrity）
  • Provable（可证明）：可以形式化地定义安全的含义，然后用数学证明安全声明。全书的主线是安全构件的组合逻辑
  • Fundamentals（基础）：入门级教材，覆盖基础概念。读完后能应对大多数实际场景，也具备学习高级主题的能力

全书的安全声明都是条件性的——如果 X 安全，那么 Y 安全。最终追溯到少数几个被猜想为安全的密码学原语（如 PRG），其余都是基于这些原语的可证明安全构造。

全书结构（共 15 章 + 第 0 章）

第 0 章：概念与符号复习

  • 对数与指数、模运算、字符串、函数、概率、伪代码符号、渐近复杂度（Big-O）
  • 是后续章节的数学基础

第 1 章：一次一密 & Kerckhoffs 原则

Kerckhoffs 原则（1883）：

“系统的安全性不应依赖于算法的保密性；即使算法落入敌手手中，也不应造成麻烦。”

  • 所有安全性应集中在密钥的保密性上，而非算法的保密性
  • 密钥泄露后只需换密钥，无需重新发明加密算法
  • 多用户可以使用相同算法、不同密钥

一次一密（One-Time Pad, OTP）：

  • KeyGen：从 {0,1}^λ 中均匀采样密钥 k
  • Enc(k, m) = k ⊕ m
  • Dec(k, c) = k ⊕ c
  • 完美保密：密文对攻击者而言完全是均匀随机的
  • 缺点：密钥必须和明文一样长，且一个密钥只能用一次

什么”不是密码学”：

  • Base64 编码/解码（无秘密，无安全性）
  • 二进制表示（仅是数据格式）
  • 隐写术（隐藏通信存在本身，不是密码学的范畴）

第 2 章：可证明安全基础

这是全书最重要的方法论章节。教你如何写安全定义、证明安全、演示不安全。

语法 vs 正确性 vs 安全性：

  • 语法（Syntax）：算法的输入输出类型定义（如 Enc 输入密钥+明文，输出密文）
  • 正确性（Correctness）：解密总能还原原始明文（与攻击者无关）
  • 安全性（Security）：在攻击者存在时的行为保证

安全定义的两种风格：

  1. Real-vs-Random（真密文 vs 随机串）：

    • 直觉：“密文看起来像随机垃圾”
    • 形式化：两个库（一个真加密、一个输出随机串）对所有调用程序来说行为不可区分

  2. Left-vs-Right（左明文加密 vs 右明文加密）：

    • 直觉：“m_L 的密文和 m_R 的密文看起来一样”
    • 形式化：两个库（分别加密左右明文）不可区分

混合论证（Hybrid Technique）：

  • 证明两个库不可区分的核心技术
  • 通过一系列中间库（混合体）逐步过渡，每一步差异都可归约到某个底层安全假设
  • 总优势 = 各步优势之和

攻击 = 区分器：

  • 展示一个方案不安全 = 构造一个能有效区分两个安全库的程序
  • 这是密码学中”攻击”的精确定义

第 3 章：秘密共享（Secret Sharing）

问题：将一个秘密拆成 n 份（份额 share），使得：

  • 任意 ≥ t 份可以重建秘密（正确性）
  • 任意 < t 份完全不泄露秘密信息（安全性）

安全定义要点：

  • 低于阈值时，份额必须完全不泄露任何信息（不是”泄露一点点”）
  • 这是一个很强的要求：信息泄露是 0-1 的，不是渐变的

不安全的反例：

  • 把秘密直接切成 n 段——拿到 1 份就泄露了 1/n 的信息，违反安全定义

2-out-of-2 方案：

  • 用一次一密的思想：s1 = 随机，s2 = m ⊕ s1
  • 单独一个份额完全均匀随机

Shamir 秘密共享（t-out-of-n）：

  • 基于多项式插值
  • 将秘密编码为常数项，生成 t-1 次随机多项式
  • 每个用户得到多项式上的一个点（x_i, f(x_i)）
  • 任意 t 个点可以插值还原多项式（从而得到常数项 = 秘密）
  • 任意 t-1 个点什么也确定不了

第 4 章：基于难解计算的密码学

从信息论安全（如 OTP）过渡到计算安全：

  • 计算不可行（Computationally Infeasible）：多项式时间算法做不到的事情
  • 可忽略的成功概率（Negligible）：比任何多项式的倒数衰减都快，记为 negl(λ)
  • 不可区分性（Indistinguishability）：两个分布如果没有多项式时间算法能以不可忽略的优势区分，就称计算不可区分

生日悖论：

  • 从 N 个元素中有放回采样，约 √N 次采样后出现碰撞的概率 > 50%
  • 对密码学的影响：生日攻击的复杂度是 O(2^(n/2))，而不是 O(2

安全参数 λ 的意义：增大 λ 会让方案更难被攻破（代价是效率降低）

第 5 章：伪随机生成器（PRG）

PRG（Pseudorandom Generator）：

  • 输入：短的均匀随机种子（λ 位）
  • 输出：长的”看起来随机”的串（比如 2λ 位）
  • 安全性：输出分布与均匀分布计算不可区分

关键直觉：

  • “一茶匙水倒入海洋”——虽然 PRG 输出只占可能空间的极小一部分，但多项式时间的观察者无法察觉
  • 伪随机性是生成过程的属性，不是单个字符串的属性

PRG 的存在性：

  • 没有已知的可证明安全的 PRG（证明存在性等于解决 P vs NP 问题）
  • 实际使用的 PRG 都是猜想安全的候选方案
  • 实际中通常从分组密码（block cipher）构造 PRG

PRG 的扩展（Hybrid Proof 的典型应用）：

  • 如果存在长度加倍的 PRG，就可以构造任意多项式长度伸展的 PRG
  • 使用混合论证证明安全性

应用：

  • 流密码（Stream Cipher）：用 PRG 生成密钥流，与明文异或
  • 对称棘轮（Symmetric Ratchet）：每次用当前状态生成输出和下一状态

第 6 章：伪随机函数 & 分组密码

PRF（Pseudorandom Function）：

  • 直觉：模拟一个巨大的随机查找表（有 2^in 个条目）
  • 形式化：带密钥的函数 F(k, x)，与真正的随机函数（懒加载的关联数组）不可区分
  • 密钥只有 λ 位，但效果等价于 2^in × out 位的共享随机数

分组密码（Block Cipher = PRP）：

  • 伪随机置换（Pseudorandom Permutation）
  • 输入和输出长度相同（分组长度），且是双射（可逆）
  • AES 是最著名的分组密码

PRF 与 PRP 的关系：

  • PRP 一定是 PRF（生日悖论范围内）
  • 可以用 PRF 构造 PRP（Feistel 网络等）

共享一个短密钥 = 共享一个指数大的随机查找表的效果

第 7 章：选择明文攻击安全（CPA Security）

确定性加密的局限：

  • 相同明文 → 相同密文 → 泄露明文是否重复

CPA 安全：

  • 攻击者可以选择任意明文并获得其加密（选择明文攻击）
  • 仍然无法区分 m_L 和 m_R 的密文
  • 引入随机化加密（每次加密引入随机性，如随机 IV）

基于 PRF 的 CPA 安全加密：

  • 思路：选一个随机 r，密文 = (r, F(k, r) ⊕ m)
  • 类似”随机位置的 one-time pad”
  • 因为 PRF 让每个 F(k, r) 看起来像独立的随机串

第 8 章：分组密码工作模式

将分组密码（只能处理固定长度块）扩展到任意长度消息：

  • ECB 模式：每个块独立加密 —— 不安全（相同明文块 → 相同密文块）
  • CBC 模式：密文块 = Enc(k, 明文块 ⊕ 上一个密文块) —— CPA 安全
  • OFB 模式：生成密钥流，与明文异或（类似流密码）—— CPA 安全
  • CTR 模式：用计数器作为 PRF 输入生成密钥流 —— CPA 安全，可并行

填充与密文窃取：

  • 当明文长度不是块大小的整数倍时需要填充
  • PKCS#7 填充等

第 9 章：选择密文攻击（CCA）

Padding Oracle 攻击：

  • 攻击者发送修改后的密文，观察解密是否报错（填充是否合法）
  • 可以逐字节恢复明文
  • 说明仅有 CPA 安全是不够的

CCA 安全：

  • 攻击者除了加密预言机，还有解密预言机
  • 但不能用挑战密文本身去解密（否则安全毫无意义）
  • 比 CPA 安全更强的安全性概念

CCA 安全的方案能抵御”攻击者构造密文并观察解密结果”的攻击

第 10 章：消息认证码（MAC）

MAC（Message Authentication Code）：

  • 目的：认证（authenticity），不是加密（confidentiality）
  • 只有知道密钥的人才能生成有效的标签（tag）
  • 安全性：攻击者即使获得了多个消息的 MAC 标签，也无法为新消息伪造有效标签

PRF 即 MAC：

  • 安全的 PRF 直接就是安全的 MAC
  • 因为不知道密钥的攻击者无法预测 F(k, m) 的值

长消息的 MAC：

  • CBC-MAC、ECBC-MAC 等构造
  • 用分组密码处理多块消息

Encrypt-then-MAC（先加密后 MAC）：

  • 对密文计算 MAC，附在密文后面
  • 解密前先验证 MAC，无效则直接拒绝
  • CPA 安全加密 + 安全 MAC → CCA 安全
  • 这是构造 CCA 安全加密的标准方法

加密解决”别人看不到内容”，MAC 解决”内容没被篡改”。两者独立，缺一不可。

第 11 章：哈希函数

安全属性：

  • 抗碰撞（Collision Resistance）：难以找到 x ≠ y 使得 H(x) = H(y)
  • 第二原像抗性（Second Preimage Resistance）：给定 x，难以找到 y ≠ x 使得 H(x) = H(y)
  • 原像抗性（Preimage Resistance / One-way）：给定 h，难以找到 x 使得 H(x) = h

Merkle-Damgård 构造：

  • 将定长压缩函数扩展为任意长度输入的哈希函数
  • MD5、SHA-1、SHA-2 都使用此结构

长度扩展攻击（Length-Extension Attack）：

  • Merkle-Damgård 结构的固有问题
  • 知道 H(m) 可以计算 H(m ‖ pad(m) ‖ x)，无需知道 m
  • 后果：不要用 H(k ‖ m) 当 MAC（HMAC 是正确做法）

第 12 章：认证加密 & AEAD

AE（Authenticated Encryption）：

  • 同时提供机密性和真实性
  • 解密失败时返回错误，不泄露任何部分信息

AEAD（AE with Associated Data）：

  • 关联数据（AD）：需要认证但不需要加密的数据
  • 比如：序列号、时间戳、发送者/接收者地址
  • 密文长度只依赖明文长度，不依赖 AD 长度

GCM 模式（Galois/Counter Mode）：

  • 基于 CTR 模式 + GHASH（通用哈希）
  • 高性能，可并行
  • 是实际应用中最常用的 AEAD 方案之一

Carter-Wegman MAC：

  • 基于通用哈希函数（UHF）的 MAC
  • 比基于 PRF 的 MAC 更高效
  • 通用哈希函数只需保证”盲碰撞”困难，比抗碰撞哈希弱得多

第 13 章：RSA & 数字签名

RSA 函数：

  • 密钥生成：选两个大素数 p, q，N = pq，选 e，计算 d ≡ e^(-1) mod φ(N)
  • 公钥：(N, e)，私钥：d
  • 加密/签名：基于模幂运算

RSA 的难解性等价链（Theorem 13.12）： 以下问题在多项式时间意义下等价（能解一个就能解所有）：

  1. 分解 N = pq
  2. 计算 φ(N)
  3. 给定 e，计算 d
  4. 找到模 N 的非平凡单位平方根

找到非平凡单位平方根 → 用 gcd(x±1, N) 分解 N

数字签名：

  • 公钥密码学的核心应用之一
  • 私钥签名，公钥验证
  • 任何人都可以验证签名的真实性

中国剩余定理（CRT）：

  • 模 N = pq 的计算可以分解到模 p 和模 q 上分别进行，再合并结果
  • 用于加速 RSA 私钥运算（约快 4 倍）

第 14 章：Diffie-Hellman 密钥交换

循环群：

  • 由一个生成元 g 的所有幂次构成的群
  • 离散对数问题（DLP）：给定 g 和 g^x，求 x

DH 密钥交换：

  • Alice 选 a，发送 g^a；Bob 选 b，发送 g
  • 双方都计算 g^(ab) 作为共享密钥
  • 攻击者只能看到 g^a 和 g^b，难以计算 g

DDH 假设（Decisional Diffie-Hellman）：

  • (g^a, g^b, g^(ab)) 与 (g^a, g^b, g^c)（c 随机）计算不可区分
  • 是许多公钥方案的安全基础

第 15 章：公钥加密

公钥加密 vs 对称加密：

  • 对称加密：双方共享同一个密钥
  • 公钥加密：任何人可以用公钥加密，只有私钥持有者能解密

安全定义：

  • 公钥版本的 CPA 安全（IND-CPA）
  • 因为攻击者知道公钥，可以自己加密任意消息，所以”选择明文攻击”是天然的

ElGamal 加密：

  • 基于 DDH 假设
  • 密文：(g^r, h^r ⊕ m)，其中 h = g^a 是公钥
  • 本质上是”用 DH 协商一个临时密钥，然后一次性加密”

混合加密（Hybrid Encryption）：

  • 公钥加密只用于加密一个随机的对称密钥
  • 实际数据用对称加密（速度快）
  • 实际系统的标准做法

重要概念地图

信息论安全
  ├─ One-Time Pad (完美保密)
  └─ Shamir 秘密共享

计算安全基础
  ├─ 不可忽略函数 / 多项式时间
  ├─ 不可区分性
  └─ 生日悖论

对称密钥原语
  ├─ PRG (伪随机生成器)
  ├─ PRF / PRP (伪随机函数/置换 = 分组密码)
  ├─ MAC (消息认证码)
  └─ 哈希函数

加密安全性
  ├─ 一次性安全
  ├─ CPA 安全 (选择明文攻击)
  │  └─ 工作模式: CBC, CTR, OFB
  ├─ CCA 安全 (选择密文攻击)
  │  └─ Encrypt-then-MAC 构造
  └─ AE / AEAD (认证加密)
     └─ GCM 模式

公钥密码学
  ├─ 数论基础: 模运算, CRT, 群论
  ├─ RSA (基于大数分解假设)
  ├─ Diffie-Hellman (基于离散对数假设)
  ├─ 数字签名
  ├─ ElGamal 加密
  └─ 混合加密

核心方法论

  1. 定义安全：用”库不可区分”的方式写安全定义（攻击者 = 调用程序）
  2. 构造方案：定义算法（KeyGen, Enc, Dec, …）
  3. 证明安全：用混合论证，将安全性归约到底层原语的安全性
  4. 攻击 = 区分器：不安全 = 存在高效的区分程序

“密码学是将很多不同问题转化为密钥管理问题的工具。” — Lea Kissner

与其他知识的关联

  • 《Rust算法与数据结构》 — 算法复杂度分析（Big-O）是理解密码学计算假设的基础
  • 对称加密 → AES、GCM 等实际标准
  • 公钥加密 → TLS/SSL、HTTPS、数字证书
  • 哈希函数 → 区块链、密码学货币、文件完整性校验
  • 秘密共享 → 分布式密钥管理、多方计算

阅读建议

  • 本书是 CC BY-NC-SA 4.0 开源教材，最新版在 joyofcryptography.com
  • 适合有离散数学基础的 CS 本科生
  • 每章末尾有练习题，是理解概念的重要方式
  • 重点掌握第 2 章的安全定义方法和混合论证——这是后续所有章节的方法论基础

关系图谱

反向链接