《密码学的乐趣》- The Joy of Cryptography - Mike Rosulek
基本信息
- 书名: The Joy of Cryptography（密码学的乐趣）
- 作者: Mike Rosulek（Oregon State University）
- 版本: Draft of January 3, 2021
- 许可: Creative Commons BY-NC-SA 4.0
- 原文件: /books/密码学.pdf
- 页数: 286 页
- 处理日期: 2026-09-01
- 处理方法: pdf-inspector 文本提取（text_based）
书籍定位与特色
这是一本美国本科密码学教材，源自 Oregon State University 的 CS427 课程讲义。作者 Mike Rosulek 采用 code-based games（基于代码的游戏） 风格来表达所有安全定义和证明，这是本书最大的教学创新。
核心哲学：密码学不是关于”算法如何工作”，而是关于”为什么算法是安全的”。安全性是一个全局性质——无法通过具体例子来证明，必须在抽象层面理解。
先修要求：
- 离散数学（模运算、概率、组合、证明技巧）
- 算法与数据结构
- 计算理论（推荐）
不涵盖：PGP、Tor、Signal、TrueCrypt、比特币、黑客技术——这是一本理论基础书，不是应用手册。
全书结构（共15章 + 第0章预备知识）
第0章：概念与符号复习
- 对数与指数、模运算、字符串、函数、概率
- 伪代码符号约定
- 渐进复杂度（Big-O）
第一部分：对称密码学基础
- 第1章：一次一密 & Kerckhoffs 原则
- 第2章：可证明安全的基础（安全定义的写法、攻击与证明、混合技术）
- 第3章：秘密共享（Shamir 门限方案、多项式插值、视觉秘密共享）
- 第4章：基于难解计算的密码学（计算不可行、可忽略概率、不可区分性、生日悖论）
第二部分：伪随机性与分组密码
- 第5章：伪随机生成器（PRG）定义、构造与扩展
- 第6章：伪随机函数（PRF）与伪随机置换（PRP）、分组密码、Switching Lemma
- 第7章：选择明文攻击（CPA）安全性
- 第8章：分组密码工作模式（ECB/CBC/CTR/OFB、CPA安全、填充与密文窃取）
- 第9章：选择密文攻击（CCA）、Padding Oracle 攻击
第三部分：认证与哈希
- 第10章：消息认证码（MAC）定义、CBC-MAC、Encrypt-then-MAC
- 第11章：哈希函数（碰撞抗性、Merkle-Damgård 构造、长度扩展攻击）
- 第12章：认证加密 & AEAD（定义、Encrypt-then-MAC、Carter-Wegman MAC、GCM 模式）
第四部分：公钥密码学
- 第13章：RSA & 数字签名（RSA函数、CRT、RSA签名、哈希RSA签名）
- 第14章：Diffie-Hellman 密钥协商（循环群、离散对数、DDH假设）
- 第15章：公钥加密（安全定义、ElGamal加密、混合加密）
核心概念笔记
1. Code-Based Games 方法论
本书的核心教学方法——用”两个具有相同接口但内部实现不同的库（library）“来定义安全性：
- 安全 = 攻击者无法区分两个库的行为
- 每个安全定义都遵循同一种模式：真实库 vs 理想库
- 证明 = 通过一系列混合（hybrid）库逐步转换，每一步都基于某个密码学原语的安全性
- 攻击 = 编写一个调用程序，能够显著区分两个库
优势：统一了所有安全定义的表达方式，使得证明过程变成了”构造性重写规则”的应用，降低了抽象难度。
2. 安全性定义索引（全书关键定义）
本书末尾附有安全定义索引，以下是最重要的：
| 定义 | 章节 | 描述 |
|---|---|---|
| 一次一密密文一致性 | 2.5 | 对称加密基础 |
| 一次保密性（OT安全） | 2.6 | 单消息安全 |
| 秘密共享门限安全 | 3.3 | t-out-of-n 门限 |
| 伪随机生成器（PRG） | 5.1 | 计算不可区分 |
| 伪随机函数（PRF） | 6.1 | 函数级不可区分 |
| 伪随机置换（PRP） | 6.6 | 置换级不可区分 |
| 强伪随机置换（SPRP） | 6.13 | 正反双向不可区分 |
| CPA安全（对称加密） | 7.1 | 选择明文攻击 |
| CPA$安全 | 7.2 | 伪随机密文 |
| CCA安全 | 9.1 | 选择密文攻击 |
| MAC安全 | 10.2 | 消息认证码不可伪造 |
| 碰撞抗性 | 11.1 | 哈希函数安全性 |
| 数字签名安全 | 13.6 | 存在性不可伪造 |
| 密钥协商安全 | 14.4 | DH密钥交换 |
| DDH假设 | 14.5 | 判定性Diffie-Hellman |
| 公钥CPA安全 | 15.1 | 公钥加密基本安全 |
3. Kerckhoffs 原则
密码系统的安全性不应依赖于算法的保密，而应只依赖于密钥的保密。
- 敌人了解系统（包括算法）
- 秘密只有密钥
- 这是现代密码学的基石
4. 混合技术（Hybrid Technique）
证明安全性的核心工具：
- 目标：证明 Library L 和 Library R 不可区分
- 方法：构造一系列混合库 L = H₀, H₁, H₂, …, Hₙ = R
- 每对相邻混合库的不可区分性基于某个密码学假设
- 最终结论：L 和 R 不可区分（传递性）
5. 生日悖论与边界
- n 个元素中随机采样 q 次，发生碰撞的概率 ≈ q²/(2n)
- 对于 N 空间，约 √N 次采样后碰撞概率达到 50%
- 这解释了为什么哈希函数输出长度需要是安全参数的2倍（抗碰撞需要 2^n/2 次操作）
重要知识点
分组密码工作模式
- ECB：绝对不要用！相同明文块产生相同密文块，信息泄露严重
- CBC：经典模式，需要 IV，CPA安全
- CTR：将分组密码转化为流密码，可并行加密，CPA安全
- OFB：输出反馈模式，生成密钥流
- GCM：Galois/Counter Mode，提供认证加密（AEAD），CTR + GHASH
加密与认证的组合
正确顺序：Encrypt-then-MAC（先加密再认证）
- 密文被MAC保护
- 解密前先验证MAC，防止Padding Oracle攻击
- 错误顺序（MAC-then-encrypt、Encrypt-and-MAC）存在安全漏洞
哈希函数长度扩展攻击
Merkle-Damgård 构造的哈希函数（MD5、SHA-1、SHA-2）存在长度扩展攻击：
- 已知 H(m) 和 len(m)，可以计算 H(m ‖ padding ‖ m’)
- 影响：不能用 H(key ‖ message) 作为 MAC
- 解决方案：HMAC 双层结构
RSA 要点
- 基于大整数分解困难性
- 教科书RSA不安全（同态性、确定性）
- 实际使用需要填充方案（OAEP等）
- CRT（中国剩余定理）可加速 RSA 私钥运算约 4 倍
Diffie-Hellman 密钥协商
- 基于离散对数困难性（更准确地说，DDH假设）
- 双方无需预先共享密钥即可协商出共享秘密
- 本身不提供认证，易受中间人攻击
- 实际使用需要认证机制（如数字签名）
阅读建议
适合人群：
- 计算机科学专业本科生
- 想从理论层面理解”为什么安全”而非只知道”怎么用”的工程师
- 准备学习更高级密码学（零知识证明、后量子密码等）的读者
学习路径：
- 先确保第0章预备知识扎实
- 第1-4章建立安全思维框架（最重要的是第2章）
- 第5-12章系统学习对称密码学
- 第13-15章进入公钥密码学
- 对照书末的安全定义索引复习巩固
与其他密码学教材的区别：
- 比 Katz & Lindell 更入门，更注重直觉
- 比 Stinson 更现代，强调 provable security
- Code-based games 风格是独特的教学创新
关联笔记
- 《密码学的乐趣》-The Joy of Cryptography-Mike Rosulek — （本书）
- 待补充：更多密码学相关笔记
状态
- 处理状态: done（全文本提取，完整结构整理）
- 内容质量: 高（text_based PDF，pdf-inspector 提取质量好）
- 价值评级: ★★★★☆（优秀的本科密码学理论教材）