密码学入门

一份从零开始的密码学入门笔记。从凯撒密码到后量子加密，重点讲"为什么这么设计"（费曼式 📌 讲解），覆盖对称加密、非对称加密、哈希、数字签名、密钥交换、PKI 到现代前沿。

图表在 /密码学入门/diagrams/ 目录。图注名即原图文件名（如图注"图 1 · 密码学全景"对应 图1_密码学全景.d2 / 图1_密码学全景.d2.svg），改图请编辑同名 .d2 源文件后运行 scripts/build-d2.ps1 重新渲染。

怎么用这份笔记

学习/复习 → 顺序看正文，重点看 📌 类比和"为什么"
查术语 → 翻 附录 A 速查表
用工具 → 翻 附录 B OpenSSL 等命令速查
检验 → 做 附录 C 自测题，盖住答案自答

1 · 密码学全景

$图 1 \xb7 密码学全景$

1.1 密码学解决什么问题

密码学不是"把数据搞乱"，而是用数学方法解决四个核心问题：

问题	术语	通俗解释
保密性	Confidentiality	只有指定的人能看懂内容
完整性	Integrity	数据没被篡改过
认证	Authentication	确认对方身份
不可否认	Non-repudiation	发送方不能抵赖"我没发过"

TIP

📌 打个比方：密码学就像邮局系统——

保密性：信封密封，别人拆不开
完整性：信封上有火漆印章，拆过就有痕迹
认证：信上有寄信人签名，能验真伪
不可否认：签名是唯一的，寄信人不能说"不是我寄的" :::

1.2 密码学的三大分支

密码学
├── 对称加密（一把钥匙开锁）
│   ├── 流密码：RC4, ChaCha20
│   └── 分组密码：DES, AES, SM4
├── 非对称加密（两把钥匙：公钥+私钥）
│   ├── RSA
│   ├── ECC（椭圆曲线）
│   └── DH（密钥交换）
└── 哈希函数（不可逆指纹）
    ├── MD5（已不安全）
    ├── SHA-1（已不安全）
    └── SHA-256/512, SM3

1.3 Kerckhoffs 原则

1883 年，Kerckhoffs 提出了密码学的黄金法则：

密码系统的安全性应只依赖于密钥的保密性，而不应依赖于算法的保密性。

:::tip 📌 为什么算法要公开？因为"保密算法"等于"把锁的设计图藏起来"——一旦设计图泄露，所有锁都失效。而公开算法等于"锁的设计图人人可见，但只有有钥匙的人能开"——即使你知道锁的内部结构，没有钥匙也打不开。公开算法还能让全世界的研究者帮你找漏洞。

2 · 古典密码

2.1 凯撒密码：最简单的替换密码

凯撒密码把每个字母向后移固定位数。比如移 3 位：A→D, B→E, ..., X→A。

明文：  HELLO
密钥：  3（右移 3 位）
密文：  KHOOR

加密公式：C = (P + K) mod 26 解密公式：P = (C - K) mod 26

TIP

📌 凯撒密码为什么弱？只有 25 种可能的密钥（移 1~25 位），暴力试一遍就破了。但它体现了密码学的基本思路：用一个参数（密钥）控制变换规则。

2.2 维吉尼亚密码：多表替换

维吉尼亚密码用一个密钥词组循环移位，每个字母用不同的位移量：

明文：  ATTACKATDAWN
密钥：  LEMONLEMONLE
密文：  LXFOPVEFRNHR

每个位置的位移 = 密钥对应字母的序号（L=11, E=4, M=12, O=14, N=13）。

TIP

📌 维吉尼亚密码为什么比凯撒强？同一个字母在不同位置被加密成不同字母，简单的频率分析失效了。它统治了密码学 300 年，被称为"不可破译的密码"（Le Chiffre Indéchiffrable）。

📌 最终怎么破的？19 世纪，Babbage 和 Kasiski 各自发现了破法：如果密钥长度是 n，那么每隔 n 个位置的字母用的是同一个凯撒密码。先用重复密文段猜出密钥长度，再对每组做频率分析。

2.3 一次性密码本（OTP）：理论最安全

OTP 的规则极其简单：明文和等长的随机密钥逐位 XOR。

明文：  01001011
密钥：  11010100
密文：  10011111  （XOR 结果）

TIP

📌 OTP 为什么理论不可破？香农在 1949 年证明了：如果密钥真正随机、只用一次、和明文等长，则 OTP 满足完美保密（Perfect Secrecy）——即使攻击者有无限计算能力，也无法推出明文。因为对任何可能的明文，都存在一个密钥能产生同样的密文，无法区分。

📌 为什么实际不用 OTP？密钥要和明文一样长，且只能用一次。传 1GB 文件就要先安全传 1GB 密钥——那为什么不直接传文件？OTP 用于冷战时期的热线电话（莫斯科-华盛顿），密钥由外交官用硬盘物理运送。

2.4 古典密码的教训

教训	现代密码的改进
密钥空间太小 → 暴力破解	AES-256 密钥空间 2^256 ≈ 10^77
算法保密 → 泄露即全灭	Kerckhoffs 原则：算法公开，只保密钥
频率分析 → 统计攻击	现代分组密码混淆+扩散，消除统计特征
密钥重复使用 → 信息泄露	每次加密用随机 IV/Nonce，不重复

3 · 对称加密

$图 2 \xb7 对称加密流程$

3.1 什么是对称加密

一把密钥同时用于加密和解密。发送方和接收方必须事先共享同一把密钥。

Alice                          Bob
  │                              │
  │  共享密钥 K                    │
  │  ─────────────────────────── │
  │                              │
  │  加密: C = E(Key, P)          │
  │  ──── 密文 C ──────────────→ │
  │                              │  解密: P = D(Key, C)

TIP

📌 打个比方：对称加密像一把家门钥匙——锁门和开门用的是同一把。你和家人都有这把钥匙，外人没有就进不来。问题是：怎么把钥匙安全地给家人？ 这就是"密钥分发问题"，非对称加密来解决。

3.2 DES：曾经的王者

DES（Data Encryption Standard）由 IBM 设计、NSA 修改，1977 年成为美国标准。

分组大小：64 位（8 字节）
密钥长度：56 位（有效），64 位中 8 位是校验位
结构：Feistel 网络——16 轮替换和置换

Feistel 网络（每轮）：
  L_i = R_{i-1}
  R_i = L_{i-1} XOR F(R_{i-1}, K_i)

  → 加密和解密用同一结构，只是子密钥顺序反转

TIP

📌 DES 为什么退役？56 位密钥只有 2^56 ≈ 7.2×10^16 种可能。1998 年，EFF 用 25 万美元的专用机器在 56 小时内暴力破解了 DES。现在普通电脑几小时就能破。

📌 3DES 不是新算法：用 3 把 DES 密钥依次加密 C = E(K3, D(K2, E(K1, P)))，有效密钥长度 168 位。但速度只有 DES 的 1/3，且 64 位分组太小（生日攻击在 2^32 ≈ 4GB 数据后出现），已逐步淘汰。

3.3 AES：现代对称加密之王

AES（Advanced Encryption Standard）由 Joan Daemen 和 Vincent Rijmen 设计（原名 Rijndael），2001 年成为美国标准。

分组大小：128 位（16 字节）
密钥长度：128 / 192 / 256 位（分别 10/12/14 轮）
结构：代换-置换网络（SPN），非 Feistel

AES 每轮四步：

1. SubBytes    — 字节替换（S 盒，非线性变换，消除统计特征）
2. ShiftRows   — 行移位（扩散，打乱字节位置）
3. MixColumns  — 列混淆（GF(2^8) 上的矩阵乘法，进一步扩散）
4. AddRoundKey — 轮密钥加（与子密钥 XOR，引入密钥）

TIP

📌 混淆与扩散（Shannon 提出的两大原则）：

混淆 (Confusion)：密钥和密文的关系尽量复杂 → SubBytes + AddRoundKey
扩散 (Diffusion)：明文每 1 位变化影响密文尽可能多位 → ShiftRows + MixColumns

📌 AES 为什么安全？经过 20 多年的全球分析，没有找到比暴力破解更快的攻击方法。AES-128 足够安全，AES-256 用于绝密级。量子计算机对 AES 的威胁只是把密钥空间减半（Grover 算法），AES-256 量子下仍等效 AES-128，依然安全。

3.4 SM4：中国国密算法

SM4 是中国密码管理局发布的分组密码标准，用于无线局域网等。

分组大小：128 位
密钥长度：128 位
结构：Feistel 变体，32 轮

TIP

📌 SM4 vs AES：两者安全强度相当（都是 128 位分组+128 位密钥）。SM4 轮数更多（32 vs 10），但每轮更简单。国内政务/金融系统要求使用 SM4 替代 AES。

3.5 流密码：ChaCha20

流密码不分组，而是用密钥生成伪随机流，和明文逐位 XOR：

密钥流 = PRF(Key, Nonce)  → 无限长伪随机流
密文 = 明文 XOR 密钥流

ChaCha20：Google 在 TLS 中推广的流密码，替代 RC4。

TIP

📌 ChaCha20 vs AES：AES 有硬件加速（AES-NI 指令），有硬件时 AES 更快。没有硬件加速时（手机/物联网），ChaCha20 更快且更安全。ChaCha20 + Poly1305 是 TLS 1.3 的推荐组合。

4 · 分组密码模式

4.1 为什么需要"模式"

分组密码一次只加密固定长度（AES = 16 字节）。要加密更长的数据，需要定义如何分组处理——这就是"模式"。

4.2 ECB 模式：最简单但最危险

明文块1 → AES → 密文块1
明文块2 → AES → 密文块2
明文块3 → AES → 密文块3
（每块独立加密，无关联）

TIP

📌 ECB 为什么危险？相同的明文块加密后得到相同的密文块。如果加密一张图片，密文的图案会暴露原图轮廓。著名的"ECB 企鹅"图就是用 ECB 加密 Linux 企鹅 logo 后，密文仍然能看出企鹅形状。永远不要用 ECB。

4.3 CBC 模式：链式拼接

C_0 = IV
C_i = E(Key, P_i XOR C_{i-1})

每个明文块先和前一个密文块 XOR，再加密。第一个块和 IV（初始化向量）XOR。

TIP

📌 CBC 的关键：IV 必须不可预测（不一定要保密，但每次加密要用新的随机 IV）。如果 IV 重复，相同的明文+相同 IV 会产生相同的第一块密文，泄露信息。

📌 CBC 的缺点：加密不能并行（每块依赖前一块）。如果某块密文损坏，只影响当前块和下一块的解密（自同步）。

4.4 CTR 模式：计数器

C_i = P_i XOR E(Key, Nonce || Counter_i)
Counter: 0, 1, 2, 3, ...

不直接加密明文，而是加密计数器值，再和明文 XOR。把分组密码变成了流密码。

TIP

📌 CTR 的优点：

加密解密都能并行（每块独立）
可以随机访问（直接算第 N 块的密钥流）
不需要填充（密文长度 = 明文长度）

📌 CTR 的致命要求：Nonce 绝对不能重复！同一个 Key+Nonce 加密两条消息，XOR 两个密文就消掉了密钥流，直接得到两条明文的 XOR——信息完全泄露。

4.5 GCM 模式：认证加密

GCM = CTR 加密 + GMAC 认证。一步完成加密和完整性验证。

加密：CTR 模式加密
认证：对密文计算 GMAC（基于 GHASH）
输出：密文 + Tag（认证标签）

TIP

📌 为什么 GCM 是现代首选？它同时保证保密性和完整性——即使攻击者篡改了 1 个比特，Tag 验证也会失败。TLS 1.3 基本只用 AEAD 模式（GCM 或 ChaCha20-Poly1305）。

📌 GCM 的注意点：IV（Nonce）96 位时不能超过 2^32 次加密；认证 Tag 验证失败时绝不能泄露解密结果（Padding Oracle 攻击的教训）。

4.6 模式对比

模式	并行	填充	认证	推荐度
ECB	是	需要	否	禁止
CBC	加密不可	需要	否	旧系统
CTR	是	不需要	否	需配 MAC
GCM	是	不需要	是	首选
ChaCha20-Poly1305	是	不需要	是	首选

5 · RSA 非对称加密

$图 3 \xb7 RSA 与非对称加密$

5.1 非对称加密的核心思想

两把钥匙：公钥加密，私钥解密。公钥可以随便公开，私钥只有自己保管。

Alice 的公钥（公开）  →  任何人都能加密发给 Alice
Alice 的私钥（保密）  →  只有 Alice 能解密

TIP

📌 打个比方：非对称加密像信箱——

公钥 = 信箱的投信口，任何人都能往里塞信
私钥 = 信箱的钥匙，只有主人能开箱取信
你把投信口（公钥）告诉全世界，但钥匙（私钥）只有你有

📌 数学基础：非对称加密依赖"单向函数"——正向容易算，反向极难。RSA 依赖大整数分解：两个大素数相乘容易，但把乘积分解回两个素数极难。

5.2 RSA 的数学原理

密钥生成：

1. 选两个大素数 p, q（如各 1024 位）
2. n = p × q                    （模数，公开）
3. φ(n) = (p-1)(q-1)            （欧拉函数，保密）
4. 选 e：1 < e < φ(n)，gcd(e, φ(n)) = 1   （公钥指数，常选 65537）
5. 算 d：e × d ≡ 1 (mod φ(n))   （私钥指数，保密）

公钥 = (n, e)
私钥 = (n, d)

加密：C = M^e mod n 解密：M = C^d mod n

为什么能解密？根据欧拉定理：如果 gcd(M, n) = 1，则 M^(e×d) ≡ M (mod n)，所以 C^d = (M^e)^d = M^(e×d) ≡ M (mod n)。

TIP

📌 RSA 为什么安全？攻击者知道 n 和 e，要算 d 必须知道 φ(n) = (p-1)(q-1)，而算 φ(n) 必须分解 n = p × q。2048 位的 n，分解它用现有最好的算法和最快的超级计算机也需要数十亿年。

📌 RSA 为什么慢：要算大数的模幂运算（M^e mod n），涉及几百位的大数乘法。RSA 比 AES 慢约 1000 倍。所以实际使用中，RSA 只用来加密"AES 密钥"，数据本身用 AES 加密——这就是混合加密。

5.3 RSA 的填充：为什么不能裸加密

直接用 RSA 加密 M（即 C = M^e mod n）是不安全的：

确定性：相同的明文加密后得到相同的密文，攻击者能识别重复消息
代数攻击：E(M1) × E(M2) = E(M1 × M2)，可被利用做选择密文攻击
小指数攻击：e=3 且 M 很小时，M^e < n，直接开立方就能还原

解决方案：OAEP（Optimal Asymmetric Encryption Padding）填充：

OAEP(M) = M || padding  →  加入随机数 →  再 RSA 加密

TIP

📌 填充就像给信加随机空白页：每次加密前先往明文里混入随机数，这样同一条消息每次加密结果都不同。OAEP 是 RSA 加密的标准填充方案，TLS 1.3 中 RSA 只用于签名（不用 RSA 加密了）。

5.4 RSA 密钥长度

密钥长度	安全强度	等效对称强度	推荐场景
1024 位	~80 位	不安全	已淘汰
2048 位	~112 位	AES-128	最低标准
3072 位	~128 位	AES-128	推荐
4096 位	~152 位	AES-192	长期安全

TIP

📌 为什么 RSA 3072 才等效 AES-128？RSA 的安全强度不是线性增长的。1024 位 RSA 只有 80 位安全强度，要达到 128 位需要 3072 位。这是因为大数分解的亚指数算法（GNFS）比暴力破解更高效。

6 · 椭圆曲线加密 (ECC)

6.1 椭圆曲线是什么

椭圆曲线不是椭圆，而是一类形如 y² = x³ + ax + b 的曲线。密码学用的是有限域上的椭圆曲线（点坐标是整数，模一个大素数 p）。

椭圆曲线方程：y² = x³ + ax + b (mod p)

核心操作：点加
  P + Q = R  （过 P,Q 做直线，交曲线第三点，关于 x 轴对称）

标量乘法：
  k × P = P + P + ... + P  （k 次）

TIP

📌 ECC 的"单向"特性：已知 P 和 k，算 k × P 容易（类似快速幂）。但已知 P 和 k × P，反推 k 极难——这就是椭圆曲线离散对数问题 (ECDLP)。

📌 打个比方：想象你在地球表面走 k 步，每步走 1 米，方向固定。知道起点和步数，算终点容易。但知道起点和终点，反推走了多少步极难——因为地球表面是"弯曲的"，步数和距离不是简单的线性关系。椭圆曲线上的点加也有类似的"弯曲"特性。

6.2 ECC vs RSA

指标	RSA-2048	ECC-256	对比
安全强度	112 位	128 位	ECC 更强
密钥长度	2048 位	256 位	ECC 短 8 倍
签名速度	慢	快	ECC 快 3~5 倍
验证速度	快	中	RSA 验证略快
TLS 握手	大	小	ECC 节省带宽

TIP

📌 ECC 为什么密钥更短：RSA 依赖大数分解，有亚指数算法（GNFS），所以需要很大的数。ECC 依赖椭圆曲线离散对数，只有指数级算法（Pollard's rho），没有"捷径"，所以小密钥就能达到同等安全强度。

📌 ECC 的注意事项：曲线选择很重要。NIST 曲线（P-256 等）被怀疑有 NSA 后门。推荐使用 Curve25519（Daniel J. Bernstein 设计）或 SM2（中国国密）。

6.3 SM2：中国国密椭圆曲线

SM2 基于 256 位椭圆曲线，用于数字签名、密钥交换和公钥加密。国内金融、政务系统要求使用 SM2 替代 RSA。

7 · 密钥交换 (Diffie-Hellman)

$图 4 \xb7 密钥交换流程$

7.1 密钥分发问题

对称加密需要双方共享密钥，但如何在不安全的信道上安全地协商密钥？这就是密钥分发问题。

7.2 Diffie-Hellman 协议

1976 年，Diffie 和 Hellman 提出了革命性的方案——两人可以在公开信道上协商出共享密钥，即使窃听者听到了所有通信内容也无法算出密钥。

公开参数：大素数 p，生成元 g

Alice                          Bob
选秘密 a                        选秘密 b
A = g^a mod p                  B = g^b mod p
                               ←── B ──→
共享密钥 = B^a mod p           共享密钥 = A^b mod p
         = (g^b)^a mod p      = (g^a)^b mod p
         = g^(ab) mod p        = g^(ab) mod p  相同！

TIP

📌 为什么窃听者算不出来？窃听者知道 g, p, A=g^a, B=g^b，要算 g^(ab) 必须知道 a 或 b——这就是离散对数问题 (DLP)：已知 g^a mod p 反推 a，在 p 足够大时极难。

📌 打个比方：Alice 用一种只有她知道的颜料混合法，Bob 也用他的。两人交换混合后的颜料，再各自加入自己的秘密颜料——最终两人得到相同的颜色，但旁观者看到了交换的混合颜料，却无法分离出原始的秘密颜料。

7.3 ECDH：椭圆曲线版 DH

把 DH 中的模幂运算换成椭圆曲线标量乘法：

Alice: 私钥 a，公钥 A = a × G
Bob:   私钥 b，公钥 B = b × G
共享密钥 = a × B = a × (b × G) = b × (a × G) = b × A

ECDH 比 DH 更快、密钥更短，是 TLS 1.3 的默认密钥交换方式。

7.4 前向安全 (Forward Secrecy)

TIP

📌 什么是前向安全？即使长期私钥泄露，之前录制的加密通信也无法被解密。因为每次连接用的临时密钥（Ephemeral Key）用完即丢，不在任何地方保存。

📌 为什么重要？攻击者可能录下了你过去所有的 TLS 流量，暂时解不了但存着。如果你的私钥某天泄露，如果没有前向安全，攻击者可以用私钥解出所有历史会话的对称密钥，从而解密所有历史流量。有前向安全（ECDHE），即使私钥泄露，历史流量仍然安全——因为临时密钥已经销毁。

📌 TLS 1.3 强制前向安全：只支持 ECDHE/DHE 密钥交换，不再支持静态 RSA 密钥交换。这是 TLS 1.3 的重大安全改进。

8 · 哈希函数

8.1 什么是哈希函数

哈希函数把任意长度的输入压缩成固定长度的"指纹"：

输入（任意长度）→  哈希函数 H()  →  输出（固定长度）
"Hello"           →  SHA-256     →  185f8db3...（64 个十六进制字符 = 256 位）

三个核心性质：

性质	含义	用途
抗原像	给定 H(x)，难以反推 x	密码存储
抗第二原像	给定 x，难以找到 y≠x 使 H(y)=H(x)	文件完整性
抗碰撞	难以找到任意 x,y 使 H(x)=H(y)	数字签名

TIP

📌 哈希不是加密！加密是可逆的（有密钥能解密），哈希是不可逆的（没有"反哈希"操作）。哈希像搅拌机——把食材打成汁后，你无法从果汁还原出原始食材。

📌 "难以"不等于"不可能"：碰撞一定存在（鸽笼原理：无限输入映射到有限输出）。抗碰撞的意思是"找到碰撞的计算代价极高"，而不是"不存在碰撞"。

8.2 常见哈希函数

算法	输出长度	安全性	状态
MD5	128 位	2^18 次运算可碰撞	已破解
SHA-1	160 位	2^63 次运算可碰撞	已破解
SHA-256	256 位	安全	推荐
SHA-512	512 位	安全	推荐
SHA-3	224~512 位	安全（不同结构）	备选
SM3	256 位	安全（中国国密）	国内推荐
BLAKE3	任意	安全+极快	新星

TIP

📌 MD5 怎么被破解的？2004 年王小云团队找到了 MD5 的快速碰撞方法——几分钟内就能找到两个不同输入产生相同的 MD5。2010 年，黑客用 MD5 碰撞伪造了 CA 证书，直接导致 MD5 在安全领域被判死刑。

📌 SHA-1 的谢幕：2017 年 Google 发表 SHAttered 攻击，用 110 块 GPU 跑了 6500 CPU 年，找到了 SHA-1 碰撞。Git 在 2020 年开始迁移到 SHA-256。

8.3 密码存储：为什么不能存明文

错误：数据库存明文密码 → 数据库泄露 = 所有密码泄露

正确：数据库存哈希值
  注册：password → SHA-256(password) → 存入数据库
  登录：input → SHA-256(input) → 和数据库比对

TIP

📌 只哈希还不够：攻击者拿到哈希值后可以用"彩虹表"（预计算的哈希对照表）反查常见密码。解决方案是加盐 (Salt)：

存储 = SHA-256(salt + password)
每次注册生成随机 salt（如 16 字节）
salt 和哈希一起存数据库

加了盐后，即使两个用户密码相同，哈希值也不同，彩虹表失效。

📌 更推荐：慢哈希：bcrypt / scrypt / Argon2 专门为密码存储设计——故意很慢（可调），让暴力破解代价极高。bcrypt 调一次约 100ms，暴力试 100 万个密码需要 27 小时；SHA-256 调一次约 1μs，同样只需 1 秒。

8.4 HMAC：带密钥的哈希

普通哈希任何人都能算，无法验证身份。HMAC 用密钥来认证：

HMAC(Key, Message) = H((Key XOR opad) || H((Key XOR ipad) || Message))

接收方知道 Key，能重新计算 HMAC 并比对。不知道 Key 的人无法伪造。

TIP

📌 HMAC 和 MAC 的区别：MAC（消息认证码）是概念，HMAC 是用哈希函数实现 MAC 的具体方案。HMAC 可以用任何哈希函数：HMAC-SHA256、HMAC-SM3 等。

9 · 消息认证码 (MAC)

9.1 MAC 解决什么问题

加密只保证保密性，不保证完整性——攻击者可以篡改密文，接收方解密后得到错误数据但不知道被篡改了。MAC 提供完整性+认证。

发送方：
  Tag = MAC(Key, Message)
  发送：Message || Tag

接收方：
  收到：Message' || Tag'
  计算：Tag'' = MAC(Key, Message')
  验证：Tag'' == Tag' ?  → 通过则未被篡改

9.2 AEAD：一步搞定加密+认证

现代密码学推荐 AEAD（Authenticated Encryption with Associated Data）——一步完成加密和认证：

AEAD(Key, Nonce, Plaintext, AAD) → Ciphertext + Tag

验证 Tag 通过 → 解密
验证 Tag 失败 → 拒绝（不输出任何明文）

TIP

📌 为什么先验证再解密很重要：Padding Oracle 攻击（如 POODLE、Lucky 13）就是利用了"先解密再验证"的设计缺陷——攻击者通过观察验证失败的错误信息，逐字节猜出明文。AEAD 强制"先验证 Tag，通过才解密"，从根本上杜绝了这类攻击。

10 · 数字签名

$图 5 \xb7 数字签名流程$

10.1 签名 vs MAC

	MAC	数字签名
密钥	对称（共享）	非对称（私钥签，公钥验）
谁能验证	持共享密钥者	任何人（公钥公开）
不可否认	否（双方都能签）	是（只有私钥持有者能签）
速度	快	慢

10.2 RSA 签名

签名：S = H(M)^d mod n    （用私钥 d 对哈希值做 RSA 解密运算）
验证：H(M) == S^e mod n   （用公钥 e 对签名做 RSA 加密运算，比对哈希）

TIP

📌 为什么签哈希而不是签原文？

效率：RSA 很慢，签 1MB 原文要很久，签 32 字节哈希瞬间完成
安全：直接签原文有各种代数攻击的可能

📌 签名的"不可否认"怎么来的？因为只有私钥持有者能生成正确签名。第三方仲裁时，用公钥验证签名通过，就能证明"这条消息确实由私钥持有者发出"——和手写签名的法律效力类似。

10.3 ECDSA 签名

椭圆曲线数字签名算法，是 TLS 证书中最常用的签名方案。

签名 (消息 M, 私钥 d)：
  1. 选随机 k
  2. (x, y) = k × G
  3. r = x mod n
  4. s = k^(-1) × (H(M) + d × r) mod n
  5. 签名 = (r, s)

验证 (消息 M, 签名 (r,s), 公钥 Q)：
  1. w = s^(-1) mod n
  2. u1 = H(M) × w mod n
  3. u2 = r × w mod n
  4. (x, y) = u1 × G + u2 × Q
  5. 验证 x mod n == r

TIP

📌 ECDSA 的 k 致命要求：随机数 k 绝对不能重复或可预测！如果两次签名用了相同的 k，攻击者可以通过两个签名算出私钥 d。2010 年索尼 PS3 的 ECDSA 私钥就是因为 k 固定而被破解。现代实现用 RFC 6979（确定性 k）避免这个问题。

10.4 EdDSA 签名

Ed25519 是现代推荐的签名方案（Daniel J. Bernstein 设计）：

确定性签名（不需要随机数，避免 k 重用问题）
高速签名和验证
抗侧信道攻击（不依赖分支条件）

TIP

📌 Ed25519 vs ECDSA：Ed25519 更快、更安全、更简单。SSH 从 8.0 开始默认使用 Ed25519 密钥。Git 也开始支持 Ed25519 签名。

11 · PKI 与证书

11.1 公钥信任问题

非对称加密解决了密钥分发问题，但引入了新问题：你怎么知道这个公钥真的是 Alice 的？ 攻击者可以伪造公钥冒充 Alice。

11.2 PKI：证书授权体系

PKI（Public Key Infrastructure）通过 CA（Certificate Authority）来解决信任问题：

1. Alice 生成密钥对（公钥+私钥）
2. Alice 向 CA 申请证书（提交公钥+身份信息）
3. CA 验证 Alice 的身份
4. CA 用自己的私钥对 Alice 的公钥+身份信息签名
5. 生成证书 = Alice 的公钥 + 身份信息 + CA 的签名

验证证书：
  1. 用 CA 的公钥验证证书签名
  2. 签名有效 → 证书中的公钥可信
  3. 检查证书有效期、域名匹配等

TIP

📌 打个比方：PKI 像身份证系统——

CA = 公安局（可信权威）
证书 = 身份证（公安局签发，包含你的照片和身份信息）
CA 签名 = 身份证上的防伪标记（只有公安局能制作）
验证 = 检查身份证防伪标记（用公安局的公开验证方法）

📌 信任链：根 CA → 中间 CA → 终端证书。根 CA 证书预装在操作系统/浏览器中（自签名），中间 CA 由根 CA 签名，终端证书由中间 CA 签名。验证时逐级向上验证签名，直到根 CA。

11.3 证书格式

X.509 证书内容：
  版本号
  序列号
  签名算法
  颁发者 (Issuer)
  有效期 (Not Before / Not After)
  主体 (Subject) — 域名/组织名
  公钥 (Public Key)
  扩展字段 — SAN (Subject Alternative Name) 等
  CA 签名 (Signature)

11.4 证书类型

类型	验证级别	适用场景
DV (Domain Validation)	仅验证域名所有权	个人网站
OV (Organization Validation)	验证域名+组织信息	企业网站
EV (Extended Validation)	严格验证+地址栏显示组织名	金融/电商

TIP

📌 Let's Encrypt 的革命：2015 年 Let's Encrypt 提供免费 DV 证书，自动化签发，把 HTTPS 从"花钱买证书"变成"一键免费"。目前互联网上超过 80% 的 HTTPS 证书来自 Let's Encrypt。

12 · TLS/SSL 握手

12.1 TLS 是什么

TLS（Transport Layer Security）是 HTTPS 的安全基础，在 TCP 之上提供加密、认证和完整性。SSL 是 TLS 的前身（SSL 3.0 → TLS 1.0），现在已完全淘汰。

12.2 TLS 1.2 握手流程

Client                              Server
  │ ── ClientHello ──────────────→ │
  │    （支持的密码套件、随机数）      │
  │                                │
  │ ←── ServerHello ────────────── │
  │    （选定的密码套件、随机数）      │
  │ ←── Certificate ────────────── │
  │    （服务器证书）                 │
  │ ←── ServerKeyExchange ───────── │
  │    （ECDHE 公开参数）            │
  │ ←── ServerHelloDone ─────────── │
  │                                │
  │ ── ClientKeyExchange ────────→ │
  │    （ECDHE 公开参数）            │
  │                                │
  │    双方计算共享密钥               │
  │                                │
  │ ── ChangeCipherSpec ─────────→ │
  │ ── Finished (加密) ──────────→ │
  │ ←── ChangeCipherSpec ───────── │
  │ ←── Finished (加密) ─────────── │
  │                                │
  │ ←═══ 加密通信开始 ═══════════→ │

12.3 TLS 1.3 的改进

Client                              Server
  │ ── ClientHello ──────────────→ │
  │    （密码套件+DH 公开参数+      │
  │     0-RTT 数据）                │
  │                                │
  │ ←── ServerHello ────────────── │
  │    （密码套件+DH 公开参数）      │
  │ ←── Finished (加密) ─────────── │
  │                                │
  │ ── Finished (加密) ──────────→ │
  │                                │
  │ ←═══ 加密通信开始 ═══════════→ │

TIP

📌 TLS 1.3 的关键改进：

1-RTT 握手（TLS 1.2 需要 2-RTT），0-RTT 恢复模式甚至 0 延迟
强制前向安全：只用 ECDHE，不再支持 RSA 密钥交换
删掉不安全的算法：RC4、DES、MD5、SHA-1、静态 DH 全部移除
加密更多握手：ServerHello 之后立即加密，证书不再明文传输
简化密码套件：从 300+ 种缩减到 5 种

📌 0-RTT 的代价：0-RTT 数据是重放安全的隐患——攻击者可以录制并重放 0-RTT 数据。所以 0-RTT 只能用于幂等请求（如 GET），不能用于会改变状态的请求（如 POST 转账）。

13 · 密码学实战

13.1 OpenSSL 常用命令

# 生成 RSA 密钥对
openssl genrsa -out private.pem 2048
openssl rsa -in private.pem -pubout -out public.pem

# 用 RSA 加密（实际应使用 OAEP 填充）
openssl rsautl -encrypt -pubin -inkey public.pem -in msg.txt -out msg.enc
openssl rsautl -decrypt -inkey private.pem -in msg.enc -out msg.dec

# 用 AES-256-GCM 加密
openssl enc -aes-256-gcm -in file.txt -out file.enc -pass pass:password

# 计算哈希
echo -n "Hello" | openssl dgst -sha256
echo -n "Hello" | openssl dgst -sm3

# 生成自签名证书
openssl req -x509 -newkey rsa:2048 -keyout key.pem -out cert.pem -days 365 -nodes

# 查看证书
openssl x509 -in cert.pem -text -noout

# 生成 ECDSA 密钥（P-256）
openssl ecparam -name prime256v1 -genkey -noout -out ecdsa.pem

# 生成 Ed25519 密钥
openssl genpkey -algorithm ed25519 -out ed25519.pem

13.2 密码学选择速查

需求	推荐方案	不推荐
对称加密	AES-256-GCM / ChaCha20-Poly1305	DES, 3DES, RC4, AES-ECB
非对称加密	RSA-3072+OAEP / ECDH	RSA-1024, 裸 RSA
数字签名	Ed25519 / ECDSA P-256 / RSA-3072-PSS	RSA-1024, DSA
哈希	SHA-256 / SHA-3 / BLAKE3	MD5, SHA-1
密码存储	Argon2id / bcrypt / scrypt	MD5, SHA-256（太快）
HMAC	HMAC-SHA256 / HMAC-SM3	HMAC-MD5, HMAC-SHA1
密钥交换	X25519 (ECDH)	RSA 密钥交换, DH-1024
TLS	TLS 1.3	SSL 3.0, TLS 1.0/1.1

13.3 常见错误

TIP

📌 新手最常犯的密码学错误：

用 MD5 存密码 → 用 Argon2id 或 bcrypt
用 AES-ECB 模式 → 用 AES-GCM 或 ChaCha20-Poly1305
Nonce/IV 重复 → 每次加密必须用新的随机 Nonce
自己实现加密算法 → 永远用成熟的库（OpenSSL, libsodium, Tink）
密钥硬编码在代码里 → 用 KMS / 环境变量 / 密钥管理服务
用 RSA 加密大文件 → 用 RSA 加密 AES 密钥，AES 加密文件
先解密后验证 → 用 AEAD，先验证 Tag 再解密
随机数用 rand() → 用密码学安全随机数（/dev/urandom, CSPRNG） :::

14 · 后量子密码

14.1 量子计算机的威胁

量子计算机利用量子叠加和纠缠，能在某些问题上远超经典计算机：

量子算法	威胁的对象	影响
Shor 算法	RSA, ECC, DH	多项式时间破解（致命）
Grover 算法	AES, SHA	密钥空间减半（AES-256 → AES-128）

:::tip 📌 Shor 算法为什么能破 RSA：Shor 算法能在多项式时间内分解大整数和求离散对数——RSA 和 ECC 的安全基础直接失效。2048 位 RSA 在量子计算机面前等效于 0 位。

📌 Grover 算法不是致命的：Grover 只是把暴力搜索从 O(N) 加速到 O(√N)，相当于密钥空间开方。AES-256 变成 128 位安全强度，仍然安全。所以对称加密和哈希受量子威胁较小，非对称加密受威胁极大。

14.2 后量子密码算法 (PQC)

NIST 在 2016 年开始征集后量子密码标准，2024 年公布最终标准：

算法	类型	用途	状态
ML-KEM (Kyber)	格基	密钥封装 (KEM)	标准化
ML-DSA (Dilithium)	格基	数字签名	标准化
SLH-DSA (SPHINCS+)	哈希	数字签名	标准化
FN-DSA (Falcon)	格基	数字签名	标准化

TIP

📌 格基密码为什么是主流：格问题（如 LWE、SVP）被认为即使量子计算机也难以解决。而且格基运算速度快、密钥尺寸适中。Kyber 和 Dilithium 都基于格问题。

📌 现在该做什么？美国 NSA 要求 2033 年前完成 PQC 迁移。Google Chrome 已在部分连接中测试 X25519Kyber768 混合密钥交换。现在应该：了解 PQC、评估现有系统的量子风险、规划迁移路线。

15 · 同态加密与零知识证明

15.1 同态加密 (Homomorphic Encryption)

同态加密允许在密文上直接计算，解密后得到对明文计算的结果：

加密：E(3) = C1, E(5) = C2
密文计算：C3 = C1 + C2
解密：D(C3) = 8  ← 等于 3+5，但计算过程中服务器从未看到明文！

类型	支持运算	代表方案
半同态 (HE)	仅加法或仅乘法	Paillier（加法）
些许同态 (SHE)	有限次加法+乘法	BGV, BFV
全同态 (FHE)	任意次数加法+乘法	Gentry, CKKS

TIP

📌 全同态加密的意义：你可以把加密数据发给云服务器，服务器在密文上做计算（如机器学习推理），返回加密结果——服务器全程不知道你的数据内容。这对医疗、金融等隐私敏感场景意义重大。

📌 为什么 FHE 还没普及：太慢了。FHE 的计算开销比明文计算慢 10^6 倍以上。虽然每年在改善，但距离实用还有距离。目前半同态（如 Paillier）已有实际应用。

15.2 零知识证明 (Zero-Knowledge Proof)

零知识证明让你证明你知道某个秘密，但不泄露秘密本身：

证明者 (Prover)              验证者 (Verifier)
  知道秘密 S                   不知道 S
  │                            │
  │  证明："我知道 S"            │
  │  （但不透露 S 的任何信息）     │
  │ ──────────────────────────→ │
  │                            │
  │  验证通过 → 接受证明          │
  │  但 Verifier 仍不知道 S      │

:::tip 📌 经典比喻——阿里巴巴山洞：山洞有一个入口和两条岔路（A 和 B），尽头有魔法门连接两条路，开门需要密码。证明者知道密码，要向验证者证明但不泄露密码：

验证者在洞外，看不到证明者走哪条路
证明者进入山洞，随机选 A 或 B
验证者进洞，喊"从 B 出来！"
如果证明者之前走的是 A，必须用密码开门到 B
如果之前走的是 B，直接出来即可
重复 40 次：每次都正确出来 → 概率上几乎确定证明者知道密码
但验证者每次只看到"从指定路出来"，学不到任何密码信息

📌 现代应用：

zk-SNARK：Zcash 隐私交易（证明你有足够余额但不暴露金额）
zk-Rollup：以太坊 Layer 2 扩容（链下计算+链上验证）
身份验证：证明你满 18 岁但不暴露具体年龄 :::

15.3 密码学前沿趋势

方向	核心价值	成熟度
后量子密码 (PQC)	抗量子计算机	标准化中
全同态加密 (FHE)	密文上直接计算	研究阶段
零知识证明 (ZKP)	证明不泄露	部分落地
多方安全计算 (MPC)	多方协作不泄露各自输入	部分落地
可搜索加密	加密数据可搜索	研究阶段

附录 A · 术语速查表

术语	英文	含义
明文	Plaintext	未加密的原始数据
密文	Ciphertext	加密后的数据
密钥	Key	控制加密/解密的秘密参数
加密	Encryption	明文→密文
解密	Decryption	密文→明文
哈希	Hash	任意长度→固定长度的单向映射
碰撞	Collision	两个不同输入产生相同哈希
盐	Salt	防彩虹表的随机值
IV	Initialization Vector	初始化向量，每次加密的随机值
Nonce	Number used once	只用一次的随机数
MAC	Message Authentication Code	消息认证码
AEAD	Authenticated Encryption with Associated Data	认证加密
PKI	Public Key Infrastructure	公钥基础设施
CA	Certificate Authority	证书授权机构
CRL	Certificate Revocation List	证书吊销列表
OCSP	Online Certificate Status Protocol	在线证书状态协议
KDF	Key Derivation Function	密钥派生函数
HSM	Hardware Security Module	硬件安全模块
CSPRNG	Cryptographically Secure PRNG	密码学安全随机数生成器
PQC	Post-Quantum Cryptography	后量子密码
FHE	Fully Homomorphic Encryption	全同态加密
ZKP	Zero-Knowledge Proof	零知识证明

附录 B · 密码学工具命令速查

OpenSSL

# 对称加密
openssl enc -aes-256-gcm -in file -out file.enc -pass pass:pwd
openssl enc -d -aes-256-gcm -in file.enc -out file.dec -pass pass:pwd

# 哈希
openssl dgst -sha256 file
openssl dgst -sm3 file

# HMAC
openssl dgst -sha256 -hmac "secretkey" file

# RSA 密钥
openssl genrsa -out priv.pem 3072
openssl rsa -in priv.pem -pubout -out pub.pem

# RSA 签名
openssl dgst -sha256 -sign priv.pem -out sig.bin file
openssl dgst -sha256 -verify pub.pem -signature sig.bin file

# 证书
openssl req -x509 -newkey rsa:3072 -keyout key.pem -out cert.pem -days 365 -nodes
openssl x509 -in cert.pem -text -noout

# ECDSA
openssl ecparam -name prime256v1 -genkey -noout -out ec.pem
openssl ec -in ec.pem -pubout -out ec_pub.pem

# Ed25519
openssl genpkey -algorithm ed25519 -out ed.pem
openssl pkey -in ed.pem -pubout -out ed_pub.pem

GnuPG

# 生成密钥
gpg --full-generate-key

# 加密
gpg -e -r alice@example.com file

# 解密
gpg -d file.gpg > file

# 签名
gpg --sign file

# 验证签名
gpg --verify file.sig

Python (cryptography 库)

from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os

# AES-256-GCM
key = AESGCM.generate_key(bit_length=256)
aesgcm = AESGCM(key)
nonce = os.urandom(12)  # 96-bit nonce
ciphertext = aesgcm.encrypt(nonce, b"Hello World", None)
plaintext = aesgcm.decrypt(nonce, ciphertext, None)

ssh-keygen

# 生成 Ed25519 密钥（推荐）
ssh-keygen -t ed25519 -C "alice@example.com"

# 生成 RSA 密钥
ssh-keygen -t rsa -b 3072 -C "alice@example.com"

附录 C · 自测题

基础题

Q1：Base64 是加密吗？为什么？

不是。Base64 是编码，没有密钥，任何人都能解码。它的目的是格式转换（让二进制数据能穿过文本通道），不是保密。

Q2：为什么说 MD5 不安全？具体是什么攻击？

2004 年王小云团队发现了 MD5 的快速碰撞方法——在几分钟内找到两个不同输入产生相同的 MD5 值。抗碰撞被打破，意味着攻击者可以伪造签名和证书。

Q3：对称加密和非对称加密的最大区别是什么？

对称加密用同一把密钥加解密，速度快但密钥分发困难。非对称加密用公钥加密、私钥解密，解决了密钥分发问题但速度慢约 1000 倍。

Q4：为什么 AES-ECB 模式不安全？

ECB 模式下相同的明文块产生相同的密文块，泄露了明文的模式信息。加密图片仍能看出原图轮廓（ECB 企鹅图）。

进阶题

Q5：什么是前向安全？为什么 TLS 1.3 强制要求它？

前向安全指即使长期私钥泄露，历史通信也无法被解密。因为每次连接用临时密钥（ECDHE），用完即丢。TLS 1.3 强制 ECDHE，不再支持 RSA 密钥交换，确保即使私钥泄露，录制的历史流量仍然安全。

Q6：为什么 RSA-3072 才等效 AES-128 的安全强度？

RSA 依赖大数分解，有亚指数算法（GNFS），所以安全强度不是线性增长。1024 位 RSA 只有 80 位安全强度，3072 位才达到 128 位。AES 依赖暴力破解（指数级），128 位就是 128 位安全强度。

Q7：Diffie-Hellman 密钥交换为什么安全？窃听者听到了什么？为什么算不出密钥？

窃听者知道公开参数 p, g, A=g^a mod p, B=g^b mod p，要算共享密钥 g^(ab) mod p 必须知道 a 或 b——这是离散对数问题（DLP），在 p 足够大时计算不可行。

Q8：为什么密码存储用 bcrypt 而不是 SHA-256？

SHA-256 太快（~1μs），攻击者每秒可以试 100 万个密码。bcrypt 故意很慢（~100ms），且可调成本因子。同样试 100 万个密码，SHA-256 需要 1 秒，bcrypt 需要 27 小时。

思考题

Q9：如果量子计算机成熟了，哪些密码算法需要换？哪些可以继续用？

需要换：RSA、ECC、DH（Shor 算法多项式时间破解）。可以继续用：AES（Grover 算法只减半安全强度，AES-256 → 128 位仍安全）、SHA-256（同上）。需要升级：对称加密密钥长度翻倍即可。

Q10：你收到一封邮件，数字签名验证通过。你能确定什么？不能确定什么？

能确定：邮件内容未被篡改（完整性）、邮件确实由私钥持有者发出（认证+不可否认）。不能确定：私钥持有者本人是否自愿发送（可能被胁迫）、私钥是否被盗用（需要结合时间戳和撤销检查）、邮件是否在传输中被延迟或重放。

本页目录

密码学入门#

怎么用这份笔记#

1 · 密码学全景#

1.1 密码学解决什么问题#

1.2 密码学的三大分支#

1.3 Kerckhoffs 原则#

2 · 古典密码#

2.1 凯撒密码：最简单的替换密码#

2.2 维吉尼亚密码：多表替换#

2.3 一次性密码本（OTP）：理论最安全#

2.4 古典密码的教训#

3 · 对称加密#

3.1 什么是对称加密#

3.2 DES：曾经的王者#

3.3 AES：现代对称加密之王#

3.4 SM4：中国国密算法#

3.5 流密码：ChaCha20#

4 · 分组密码模式#

4.1 为什么需要"模式"#

4.2 ECB 模式：最简单但最危险#

4.3 CBC 模式：链式拼接#

4.4 CTR 模式：计数器#

4.5 GCM 模式：认证加密#

4.6 模式对比#

5 · RSA 非对称加密#

5.1 非对称加密的核心思想#

5.2 RSA 的数学原理#

5.3 RSA 的填充：为什么不能裸加密#

5.4 RSA 密钥长度#

6 · 椭圆曲线加密 (ECC)#

6.1 椭圆曲线是什么#

6.2 ECC vs RSA#

6.3 SM2：中国国密椭圆曲线#

7 · 密钥交换 (Diffie-Hellman)#

7.1 密钥分发问题#

7.2 Diffie-Hellman 协议#

7.3 ECDH：椭圆曲线版 DH#

7.4 前向安全 (Forward Secrecy)#

8 · 哈希函数#

8.1 什么是哈希函数#

8.2 常见哈希函数#

8.3 密码存储：为什么不能存明文#

8.4 HMAC：带密钥的哈希#

9 · 消息认证码 (MAC)#

9.1 MAC 解决什么问题#

9.2 AEAD：一步搞定加密+认证#

10 · 数字签名#

10.1 签名 vs MAC#

10.2 RSA 签名#

10.3 ECDSA 签名#

10.4 EdDSA 签名#

11 · PKI 与证书#

11.1 公钥信任问题#

11.2 PKI：证书授权体系#

11.3 证书格式#

11.4 证书类型#

12 · TLS/SSL 握手#

12.1 TLS 是什么#

12.2 TLS 1.2 握手流程#

12.3 TLS 1.3 的改进#

13 · 密码学实战#

13.1 OpenSSL 常用命令#

13.2 密码学选择速查#

13.3 常见错误#

14 · 后量子密码#

14.1 量子计算机的威胁#

14.2 后量子密码算法 (PQC)#

15 · 同态加密与零知识证明#

15.1 同态加密 (Homomorphic Encryption)#

15.2 零知识证明 (Zero-Knowledge Proof)#

15.3 密码学前沿趋势#

附录 A · 术语速查表#

附录 B · 密码学工具命令速查#

OpenSSL#

GnuPG#

Python (cryptography 库)#

ssh-keygen#

附录 C · 自测题#

基础题#

进阶题#