Course Overview

这份笔记假设你已经忘了前面各讲的内容，从头把整条路线重新走一遍。它随课程持续更新：每学完一讲，就在“回头看”之前补上对应的几节（目前到 Lecture 9）。每一节都按同样的顺序：遇到了什么问题 → 想到什么办法 → 具体怎么做（配小例子）→ 为什么管用 → 在哪里失效 → 于是引出下一节。新名词都先用白话解释，讲清楚之后才给出正式名称和缩写。

最后一部分“回头看”才把所有东西放进一张总图。每节末尾的一句话可以用来快速复习；想看细节，点每节开头的讲次链接。

1. 问题：在别人眼皮底下说悄悄话

对应 Lecture 1

Alice 想给 Bob 发一条消息，但消息要经过公共网络，偷听者 Eve 能看到传输的所有内容。Alice 和 Bob 事先见过面，约定了一个只有他们俩知道的秘密，叫做密钥（key）。

sequenceDiagram
    participant Alice as Alice（有密钥 k）
    participant Eve as Eve（偷听者）
    participant Bob as Bob（有密钥 k）
    Note over Alice: 用 k 把消息变成乱码
    Alice->>Bob: 乱码（Eve 也能看到）
    Note over Eve: 只看到乱码，没有 k
    Note over Bob: 用 k 把乱码变回消息

几个基本词：

词	白话
明文 $m$	原本要说的话
密文 $c$	变成乱码之后、在网上传输的东西
加密 ${\mathsf{Enc}}_k(m)$	用密钥 $k$ 把明文变成密文
解密 ${\mathsf{Dec}}_k(c)$	用密钥 $k$ 把密文变回明文
密钥生成 $\mathsf{Gen}$	事先随机挑一把密钥

这三个步骤合在一起叫一个加密方案，写成 $\Pi =(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$。基本要求是 Bob 一定能解对：${\mathsf{Dec}}_k({\mathsf{Enc}}_k(m))=m$。

还有一条重要约定（Kerckhoffs 原则）：假设 Eve 知道加密的方法，只是不知道密钥。原因是方法一旦写进软件就很难保密，而密钥泄露了换一把即可。所以安全只能靠密钥。

一句话：Alice 和 Bob 共享密钥，Eve 知道算法但不知道密钥。

2. 古典密码：看起来很乱，并不安全

对应 Lecture 1

早期的密码都靠直觉设计，例如：

• 移位密码：每个字母往后移 $k$ 位。$k=3$ 时，hello 变成 khoor。漏洞：$k$ 只有 26 种可能，Eve 全部试一遍，看哪个读得通即可。
• 替换密码：把 26 个字母打乱成一张对照表，可能的表有 $26!$ 种，没法逐个尝试。漏洞：英文中 e 最常见，密文中出现最多的字母大概就是 e，这叫频率分析。
• 维吉尼亚密码：用一个单词当密钥，不同位置移不同的位数。漏洞：猜出密钥长度后，每隔固定位置的字母仍是一个移位密码，照样能做频率分析。

这些方案都经历了“设计 → 被破 → 修补 → 再被破”的循环。问题出在没人说清楚“安全”到底指什么，只能凭感觉判断。

一句话：“看起来很乱”不等于安全，必须先给“安全”一个精确的定义。

3. 什么叫“安全”：猜硬币游戏

对应 Lecture 2

现代密码学先回答三个问题：

1. 定义：攻击者能做什么？怎样算攻击成功？
2. 假设：安全依赖哪些暂时无法证明、但大家相信的前提？
3. 证明：为什么在这些假设下，方案满足定义？

先看定义。“Eve 算不出密钥”不够：如果加密什么都不做，直接输出明文，Eve 确实算不出密钥，但消息已经全部泄露。“Eve 算不出整条明文”也不够：只泄露工资的前几位，也已经造成伤害。

合理的要求是：看到密文之后，Eve 对明文的了解没有任何增加。 比如 Eve 原本认为“Alice 说的是 yes”的可能性是 70%，看到密文后，这个判断应该仍是 70%。这叫完美保密（perfect secrecy）。

这个要求可以改写成一个更好用的游戏：

1. Eve 挑两条等长的消息，比如 yes 和 no!，交给考官。
2. 考官暗中抛一枚硬币 $b$：正面加密第一条，反面加密第二条，然后只把密文交给 Eve。
3. Eve 猜考官抛的是哪一面。

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有密钥 k）
    Eve->>Judge: 两条等长消息 m₀, m₁
    Note over Judge: 暗中抛硬币 b，加密 m_b
    Judge-->>Eve: 密文 c
    Note over Eve: 只能盯着 c 看
    Eve->>Judge: 猜 b

瞎猜也有 50% 的机会，所以安全 = Eve 猜对的概率不超过 50%。

• 让 Eve 自己挑消息，是为了考虑最坏情况：连她挑出的最好区分的两条都分不清，其他信息自然更得不到。
• 要求两条消息等长，是因为密文通常会暴露长度，我们只要求保护长度以外的内容。

这个游戏在后面会反复出现。之后每加强一次攻击者，就是给游戏里的 Eve 多开一项权限。

一句话：安全就是“Eve 猜不出考官加密的是哪一条”，猜对概率不能超过 50%。

4. 一次一密：完美安全，但代价太大

对应 Lecture 3

4.1 先认识异或

后面几乎每个方案都用到异或（XOR），记作 $\oplus$。它按位计算：两位相同得 0，不同得 1。

$x$	$y$	$x\oplus y$
0	0	0
0	1	1
1	0	1
1	1	0

可以把它想成一排开关：和 1 异或就翻转这一位，和 0 异或就不变。两条最重要的性质：

$$x\oplus k\oplus k=x,x\oplus x=0.$$

即用同一个 $k$ 异或两次就还原了。

4.2 做法

密钥是一串和消息一样长的随机比特，加密和解密都是与密钥异或：

$$c=m\oplus k,m=c\oplus k.$$

例：明文 $m=1010$，密钥 $k=0110$，密文 $c=1100$。Bob 计算 $1100\oplus 0110=1010$，还原明文。

这个方案叫一次一密（One-Time Pad，OTP）。

4.3 为什么完美安全

Eve 看到 $c=1100$。它可能是任何一条 4 位明文：若明文是 $0000$，密钥就是 $1100$；若明文是 $1111$，密钥就是 $0011$。每条明文都恰好对应一把密钥，而每把密钥被选中的概率都是 $1/16$。因此密文对哪条明文都不偏向，Eve 什么也学不到。

4.4 两个代价

代价一：密钥只能用一次。 若两条消息用同一把密钥，

$$c_1\oplus c_2=(m_1\oplus k)\oplus (m_2\oplus k)=m_1\oplus m_2.$$

密钥被消掉，Eve 直接得到两条明文的异或。例：$m_1=1010$、$m_2=0011$，$k=0110$，则 $c_1=1100$、$c_2=0101$，$c_1\oplus c_2=1001=m_1\oplus m_2$。若 Eve 知道其中一条明文，另一条就完全暴露。

代价二：密钥必须和消息一样长。 而且这不是 OTP 设计得不好，而是完美保密本身的要求：

定理：完美保密的密钥下界

任何完美保密的方案，可能的密钥数至少和可能的消息数一样多。

直观理解：固定 Eve 看到的密文，每把密钥最多把它解释成一条明文。若密钥比消息少，总有些消息无法解释这个密文，Eve 就能把它们排除，这已经是泄露。

一句话：一次一密用“等长随机密钥异或”做到完美安全，但密钥太长、只能用一次，这是完美保密的必然代价。

5. 退一步：只要“实际上破不了”

对应 Lecture 4

5.1 放宽要求

要用短密钥，就必须放宽完美保密。现实中的 Eve 是一台计算机，时间有限，所以改成两条较弱的要求：

1. 只防跑得动的 Eve。 设密钥长 $n$ 位（叫安全参数）。“跑得动”指运行时间像 $n^2$、$n^3$ 这样随 $n$ 增长。$n=128$ 时，$n^3$ 约两百万步，很快；而穷举密钥要 $2^{128}$ 步，永远跑不完。正式名称是概率多项式时间（PPT），“概率”指程序可以掷硬币。
2. 允许极小的优势。 Eve 猜对的概率可以是 $50\%+\epsilon$，只要 $\epsilon$ 小到可以忽略，比如 $2^{-n}$（$n=128$ 时约 $3\times 10^{-39}$）。正式要求是：即使重复尝试多项式次，加起来仍然很小。这叫可忽略函数（negligible）。反例：$1/n^{100}$ 虽然也趋于 0，但不算可忽略。

新的安全要求：

$$\text{任何跑得动的 Eve，猜对硬币的概率}\le \frac{1}{2}+\text{可忽略量}.$$

5.2 新工具：把短随机串“拉长”

OTP 需要一长串随机比特。如果能把一个短的随机串拉成一长串看起来随机的比特，就能用短密钥代替长密钥。

伪随机生成器就做这件事：输入一个短的随机种子（比如 128 位），按固定算法输出一长串比特（比如一百万位）。同一个种子总得到同一个输出。

“看起来随机”的含义也用游戏来定义。鉴定师拿到一长串比特，要判断它来自生成器，还是真正的随机串：

sequenceDiagram
    participant D as 鉴定师
    participant Judge as 考官
    alt 情况一
        Note over Judge: 随机抽短种子 s，算 x = G(s)
    else 情况二
        Note over Judge: 直接抽一长串真随机比特 x
    end
    Judge-->>D: 长串 x（不给看种子）
    D->>Judge: 判断是哪种情况

如果任何跑得动的鉴定师都只能以接近 50% 的概率判断正确，就称 $G$ 是伪随机生成器（Pseudorandom Generator，PRG）。

两点说明：

• 能力无限的鉴定师可以区分：把所有种子试一遍，检查 $x$ 是不是某个种子的输出。所以伪随机只对跑得动的对手成立。
• PRG 是否存在，至今无法证明。我们假设它存在，这就是第 3 节“假设”一词的含义。

一句话：只防跑得动的攻击者、允许可忽略的优势；PRG 把短种子拉成看起来随机的长串。

6. 伪一次一密：短密钥加密一条消息

对应 Lecture 5

6.1 做法

把 OTP 的长密钥换成 PRG 的输出：密钥是短种子 $k$，加密时先算出长掩码 $G(k)$，再异或。

$$c=G(k)\oplus m,m=G(k)\oplus c.$$

例（示意，真实种子至少 128 位）：设 $G(01)=10110010$，明文 $m=11110000$，密文 $c=01000010$。Bob 同样算出 $G(01)$，异或回去。

这个方案叫伪一次一密（伪 OTP）。

6.2 为什么能安全加密一条消息

若掩码 $G(k)$ 换成真随机串，方案就变成 OTP，Eve 只能瞎猜。所以，如果 Eve 在伪 OTP 上能猜得明显好于 50%，她其实就是察觉到了“掩码不是真随机的”。

把这个直觉变成证明：用 Eve 搭出一个鉴定师 B。B 拿到一串来源不明的长串 $x$，把它当成掩码，给 Eve 出一道猜硬币题：

sequenceDiagram
    participant Eve as Eve（会攻击伪 OTP）
    participant B as 鉴定师 B
    participant Judge as PRG 考官
    Judge-->>B: 来源不明的长串 x
    Eve->>B: 两条消息 m₀, m₁
    Note over B: 自己抛硬币 b
    B-->>Eve: 密文 x ⊕ m_b
    Eve->>B: 猜 b
    Note over B: Eve 猜对就判“x 来自 G”

$x$ 来自 $G$ 时，Eve 面对的正是伪 OTP；$x$ 是真随机时，Eve 面对的是 OTP，只能猜对一半。所以 Eve 猜得越准，B 就越能区分两种情况。但 PRG 假设说没有这样的 B，因此也没有这样的 Eve。

这种论证叫归约：“如果能攻破方案，就能攻破积木；积木攻不破，所以方案也攻不破。”后面所有安全证明都是这个套路。

6.3 失效：同一密钥用两次

伪 OTP 每次都用同一个掩码 $G(k)$，又回到了 OTP 复用密钥的问题：$c_1\oplus c_2=m_1\oplus m_2$。

把猜硬币游戏改成“一次交两组消息”就能体现这个问题：

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有 k）
    Eve->>Judge: 第 0 组：(0000, 0000)<br/>第 1 组：(0000, 1111)
    Note over Judge: 暗中抛硬币 b，用同一个 k 加密第 b 组的两条
    Judge-->>Eve: 两条密文 c₁, c₂
    Note over Eve: c₁ = c₂ 就猜第 0 组，否则猜第 1 组

第 0 组两条消息相同，用同一个掩码加密后，两条密文也相同；第 1 组则一定不同。Eve 每次都猜对。

更一般地，任何“同一明文总得到同一密文”的方案（确定性加密）都会这样失败。要让同一把密钥加密多条消息，每次加密都必须掺入新的随机性，让同一条明文每次加密出来都不一样。

一句话：伪 OTP 用 PRG 掩码安全地加密一条消息；但掩码固定，第二条就泄露了，必须引入随机性。

7. 更强的 Eve：能让 Alice 帮她加密

对应 Lecture 6

现实中的 Eve 往往不只是旁观。比如她给 Alice 发一封邮件，Alice 的系统自动加密转发，Eve 就拿到了“自己选的明文”对应的密文。

在游戏中，这相当于给 Eve 开一个加密窗口：递进去任意明文，窗口递出用同一把密钥加密的密文。窗口里面的密钥她看不到。挑战前后都可以使用，还可以根据之前的结果决定下一次递什么。

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有 k）
    loop 挑战前，任意多次
        Eve->>Judge: 明文 m（加密窗口）
        Judge-->>Eve: m 的密文
    end
    Eve->>Judge: m₀, m₁
    Note over Judge: 暗中抛硬币 b
    Judge-->>Eve: 挑战密文 c*
    loop 挑战后，继续使用
        Eve->>Judge: 明文 m
        Judge-->>Eve: m 的密文
    end
    Eve->>Judge: 猜 b

这叫选择明文攻击（Chosen-Plaintext Attack，CPA）；Eve 仍然猜不准，就叫 CPA 安全。

前面的方案在这里马上失败：

• 确定性加密：Eve 把 $m_0$ 递进窗口，拿回的密文和 $c^{\ast }$ 一比，相同就是 $m_0$。
• 伪 OTP：Eve 递进全零消息，拿回的密文就是掩码 $G(k)$ 本身，之后所有消息都能解开。

所以需要一种方案：每次加密都用新的掩码，但又不需要 Alice 和 Bob 事先共享更多密钥。

一句话：CPA 让 Eve 拥有加密窗口；方案必须每次加密都不一样，而且窗口的回复不能帮她解开挑战密文。

8. 伪随机函数：一本只有双方会查的随机字典

对应 Lecture 6、Lecture 7

8.1 想法：每次翻到随机的一页

设想 Alice 和 Bob 共享一本巨大的字典，每一页上写着一串随机比特。每次加密时：

1. Alice 随机翻到某一页 $r$，用这一页的内容当掩码。
2. 她把页码 $r$ 和“掩码 ⊕ 明文”一起发出。页码可以公开，因为 Eve 没有这本字典。
3. Bob 翻到同一页，取出掩码，异或还原。

每次随机翻页，同一条明文每次加密结果都不同；Eve 即使通过加密窗口看到了一些页的内容，下次 Alice 大概率会翻到一页 Eve 没见过的。

问题是这本字典太大：$n$ 位页码就有 $2^n$ 页，没法事先交换。解决办法是用一个短密钥 $k$ 加一个公开算法 $F$，让双方能随时“算出”任意一页的内容 $F_k(r)$，而且算出来的字典看起来和真正随机的字典一样。

8.2 “看起来像随机字典”是什么意思

先说清楚“真正随机的字典”（随机函数）：每一页的内容在第一次被查时掷骰子决定，之后再查同一页，照抄上次的结果。查过的页知道内容，没查过的页完全猜不到。

“看起来一样”仍用鉴定师游戏定义。这次鉴定师可以反复提问：

sequenceDiagram
    participant D as 鉴定师
    participant Dict as 黑盒字典
    Note over Dict: 情况一：用短密钥算出的 F_k<br/>情况二：掷骰子填的随机字典
    loop 多次，可以看了回复再决定下一次查哪页
        D->>Dict: 页码 x
        Dict-->>D: 这一页的内容
    end
    Note over D: 判断是哪种情况

若任何跑得动的鉴定师都分辨不出，就称 $F$ 为伪随机函数（Pseudorandom Function，PRF）。它和 PRG 的区别：PRG 只给你看一长串；PRF 让你随意挑位置查看。

8.3 做法

公式只有一行：

$${\mathsf{Enc}}_k(m)=⟨r,F_k(r)\oplus m⟩,r\text{ 每次随机抽取}.$$

但其中每个量的来历都不同：有的事先定好，有的每次重抽；有的公开发送，有的从不离开 Alice 和 Bob。先逐一列清楚：

量	是什么	谁产生、怎么产生	何时产生、用几次	Eve 知道吗
算法 $F$	由密钥和页码算出一页内容的公开方法	公开标准	固定不变	知道
密钥 $k$	决定“字典”内容的秘密	见面时均匀随机抽取 $n$ 位	事先一次，以后每条消息都用它	不知道
页码 $r$	这次用字典的哪一页	Alice 的加密程序每次均匀随机抽取 $n$ 位	每次加密重抽，只用一次	知道，随密文发送
掩码 $F_k(r)$	第 $r$ 页的内容	Alice、Bob 各自用 $k$ 算出	每次加密一个	不知道，从不发送
明文 $m$	要说的话	Alice	—	不知道
$s=F_k(r)\oplus m$	掩盖后的消息	Alice 计算	每次加密一个	知道，随密文发送

密文就是公开的两部分 $⟨r,s⟩$。下面用示意数据把一次完整的通信画出来。设 $k$ 对应的字典前四页为

页码 $r$	00	01	10	11
$F_k(r)$	0111	1010	0001	1100

sequenceDiagram
    participant Alice as Alice（知道 k）
    participant Eve as Eve（知道算法 F，不知道 k）
    participant Bob as Bob（知道 k）
    Note over Alice,Bob: 事先：见面时随机抽取密钥 k，只有两人知道，之后一直使用
    Note over Alice: 第 1 次加密 m = 1001<br/>1. 随机抽页码 r = 10<br/>2. 用 k 算掩码 F_k(10) = 0001<br/>3. s = 0001 ⊕ 1001 = 1000
    Alice->>Bob: 公开发送 ⟨r, s⟩ = ⟨10, 1000⟩
    Note over Eve: 看到 r = 10、s = 1000<br/>知道是第 10 页，但没有 k，算不出这页内容
    Note over Bob: 1. 读出页码 r = 10<br/>2. 用 k 算 F_k(10) = 0001<br/>3. m = 1000 ⊕ 0001 = 1001
    Note over Alice: 第 2 次加密同一条 m = 1001<br/>重新抽 r = 01，掩码 F_k(01) = 1010<br/>s = 1010 ⊕ 1001 = 0011
    Alice->>Bob: 公开发送 ⟨01, 0011⟩
    Note over Eve: 两次密文完全不同<br/>看不出是同一条明文
    Note over Bob: 用 k 算 F_k(01) = 1010<br/>0011 ⊕ 1010 = 1001

几个要点：

• 页码可以公开：它只说明“用哪一页”，而一页的内容必须用 $k$ 才能算出。这就像告诉别人“密码写在我日记第 10 页”，日记本不在他手里，告诉他也没用。
• 页码必须每次随机重抽：如果两次用了同一页，掩码就相同，又回到第 4.4 节密钥复用的问题，$s_1\oplus s_2=m_1\oplus m_2$。随机抽 $n$ 位，撞上旧页码的概率是 $2^{-n}$ 量级。
• 随机性由 Alice 的加密程序产生，不由 Eve 控制：即使 Eve 用加密窗口递进明文，她也只能决定 $m$，不能指定这次用哪一页。
• Bob 不需要记住任何状态：每条密文自带页码，Bob 只凭 $k$ 和收到的 $r$ 就能解密，消息丢失或乱序都不影响。
• 代价是每条密文多出 $n$ 位页码，长度变成明文的两倍。第 9 节会讨论怎样减少这个开销。

8.4 为什么 CPA 安全

Eve 从加密窗口学到的，只是她碰巧见过的那些页的内容。挑战密文用的页 $r^{\ast }$ 是随机抽的，和她见过的页撞上的概率至多是“查询次数 $q$ ÷ 总页数 $2^n$”，可以忽略。只要没撞上，这一页对她就是全新的随机掩码，挑战密文就像 OTP 一样安全。

严格证明分成四步，每步只改一个地方，称为混合论证。它的作用是把“差别很大的两个世界”拆成几段“每段差别都很小”的路：

flowchart TB
    H0["世界 0：用真实的 F_k，挑战加密 m₀"]
    H1["世界 1：换成随机字典，挑战加密 m₀"]
    H2["世界 2：随机字典，挑战改为加密 m₁"]
    H3["世界 3：换回真实的 F_k，挑战加密 m₁"]
    H0 -->|"只换字典：分不出，否则违反 PRF 假设"| H1
    H1 -->|"只换消息：没撞页时掩码全新，像 OTP"| H2
    H2 -->|"只换字典：同第一步"| H3

世界 0 和世界 3 正是真实方案加密 $m_0$ 与加密 $m_1$。每一步的差别都可以忽略，三步加起来仍可忽略，所以 Eve 分不清 $m_0$ 和 $m_1$。

第一步和第三步用的是第 6 节的归约：搭一个“中间人”，它手里只有黑盒字典，却能替 Eve 回答所有加密请求：

sequenceDiagram
    participant Eve as Eve（只会攻击加密）
    participant B as 中间人 B（没有密钥）
    participant Dict as 黑盒字典
    Eve->>B: 请加密明文 m
    Note over B: 自己抽页码 r
    B->>Dict: 查第 r 页
    Dict-->>B: 内容 y
    B-->>Eve: ⟨r, y ⊕ m⟩
    Note over B: 挑战密文也这样生成<br/>最后把 Eve 的答案原样交出

黑盒是真实的 $F_k$ 时，Eve 身处世界 0；黑盒是随机字典时，Eve 身处世界 1。所以 Eve 若能分辨这两个世界，B 就能分辨黑盒，违反 PRF 假设。

一句话：PRF 是短密钥算出来的“随机字典”；每次随机翻一页当掩码，就得到 CPA 安全的加密。

9. 长消息怎么办：分组密码与工作模式

对应 Lecture 7、Lecture 8

9.1 直接逐块加密太浪费

长消息切成若干块 $m_1,m_2,\dots$，每块用第 8 节的方法加密，每块都要附带一个页码，密文变成明文的两倍长。下面的方法都想只附带一个随机值，甚至不附带。

9.2 新积木：分组密码 = 可以还原的洗牌

分组密码 $E_k$ 把一块 $b$ 位的数据变成另一块 $b$ 位的数据，并且可以用 $D_k$ 变回来。可以想成用密钥 $k$ 把所有 $b$ 位串“洗一次牌”：每个输入对应唯一的输出，不同输入不会撞到一起。

例（2 位，示意）：$E_k$：$00\to 10$，$01\to 00$，$10\to 11$，$11\to 01$。

它的安全要求是“看起来像一次真正的随机洗牌”，同样用鉴定师游戏定义，称为伪随机置换（PRP）。如果鉴定师还能反过来问“这个输出原来是谁”，仍然分辨不出，就叫强伪随机置换。

它和 PRF 的区别：PRF 的随机字典允许两页内容碰巧相同，也不要求能反查；分组密码必须一一对应、可以还原。

9.3 ECB：每块单独洗

flowchart LR
    m1["m₁"] --> E1["E_k"] --> c1["c₁"]
    m2["m₂"] --> E2["E_k"] --> c2["c₂"]

最省事，但同一把密钥下，相同的明文块永远得到相同的密文块。用上面的例子加密 00 00 01，得到 10 10 00，Eve 一眼看出前两块一样。加密一张图片时，大片同色区域变成大片相同的密文块，轮廓仍然可见。它连一条消息都保护不了。

9.4 CBC：先混入上一块，再洗

为了让相同的块得到不同的结果，每块加密前先异或上一块的密文；第一块异或一个随机抽取、公开发送的初始值（IV）。

flowchart TB
    IV["IV（随机，公开）"] --> X1(("⊕"))
    m1["m₁"] --> X1
    X1 --> E1["E_k"] --> c1["c₁"]
    c1 --> X2(("⊕"))
    m2["m₂"] --> X2
    X2 --> E2["E_k"] --> c2["c₂"]

例：IV $=11$，明文 00 00。第一块 $E_k(00\oplus 11)=E_k(11)=01$，第二块 $E_k(00\oplus 01)=E_k(01)=00$。相同的明文块，密文不同了。

只要 IV 每次随机抽取，CBC 就是 CPA 安全的。缺点：必须算完上一块才能算下一块，加密无法并行。解密时 $m_i=D_k(c_i)\oplus c_{i-1}$，所有密文块都已收到，可以并行。

例题：IV 能被提前猜到时，CBC 就会被攻破（Chained CBC）

有人想省掉 IV：每条消息直接用上一条消息的最后一块密文当 IV。问题是 Eve 在选下一条明文之前就已经知道这个 IV。

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有 k）
    Eve->>Judge: 加密窗口：一块明文 m
    Judge-->>Eve: IV 与 c₁ = E_k(IV ⊕ m)
    Note over Eve: 下一条消息的 IV 就是 c₁，已知
    Eve->>Judge: 挑战：m₀ = IV ⊕ m ⊕ c₁，m₁ 任取其他值
    Note over Judge: 用 c₁ 作 IV，加密 m_b
    Judge-->>Eve: c*
    Note over Eve: c* = c₁ 就猜 m₀，否则猜 m₁

若加密的是 $m_0$，分组密码的输入是 $c_1\oplus m_0=\mathsf{IV}\oplus m$，与第一次完全相同，输出必然又是 $c_1$。若是 $m_1$，输入不同，输出一定不同。Eve 每次都猜对。

教训：IV 不仅要不重复，还要在 Eve 选明文时猜不到。

9.5 OFB 与 CTR：用 PRF 生成一长串掩码

另一条思路回到“掩码 ⊕ 明文”：用 PRF 从一个随机起点出发，生成一长串掩码（称为密钥流），再与整条消息异或。这类方案统称流密码。明文不经过 $F_k$，所以不需要 $F_k$ 可以还原，PRF 就够了。

OFB：把 $F_k$ 反复作用在随机的 IV 上，一块接一块地生成掩码。

flowchart TB
    IV["IV（随机，公开）"] --> F1["F_k"] --> r1["掩码 r₁"]
    r1 --> F2["F_k"] --> r2["掩码 r₂"]
    r1 --> X1(("⊕"))
    m1["m₁"] --> X1 --> c1["c₁"]
    r2 --> X2(("⊕"))
    m2["m₂"] --> X2 --> c2["c₂"]

CTR：从随机起点 $\mathsf{ctr}$ 开始数数，第 $i$ 块的掩码是 $F_k(\mathsf{ctr}+i)$，相当于在字典里连续翻页。

flowchart LR
    t1["ctr + 1"] --> F1["F_k"] --> X1(("⊕"))
    m1["m₁"] --> X1 --> c1["c₁"]
    t2["ctr + 2"] --> F2["F_k"] --> X2(("⊕"))
    m2["m₂"] --> X2 --> c2["c₂"]

两者都 CPA 安全。OFB 的掩码一块依赖上一块，只能串行；CTR 每块的掩码独立，可以并行，还能只解密第 $i$ 块。CTR 安全的关键是：两条消息用到的“页码区间”几乎不可能重叠，否则掩码就重复了。

模式	用的积木	每条消息附带	防得住 CPA	加密能否并行
ECB	分组密码	无	否	能
CBC	分组密码	随机 IV	是	否
OFB	PRF	随机 IV	是	否，但掩码可提前算好
CTR	PRF	随机起点	是	能

一句话：分组密码是可还原的洗牌；ECB 会暴露重复块，CBC 靠随机 IV 打乱；OFB、CTR 用 PRF 生成长掩码。

10. 更更强的 Eve：还能让 Bob 帮她解密

对应 Lecture 8

再给 Eve 一项能力：她可以把自己构造的密文发给 Bob，观察 Bob 解出了什么，例如服务器会把解密结果或报错返回给她。在游戏中，这相当于再开一个解密窗口。唯一的禁令是不能把挑战密文 $c^{\ast }$ 原样递进去，否则游戏没有意义。

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有 k）
    loop 挑战前，任意多次
        Eve->>Judge: 明文（加密窗口）
        Judge-->>Eve: 密文
        Eve->>Judge: 密文（解密窗口）
        Judge-->>Eve: 解密结果
    end
    Eve->>Judge: m₀, m₁
    Note over Judge: 暗中抛硬币 b
    Judge-->>Eve: 挑战密文 c*
    loop 挑战后，继续使用两个窗口
        Eve->>Judge: 明文，或任何不等于 c* 的密文
        Judge-->>Eve: 对应结果
    end
    Eve->>Judge: 猜 b

这叫选择密文攻击（Chosen-Ciphertext Attack，CCA）。第 8 节的方案在这里立刻失败，因为 Eve 可以把挑战密文改一改再递进去：

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有 k）
    Eve->>Judge: m₀, m₁
    Judge-->>Eve: c* = ⟨r, s⟩，其中 s = F_k(r) ⊕ m_b
    Note over Eve: 把 s 随便改成另一个值 s′
    Eve->>Judge: 解密窗口：⟨r, s′⟩（不是 c*，允许）
    Judge-->>Eve: F_k(r) ⊕ s′
    Note over Eve: 再异或 s′ 得到掩码 F_k(r)<br/>再异或 s 就得到 m_b

根源在于异或的“开关”性质：改动密文的某些位，解出的明文就在同样的位置翻转，变化完全可以预测。这叫可延展性（malleability）。OFB、CTR 同理；CBC 改动 IV 也会让第一块明文跟着变。所以本课到目前为止的方案，全都防不住 CCA。

一句话：CCA 让 Eve 还拥有解密窗口；“掩码 ⊕ 明文”式的方案能被改装，全部失败。

11. 保密之外：防篡改

对应 Lecture 8

即使没有解密窗口，可延展性本身就很危险。假设 Alice 用伪 OTP 发送“转账 100 元”，Eve 知道消息格式，猜到金额是 100。她把密文中金额的部分异或上 $(\text{“100”}\oplus \text{“900”})$，Bob 解密后读到的就是“转账 900 元”。Eve 没有解开任何东西，Bob 也察觉不到。

所以除了“看不懂”（保密性），还需要另一个目标：Bob 能确认消息确实来自 Alice、没有被改过（完整性）。加密不负责这件事。

办法是给消息盖一个“只有持钥人能盖的防伪章”，叫消息认证码（Message Authentication Code，MAC）：

sequenceDiagram
    participant Alice as Alice（有 k）
    participant Eve as Eve
    participant Bob as Bob（有 k）
    Note over Alice: 算标签 t = Mac_k(m)
    Alice->>Bob: (m, t)
    Note over Eve: 想把 m 改成 m′，<br/>但没有 k，配不出新标签
    Note over Bob: 检查 Verify_k(m, t)：通过才接受

一个 MAC 有三个步骤：生成密钥 $\mathsf{Gen}$、计算标签 ${\mathsf{Mac}}_k(m)$、验证 ${\mathsf{Verify}}_k(m,t)$（输出 1 表示接受）。基本要求是诚实生成的标签一定能通过验证。如果计算标签没有随机性，Bob 验证时只需自己重算一遍、比较是否相同，这叫规范验证。

有了防伪章，接下来要回答：怎样才算“Eve 伪造不出标签”，以及怎样造出这样的章。见第 12 节。

一句话：加密只管保密，不管篡改；防篡改要靠 MAC，即只有持钥人能生成的标签。

12. 防伪章怎样才算安全：伪造游戏

对应 Lecture 9

12.1 游戏规则

现实中 Eve 可能见过很多盖了章的消息，甚至能让 Alice 给她指定的消息盖章（比如寄一份文件请 Alice 签收）。所以游戏里给 Eve 一个盖章窗口：递进去任意消息，拿回它的标签。最后 Eve 交出一份“伪造品” $(m^{\ast },t^{\ast })$。

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有 k）
    loop 任意多次
        Eve->>Judge: 消息 m（盖章窗口）
        Judge-->>Eve: 标签 t
    end
    Eve->>Judge: 伪造品 (m*, t*)
    Note over Judge: Eve 赢的条件：<br/>标签能通过验证，并且 m* 没让窗口盖过章

• “$m^{\ast }$ 没盖过章”是为了排除作弊：把窗口盖好的消息原样交上去当然能通过。
• 这个游戏没有抛硬币。Eve 不是在猜，而是要做成一件事，所以要求是：她成功的概率本身可以忽略，而不是“不超过 50%”。

这样定义的 MAC 叫安全的 MAC。还有一个更严格的版本：如果盖章带随机性，同一条消息每次盖出来的章不同，那么 Eve 给盖过章的消息造出一个新的合法章，也算她赢。满足这个更严格要求的叫强安全的 MAC。

12.2 用随机字典盖章

第 8 节的“随机字典”可以直接用来盖章：把消息本身当作页码，那一页的内容就是标签。

$$t=F_k(m).$$

Bob 验证时，自己翻到第 $m$ 页，比较内容是否等于 $t$。仍用第 8.3 节的示意字典：

页码	00	01	10	11
内容	0111	1010	0001	1100

量	谁产生、怎么产生	Eve 知道吗
密钥 $k$	见面时随机抽取，一直使用	不知道
消息 $m$	Alice	知道，MAC 不负责保密
标签 $t=F_k(m)$	Alice 用 $k$ 算出	知道，随消息发送

sequenceDiagram
    participant Alice as Alice（知道 k）
    participant Eve as Eve（不知道 k）
    participant Bob as Bob（知道 k）
    Note over Alice: 消息 m = 10<br/>标签 t = F_k(10) = 0001
    Alice->>Bob: (10, 0001)
    Note over Eve: 想改成 m′ = 11<br/>需要 F_k(11)，但第 11 页她从没见过<br/>只能瞎猜一个 4 位串
    Note over Bob: 自己算 F_k(10) = 0001<br/>与收到的标签相同，接受

为什么安全：Eve 交出的消息 $m^{\ast }$ 必须是盖章窗口没盖过的，也就是她没见过的一页。

• 若字典真是随机的，没见过的一页内容完全猜不到，$n$ 位标签猜中的概率只有 $2^{-n}$（示意例子里是 $1/16$）。
• 实际字典是 $F_k$。若 Eve 在 $F_k$ 上伪造得明显比在随机字典上好，就能拿她当鉴定师，区分 $F_k$ 和随机字典，违反 PRF 假设。

这又是第 6、8 节的归约套路，只是这次只需两个世界：先换成随机字典，再算猜中概率。

一句话：MAC 安全 = Eve 有盖章窗口也造不出新消息的合法章；用 PRF 时，标签就是“消息那一页”的内容。

13. 长消息的防伪章：CBC-MAC

对应 Lecture 9

13.1 做法：链式盖章

第 12 节的章只能盖恰好 $n$ 位的消息。长消息切成块 $m_1,m_2,\dots$ 后，若每块单独盖章，标签和消息一样长；而且 Eve 交换两块消息和对应的章，就得到新消息的合法章。

CBC-MAC 像 CBC 一样把各块串起来，只输出最后一个结果：

flowchart LR
    m1["m₁"] --> F1["F_k"] --> t1["t₁"]
    t1 --> X2(("⊕"))
    m2["m₂"] --> X2 --> F2["F_k"] --> t2["t = t₂"]

$$t_1=F_k(m_1),t_2=F_k(t_1\oplus m_2),\dots$$

例（示意，每块 2 位）：设 $F_k$ 为 $00\to 10$，$01\to 11$，$10\to 01$，$11\to 00$。消息 01 10：$t_1=F_k(01)=11$，$t_2=F_k(11\oplus 10)=F_k(01)=11$，标签就是 $11$。中间结果 $t_1$ 不公开。

只要所有消息的块数相同，若 $F$ 是 PRF，CBC-MAC 就是安全的。

13.2 失效：长度可以变时

若允许不同长度的消息，Eve 可以把短消息的标签当成长消息链上的中间值，拼出新消息。用上面的示意 $F_k$：

sequenceDiagram
    participant Eve as Eve
    participant Judge as 考官（持有 k）
    Eve->>Judge: 盖章：单块消息 01
    Judge-->>Eve: t₁ = F_k(01) = 11
    Eve->>Judge: 盖章：两块消息 01 ‖ 00
    Judge-->>Eve: t₂ = F_k(11 ⊕ 00) = F_k(11) = 00
    Note over Eve: 单块消息 00 ⊕ 11 = 11 的标签<br/>就是 F_k(11)，即 t₂ = 00
    Eve->>Judge: 伪造品 (11, 00)
    Note over Judge: F_k(11) = 00，通过；消息 11 没盖过章，Eve 赢

原因：两块消息 01 00 的链，第二步算的是 $F_k(t_1\oplus 00)$。Eve 已经知道 $t_1$，于是单块消息 $t_1\oplus 00$ 的标签正好就是这一步的结果。CBC-MAC 分不清“链在这里结束了”还是“链还要继续”。

13.3 两种修补

• 长度前置：先对“消息有几块”盖一次章，从这个结果开始链接。长度不同的消息，链的起点就不同，短消息的标签不再是长消息链上的中间值。长度必须放在开头。
• 再盖一层章：用另一把独立密钥 $k_2$，把链的最后结果再过一次 $F_{k_2}$ 才公开。公开的标签不再等于链上的任何中间值，Eve 没法把它接到下一块上。

一句话：CBC-MAC 把各块串起来只出一个标签；长度可变时能被拼接伪造，要么把长度放在开头，要么最后再用另一把密钥盖一层。

14. 保密和防伪一起要：认证加密

对应 Lecture 9

现在有了两类工具：加密负责“看不懂”，MAC 负责“改不了”。实际通信两样都要，合起来叫认证加密（Authenticated Encryption，AE）：

1. 保密：即使 Eve 有加密窗口和解密窗口（CCA），看到密文也得不到明文信息。
2. 不可伪造：Eve 改动密文或自己造一个密文，Bob 解密时一律拒绝，输出“无效”（$\perp$）。

两条是相连的：只要被改过的密文一律被拒绝，第 10 节那种“改一改再请求解密”的攻击就只能拿回“无效”，解密窗口对 Eve 没用了。

一句话：认证加密 = 防得住 CCA 的保密 + 被篡改的密文一律被拒。

15. 回头看：整门课的结构

现在每个名词都讲过了，可以把它们放进同一张图里。

15.1 四类内容

类别	白话	本课的例子
定义	考什么：Eve 能做什么、怎样算赢	完美保密、单消息、多消息、CPA、CCA；MAC 安全、强安全；认证加密
积木（假设）	相信它安全、但证明不了的零件	PRG、PRF、分组密码（PRP）
构造	用积木搭出的方案	OTP、伪 OTP、PRF 加密、ECB、CBC、OFB、CTR；PRF 定长 MAC、CBC-MAC 及其修补
证明	解释为什么积木安全推出方案安全，或给出攻击	归约、混合论证、具体攻击

flowchart LR
    subgraph T["积木"]
        PRG["PRG"]
        PRF["PRF"]
        PRP["分组密码"]
    end
    subgraph S["构造"]
        OTP["OTP"]
        POTP["伪 OTP"]
        PENC["PRF 加密"]
        MODES["OFB、CTR"]
        CBC["CBC"]
        PMAC["PRF 定长 MAC"]
        CMAC["CBC-MAC 修补版"]
    end
    subgraph D["通过的定义"]
        PS["完美保密"]
        EAV["单消息"]
        CPA["CPA"]
        MSEC["MAC 安全"]
    end
    OTP --> PS
    PRG --> POTP --> EAV
    PRF --> PENC --> CPA
    PRF --> MODES --> CPA
    PRP --> CBC --> CPA
    PRF --> PMAC --> MSEC
    PRF --> CMAC --> MSEC

15.2 两类目标，各自的阶梯

保密这条线上，攻击者一步步变强：

flowchart TB
    A1["单消息：只看一条密文"]
    A2["多消息：看同一把密钥下的多条密文"]
    A3["CPA：还有加密窗口"]
    A4["CCA：还有解密窗口"]
    A1 -->|"多看几条"| A2
    A2 -->|"能主动要加密"| A3
    A3 -->|"能主动要解密"| A4

越往下，Eve 越强，要求越严。防得住强 Eve 的方案，一定防得住弱 Eve；反过来不成立。

防伪这条线上：安全的 MAC（造不出新消息的章）→ 强安全的 MAC（连旧消息的新章也造不出）。两条线最后在认证加密汇合。

15.3 方案成绩单

方案	怎么做	通过	倒在	倒下的原因
OTP	与等长随机密钥异或	完美保密	多消息	密钥复用，$c_1\oplus c_2=m_1\oplus m_2$
伪 OTP	与 $G(k)$ 异或	单消息	多消息	掩码固定
PRF 加密	随机页码 $r$，与 $F_k(r)$ 异或	CPA	CCA	改密文后请求解密
ECB	每块单独洗牌	—	单消息	相同块得到相同密文块
CBC	混入上一块再洗，随机 IV	CPA	CCA	改 IV 即改明文
Chained CBC	用上一条最后一块当 IV	—	CPA	IV 可提前猜到
OFB、CTR	PRF 生成密钥流再异或	CPA	CCA	翻转密文位，明文同位翻转
PRF 定长 MAC	标签 $=F_k(m)$	MAC 安全（定长）	—	只能处理 $n$ 位消息
CBC-MAC	链式盖章，只出最后一块	MAC 安全（块数固定）	变长消息	短消息标签 = 长消息链的中间值
CBC-MAC 修补版	长度前置，或最后再过 $F_{k_2}$	MAC 安全（变长）	—	—

15.4 贯穿全课的教训

1. 掩码绝不能重复。 OTP 复用密钥、伪 OTP 固定掩码都因此失败；PRF 加密和 CTR 的安全证明，关键都是“掩码撞车的概率可以忽略”。
2. 加密多条消息，必须带随机性。 确定性加密在多消息和 CPA 下必败，所以安全方案都有随机值：页码 $r$、IV、计数起点。随机值可以公开，但必须在 Eve 选明文时猜不到。
3. 看不懂不等于改不了。 异或式加密可以被有目的地改动，这既让它们防不住 CCA，也让 Bob 察觉不到篡改，于是引出 MAC。
4. 别泄露链上的中间状态。 Chained CBC 把下一条的 IV 提前暴露，变长 CBC-MAC 把短消息的标签变成了长消息链的中间值，两者都让 Eve 能“接着链往下算”。

15.5 名词速查

名词	白话	位置
密钥、明文、密文	共享的秘密；原话；乱码	第 1 节
完美保密	看到密文后，对明文的了解完全不变	第 3 节
异或 $\oplus$	按位的开关：遇 1 翻转，遇 0 不变	第 4 节
OTP	与等长随机密钥异或，只用一次	第 4 节
安全参数 $n$	大致是密钥长度	第 5 节
PPT	跑得动的程序	第 5 节
可忽略	小到重复多项式次仍然很小	第 5 节
PRG	把短种子拉成看似随机的长串	第 5 节
伪 OTP	用 PRG 输出代替 OTP 的长密钥	第 6 节
归约	能攻破方案 ⟹ 能攻破积木	第 6 节
CPA	Eve 有加密窗口	第 7 节
PRF	短密钥算出来的“随机字典”	第 8 节
混合论证	每次只改一处，一步步从世界 0 走到世界 3	第 8 节
分组密码、PRP	可以还原的、看似随机的洗牌	第 9 节
IV	每条消息随机抽取、公开发送的起始值	第 9 节
ECB、CBC、OFB、CTR	长消息的四种加密方式	第 9 节
CCA	Eve 还有解密窗口	第 10 节
可延展性	改密文能可预测地改明文	第 10 节
MAC	只有持钥人能生成的防伪标签	第 11 节
伪造游戏、MAC 安全	有盖章窗口也造不出新消息的合法章	第 12 节
强安全	连盖过章的消息也造不出新章	第 12 节
CBC-MAC	链式盖章，只输出最后一块	第 13 节
认证加密	防 CCA 的保密 + 篡改密文一律被拒	第 14 节