密码学复习笔记

第一章密码学概述

对称密钥加密概述

通讯双方预先共享某种秘密信息（密钥，或称对称密钥 symmetric key）。发送方采用密钥来加密信息，接收方通过相同的密钥来解密信息。消息本身称为明文(plaintext)，加密后的消息成为密文(ciphertext).

对称密钥的应用，至少需要一个基础：key本身的传递是秘密的。这限制了对称加密的应用场景。当然，在之后，通过 Diffie-Hellman 密钥协商机制（透过不安全的信道，协商出只有双方知道的一个数），可以部分地解决这个问题。

对称密钥方案由三个部分组成：密钥产生、加密、解密。

密钥产生算法 Gen ：是一个概率算法，能从方案所定义的分布里面选一个密钥 $k$ 出来。
加密算法 Enc：输入密钥 $k$ 和明文 $m$，输出密文 $c = \text{Enc}_k(m)$.
解密算法 Dec：输入密钥 $k$ 和密文 $c$，输出明文 $m = \text{Dec}_k(c)$.

Gen 输出的所有可能值，构成了密钥空间 $\mathcal{K}$. 我们上面声称它是从方案所定义的分布里面取密钥，实际上一般情况下可以假设这个分布是均匀的。

所有能作为 Enc 输入的信息构成了明文空间 $\mathcal{M}$. 显然，$\langle \mathcal{K,M} \rangle$ 唯一定义了密文空间 $\mathcal{C}$，也就是所有可能出现的密文。

由此我们知道，一个对称加密算法，可以由三个算法 $(\text{Gen, Enc, Dec})$ 以及明文空间 $\mathcal{M}$ 来定义。显然，若一个对称加密算法是有效的，必须满足 Dec 是 Enc 的逆运算，亦即 $$\text{Dec}_k( \text{Enc}_k (m) ) = m, \qquad \forall m \in \mathcal{M}$$

对称加密方案的工作流程如下：首先，运行 Gen 来得到密钥，通讯双方得知密钥；当发送方需要发出消息时，计算 $c := \text{Enc}_k(m)$，然后可以透过公开的信道发送 $c$. 接收方收到 $c$ 之后，计算 $m:= \text{Dec}_k(m)$，即可恢复原信息。

Kerckhoffs 原则

加密方法不应该被保密，唯一需要保密的是通信双方的 key.
(Kerckhoffs's principle, 柯克霍夫原则)

柯克霍夫原则要求，一个加密方案的安全性，仅取决于密钥的安全性，而不取决于算法的秘密。接受 Kerckhoffs 原则会带来很多好处：首先，由于加密算法是公开的，通讯各方只需要保密密钥（这显然比加密算法要短，按常理来讲，越短的东西越容易保密）。另外，如果密钥泄露了，双方只需要改个新的密钥就能继续安全通信（若不遵循 Kerckhoffs 原则，一旦泄露算法就需要重新设计加密方案）。最后，遵循 Kerckhoffs 原则可以带来标准化的好处：多人通讯时，可以采用相同的算法而选择不同的密钥，这样程序可以复用。

密码学的攻击场景

我们把攻击的严重程度由高到低归类（当然，攻击难度也依次递减）：

唯密文攻击(Ciphertext-only Attack, COA). 敌方观察到一个或多个密文，试图确定明文。
已知明文攻击(Known-plaintext Attack, KPA). 地方已知一个或多个使用相同密钥加密的明文-密文对。攻击目标是，对于其他密文，可以确定明文。
选择明文攻击(Chosen-plaintext attack, CPA). 敌方可以选择明文要求加密，并得到加密结果。攻击目标同上。
选择密文攻击(Chosen-ciphertext attack, CCA). 敌方可以选择密文要求解密。攻击目标同上。

当今，被广泛应用的密码方案，未必能对抗以上四种攻击（尤其是CCA）。对于特定的应用场景，需要兼顾安全性和效率。

古典密码：Caesar

凯撒密码企图通过字母代换达到加密的目的。也就是说：

$\text{Gen}$ 输出一个 $[0, 25]$ 范围的随机数 $k$.
$\text{Enc}_k(m) \equiv (m + k) \pmod {26}$.
$\text{Enc}_k(c) \equiv (c - k) \pmod {26}$.

显然，只需要枚举密钥 $k$，就能获得 26 个候选明文，从而判断真正的明文。

充分密钥空间原则

任何安全的加密方案，其密钥空间 $\mathcal{K}$ 必须能抵御穷举搜索。
(这一原则在 $|\mathcal{M}| > |\mathcal{K}|$ 时有效。若可能的明文比可能的密钥还少，枚举出所有可能的密钥，解密之后会获得比明文空间还大的候选明文集合。)

根据当前计算机的计算能力，密钥空间需要非常大，例如$2^{70}$.

需要注意的是，满足充分密钥空间原则的加密方案，未必就是安全的。来看下面的例子。

古典密码：单表代换 / 单字母替换

单字母替换(substitution)为每一个明文字母指派了一个密文字母。显然，$\mathcal{K}$ 的大小是 $26! \approx 2^{88}$，这是符合充分密钥空间原则的。然而，通过我们关于明文的统计知识，单表替换密码很容易被攻破。

一个正常的英文文本，每个字符的概率分布是已知的。文本越长，这个现象越显著（亦即，各个字母的出现频率越接近标准的英文字母频率）。从而可以快速猜测密码。

IoC 可以将这一判断过程自动化。

index of coincidence (IoC，重合因子)

英文的字频统计规律，在单表替换之后会错位。但我们考虑另一种统计方式：若每个字母的出现概率是 $p_i$，那么对于普通的英文文本，不难计算出 $$\sum p_i^2 \approx 0.065$$

判断一个串是否由英文单表替换而来：现在假设我们想要判断一个代换之后的串，在代换之前是否满足英文字母频率，那么我们记代换后字频为 $q_i$，它的集合显然与 $p_i$ 的集合相同。从而有 $$\sum q_i^2 \approx \sum p_i ^2 \approx 0.065$$

否则，若 $q_i$ 是随机的，那计算结果应该约为 $0.038$.

判断一个单表替换方案是否合适：假设我们认为明文的字母 $i$ 对应密文的字母 $s_i$. 那么，如果这个替换方案是正确的，则解密之后得到的明文，必然满足英文字母分布频率。亦即： $$\sum p_i \cdot q_{s_i} \approx \sum p_i^2 \approx 0.065$$

Vigenere 密码

维吉尼亚密码是多表代换密码。它循环使用一个 key 表，对于每一个明文字母，加上 key 得到密文。显然，维吉尼亚密码的本质，即是用 Caesar 方法加密明文的第 $i, i+t, i+2t\cdots$ 这些位置。

攻击维吉尼亚密码，一般先找到 key 长度，再确定 key. 要判断 key 长度，可以采用 Kasiski 方法：若一个串在密文中多次出现，则有很大概率它们由相同的明文加密而来；在这种情况下，一对重复串之间的距离，很大概率是 key 长度的倍数。于是可以判断 key 长度。

笔者更喜欢 Ioc 方法：首先猜测密文长度 $t$，要验证是否确实如此，只需要取出密文的 $i, i+t, i+2t\cdots$ 这一共 $t$ 组加密结果。第 $i$ 组是由 key 的第 $i$ 位通过 Caesar 加密而来，故每一组的字频平方和(IoC)应该约等于 $0.065$. 找到最符合这个要求的 $t$，即为 key 长度，或者 key 长度的倍数。

在知道 key 长度之后，可以把密文划分为 $t$ 组，每组都是一个 Caesar。拿去字频分析即可，这一步也可以采用 IoC 方法，见上文的【判断一个单表替换方案是否合适】。

上述针对 Caesar 和 vigenere 的攻击都是唯密文攻击。vigenere 比 Caesar 稍微安全一些，但是仍然被频率分析方法攻破。我们意识到，通过简单的手段达到安全是不太现实的。

现代密码学的基本原则

我们提出密码学的三个主要原则：

对“安全”的定义必须是公式化的、表述严格且精确的。
若密码学方案的安全性依赖于某个未被证明的假设，这种假设必须精确陈述，且假设需要尽可能少。
密码学方案应该有严格的安全证明。

原则一：对安全的定义

把安全定义为“攻击者不能计算出密钥”是不行的。反例：$\text{Enc}_k(m) := m$，没有任何人可以从 $c$ 里面猜出 $k$，但明文已经泄露干净了。把安全定义为“攻击者不能计算出明文”也是不行的，反例：加密算法只加密明文的前100个字节，后面部分原样输出。攻击者不能计算出明文，但显然这个加密方案是不安全的。把安全定义为“攻击者不能得知明文的任何一个字节”也是不太行的，若攻击者虽然不能得知明文的任何一个字节，但可以得知某些关键信息（例如，在一份加密的雇佣合同中，攻击者得知这个打工人的工资是大于1000块还是小于1000块），这也是不安全的。

一个合适的定义：若敌手无法从密文中计算出任何关于明文的函数，那么加密方案是安全的。也就是说，$key$未知的条件下，密文中不包含有明文的任何信息。这个对安全的定义，称为无条件安全。然而实践上，大部分的密码体系都达不到无条件安全的级别。

原则二：精确的假设

大部分密码方案达不到无条件安全。许多密码方案对这个问题做了让步——安全性依赖于某种假设。现代密码学要求，若一个方案的安全性依赖于假设，则假设必须被精确地陈述。

假设是暂无数学证明的、但据推测是正确的命题。例子：“大整数分解是无法在多项式时间内完成的”。

原则三：严格的安全证明

大部分的密码学安全证明采用了规约方法，也就是说，给出了定理：“若假设 X 是正确的，根据给定的定义，构造方案 Y 是安全的”。证明通常是展示如何将 X 归约到“攻破 Y”. 也就是说，假设敌手能攻破 Y，那么将会与 X 冲突。

$\def\Gen{{\textsf{Gen}}} \def\Enc{{\textsf{Enc}}} \def\Dec{{\textsf{Dec}}} \def\Enck{{\textsf{Enc} _ k}} \def\Deck{{\textsf{Dec} _ k}} \def\KK{{\mathcal{K}}} \def\MM{{\mathcal{M}}} \def\CC{{\mathcal{C}}} \def\AA{{\mathcal{A}}} \def\PrivK{{\textsf{PrivK}}} \def\eav{{\textsf{eav}}} \def\PrivKeav{{\PrivK^\eav}} $

第二章完善保密加密

一些定义

我们沿用之前讨论过的 Gen, Enc, Dec 三元组来定义加密方案。密钥产生算法 Gen 是概率的，每次运行会从 $\mathcal{K}$ 里面选一个输出（这个 $\KK$ 显然是有穷集）。加密算法 Enc 可能是概率的，也就是说 $\Enck(m)$ 多次运行可能输出不同的密文。但是 Dec 是确定的。

约定一下符号：我们用 $c \leftarrow \Enck(m)$ 表示这是概率过程，用 $c := \Enck(m)$ 表示 Enc 是确定的。

$\KK$ 和 $\MM$ 的分布是独立的。也就是说，密钥的选择与明文的选择互相独立。另外，$\KK$ 的分布一般是由加密方案本身决定，但 $\MM$ 的分布与这个加密方案的使用者有关。

现在，我们来定义完善保密加密的概念。假设敌手知道 $\MM$ 的概率分布（priori，先验分布），也就是说敌手知道发送各种消息的可能性（例如，发送“下雨”的概率是30%，发送“晴天”的概率是70%）。在理想的情况下，敌手从密文中不会学习到任何知识，亦即在密文已知的情况下，明文的分布（posteriori，后验分布）应该与先验分布相同。这意味着，密文没有泄露任何明文信息。形式化的表述如下：

明文空间为 $\MM$ 的加密方案 $(\Gen, \Enc, \Dec)$ 是完善保密加密，当且仅当对于 $\MM$ 上任意的概率分布，$\forall m\in \MM, c\in \CC$ 且 $\Pr[C=c]>0$，有 $$\Pr[M=m\mid C=c] = \Pr[M=m]$$

这个式子就是描述了“后验概率等于先验概率”。另一种等价的解释是：当且仅当明文和密文的分布是独立的，方案才是完善保密加密。

一个等价的公式：$$\Pr[C=c\mid M=m] = \Pr[C=c]$$

也就是说，若密文的先验概率等于后验概率，则方案也是完善保密加密。现在我们证明这与原来的公式等价。

充分性：两边乘以 $P(m)$ 除以 $P(c)$，拿贝叶斯搞一搞就出来了。
必要性：贝叶斯搞一搞就出来了。

完美不可区分性

完善保密加密还有一个等价的表述：$\CC$ 的分布独立于明文。亦即，用 $\CC(m)$ 表示加密 $m\in M$ 时的密文分布（它取决于密钥的选择、加密算法），那么 $\CC(m_0)$ 与 $\CC(m_1)$ 的分布是相同的。我们称此为完美不可区分性，因为不可能区分 $m_0$ 的密文与 $m_1$ 的密文（因为它们的分布是一样的）。

明文空间为 $\MM$ 的加密方案 (Gen, Enc, Dec) 是完善保密加密，当且仅当对于任意 $\MM$ 的概率分布，每个 $m_0, m_1\in \MM$ 和每个 $c\in \CC$，均有 $$\Pr[C=c\mid M=m_0] = \Pr[C=c\mid M=m_1]$$

必要性：若方案是完善保密加密，那么它一定满足完美不可区分性。因为 $$\Pr[C=c\mid M=m_0] = \Pr[C=c] = \Pr[C=c\mid M=m_1]$$

充分性：先贝叶斯$$P(c) = \frac{\sum P(c\mid m_i) \cdot P(m_i)}{\sum P(m_i)} = \sum P(c\mid m_i)\cdot P(m_i)$$
注意到 $P(c\mid m_i)$ 恒等，而 $\sum P(m_i) = 1$，故这式子就等于 $P(c\mid m_i)$. 证毕。

敌手不可区分性

这是完善保密加密的又一个等价定义。它基于一个涉及敌手 $\AA$ 的实验，断言“$\AA$ 不能区分出密文是来自哪个明文”，故称为敌手不可区分性。

考虑任意加密方案 $\Pi=(\Gen, \Enc, \Dec)$，任意敌手为 $\AA$. 用 $\PrivKeav$ 表示一个给定 $\Pi$ 和 $\AA$ 的实验。实验的定义如下：

窃听不可区分实验 $\def\PrivKA{{\PrivK ^ \eav_{\AA, \Pi}}} \PrivKA $ ：
1. 敌手 $\AA$ 输出一对信息 $m_o, m_1 \in \MM$.
2. 由 $\Gen$ 产生一个随机密钥 $k$，并且从 ${0, 1}$ 里面随机选择一个比特 $b$. 然后，计算密文 $c\leftarrow \Enck(m_b)$ 交给 $\AA$.
3. $\AA$ 输出一个比特 $b ^\prime$.
4. 若 $b ^ \prime = b$，定义实验的输出为 $1$；否则为 $0$. 若输出为 1，记为 $\PrivKA = 1$，此时称 $\AA$ 成功。

也就是说，$\AA$ 的任务是尽可能猜出密文从哪个明文加密而来。显然，如果它随机猜测，有 50% 的概率成功。完善保密加密的另一种定义是：如果没有敌手能以大于 0.5 的概率成功，那么这种加密方案就是完善保密加密。注意这里 $\AA$ 的计算能力没有限制。

方案 (Gen, Enc, Dec) 为完善保密加密，当且仅当对于所有敌手都满足 $$\Pr[\PrivKA = 1] = \frac12$$

$\def\lb{{\{}} \def\rb{{\}}}$

一次一密

一次一密方案定义如下：
令整数 $l>0$，设 $\MM,\KK,\CC = \lb 0, 1\rb ^ l$.
Gen 从 $\KK = \lb 0,1 \rb ^ l$ 里面按均匀分布选取一个二进制串。
$\Enck(m)$：输出 $c:= k\oplus m$
$\Deck(c)$：输出 $m:= k\oplus c$

这个方案是完善保密加密，因为给定 $c$，敌手完全无法判断来自哪个 $m$. 密钥 $k$ 对敌手而言是未知的，且选中的概率一样高；对攻击者而言，明文与密钥是一一对应，故对攻击者而言，这个 $c$ 来自所有明文的概率都均等。下面给一个严格证明。

$$\forall c, m:\quad \Pr[C=c\mid M=m] = \Pr[M\oplus K = c \mid M=m] = \Pr[m\oplus K = c] = \Pr[K = m\oplus c] = \frac1{2^l}$$

从而 $P(c\mid m_0) = P(c\mid m_1)$. 证毕。

尽管一次一密理论上是完善保密加密的，但需要密钥与明文长度相同，这会导致通讯双方需要交换一个很长的密钥。另外，一次一密仅在密钥只使用一次的情况下是安全的，若攻击者截获两条用相同密钥加密的密文，则密文异或等于明文异或，这会泄露明文信息。

完善保密的局限性

上述的问题不仅是 Vernam 这一个方案的问题。所有的完善保密加密，密钥空间都不小于明文空间。

设 (Gen, Enc, Dec) 是完善保密加密方案，则 $|\KK| \geq |\MM|$.

证明如下：若不然，则考虑攻击者截获到一个密文 $c$. 考虑攻击者利用所有的 $k$ 尝试解密，解密结果形成了集合 $\MM(c)$. 显然 $|\MM(c)| \leq |\MM|$，于是存在一些 $m_x\in M$，却不在 $\MM(c)$ 里面。于是，攻击者断言 $\Pr[M=m_x \mid C=c] = 0$，于是违背了完善保密加密。

香农定理

香农提出了完善保密加密的一种性质：若 $|\KK| = |\MM| = |\CC|$，则 Gen 必须均匀随机选择 $k$，且对于任意明文、任意密文，存在唯一的 $k$ 来把这个明文加密成这个密文。

（香农定理）设加密方案 (Gen, Enc, Dec) 的明文空间为 $\MM$，且 $|\KK| = |\MM| = |\CC|$，则当且仅当下列条件成立时，此方案是完善保密加密：
1. Gen 产生任何密钥的概率都是 $1/|\KK|$
2. 对任意 $m\in \MM, c\in \CC$，存在唯一的密钥 $k\in\KK$，使得 $\Enck(m) = c$

不难看出，香农定理的结论非常强。应用香农定理时，需要注意 $\KK, \MM, \CC$ 必须大小相等。

第三章对称密码学

若干定义

在上一章我们讨论了“假设敌手有无限的计算能力”情形下的密码学，这样的方案称为“信息理论安全”或“完美安全”，它们的安全性基于敌手没有足够的信息来完成攻击，而不管敌手的计算能力。

计算安全是更为可行的方案。它使得攻击者无法在可以接受的时间内完成攻击，从而达到实用的密码学目标。计算安全一般是这样的形式：

一个方案为 $(t, \varepsilon)$ 安全，如果每个运行时间最多为 $t$ 的敌手以最多 $\varepsilon$ 的概率成功攻破方案。

举个例子：某方案保证，在最多运行 $2^{80}$ 个 CPU 周期的情况下，没有人能以高于 $2^{-64}$ 的概率攻破方案。这显然提供了很高的安全性。

在接下来的内容中，我们采用渐进方法来研究。把敌手的运行时间和成功概率视为（关于某个参数的）函数，而不是具体数值。一个密码方案包含一个安全参数 $n$，双方生成密钥时，采取 $n$ 作为安全参数，敌手也知道这个 $n$，则敌手的运行时间和成功概率，都可以视为 $n$ 的函数。

这将帮助我们研究两个概念：

“有效的算法”，其运行时间应该是 $n$ 的多项式级别。我们把多项式时间内运行的概率算法称为概率多项式算法。概率多项式时间简写为 PPT.
“小的成功概率”，应该比任何关于 $n$ 的多项式的倒数级别更小。也就是说，$\forall c$，当 $n$ 的值足够大，敌手成功的概率小于 $\frac{1}{n ^ c}$. 比任何多项式的倒数都增长得慢的函数，称为可忽略的(negligible). 一个典型例子是，$2^{-n}$ 比任何多项式的倒数都增长得慢。

于是，渐进安全的定义一般采用下面的形式：

如果每一个 PPT 敌手攻破一个方案的概率是可忽略的，则方案是安全的。

举一个例子：一个方案可能保证，多项式运行时间的敌手，攻破方案的概率是 $2^{-n}$. 显然，$n=10$ 的时候几乎无法保证任何安全性，但 $n=100$ 的时候很安全。

更大的安全参数，提供了更高的安全性。很多加密方案采用密钥长度作为安全参数。

有效的算法

一个算法 A 在多项式时间内运行，当且仅当存在一个多项式 $p(\cdot)$，使得对于每个输入 $x\in \lb 0, 1\rb^*$，$A(x)$ 的计算在最多 $p(|x|)$ 个步骤内终止。

一个概率多项式时间(PPT)算法，是在多项式时间算法的基础上，还允许算法获取到随机数。

一个多项式时间算法，可以调用多项式时间的子算法。

需要注意的是，目前认为，概率多项式时间的敌手，未必一定比确定性的多项式时间敌手更强大。不过我们在这里把我们的对手建模成概率多项式的，提供只可能更强、不可能更弱的保证。

可忽略的成功率

设 $p$ 为某多项式。如果敌手攻破方案的概率是 $1/p(n)$ 级别，那么我们认为这是不安全的。如果敌手攻破方案的概率比每一个多项式还（渐进地）小，那我们认为方案安全。定义如下：

称函数 $f$ 为可忽略的，当且仅当对于每一个多项式 $p$，存在一个 $N$ 使得 $$f(n) < \frac1{p(n)}, \quad \forall n>N$$
一个等价表述：对于所有常量 $c$，$\exists N, s.t. \forall n>N, f(n)<n^{-c}$.

我们把一个可忽略函数表示为 negl，例如 $2^{-n}, 2^{-\sqrt n}, n^{-\log n}$ 都是可忽略的。

可忽略函数也有着闭包特性。

两个 negl 的和也是 negl.
多项式乘以 negl，得到 negl.

这意味着，一个可忽略概率的事件，重复实验多项式次，其发生的概率还是可忽略的。

如果一个攻破密码方案的事件发生概率是 negl，则是不重要的。

规约证明

许多方案依赖于假设（某难题难以攻破）的正确性。对它们的证明，一般方式如下：说明如何将任何概率不可忽略的攻破该方案的有效敌手 $\AA$，转换为能用来成功解决该难题的敌手 $\AA^\prime$. 公式化地，步骤如下：

指定某个 PPT 敌手 $\AA$ 来攻击 $\Pi$. 将敌手的成功概率表示成 $\varepsilon(n)$.
构造一个 PPT 算法 $\AA^\prime$，这个算法调用 $\AA$，试图解决难题 $X$. 在这里，$\AA^\prime$ 将子程序 $\AA$ 视为一个黑盒。$\AA^\prime$ 接受问题 $X$ 的输入，然后模拟出 $\Pi$ 的环境，调用 $\AA$；如果 $\AA$ 成功攻破了由 $\AA^\prime$ 模拟出来的 $\Pi$ 实例，则 $\AA^\prime$ 解决难题 $X$，成功率不可忽略（i.e. 至少为多项式的倒数）。
如果 $\varepsilon(n)$ 是不可忽略的，则 $\AA^\prime$ 解决 $X$ 的概率也是不可忽略的。这与原假设矛盾，故完成证明，断言 $\Pi$ 是计算安全的。

计算安全的加密

现在，我们来重新定义对称密钥加密的语法。现在我们有了安全参数可以用，默认消息空间是二进制串。

一个对称密钥加密方案是 PPT 算法 (Gen, Enc, Dec) 的三元组。
1. 密钥生成算法 Gen 的输入是安全参数 $1^n$，输出密钥 $k$. 记为 $k\leftarrow \Gen(1 ^ n)$
2. Enc 将密钥 $k$ 和明文 $m\in \lb 0,1 \rb ^ *$ 作为输入，并输出密文 $c$. 记为 $c \leftarrow \Enck(m)$
3. Dec 将 $k,c $ 作为输入，输出消息 $m$. 它是确定性的，记为 $m := \Deck(c)$

另外，需要满足 $\Deck(\Enck(m)) = m$.

若 (Gen, Enc, Dec) 满足：对每个由 $\Gen(1^n)$ 输出的密钥 $k$，算法 $\Enck$ 只对消息 $m\in \lb 0,1 \rb ^ {\ell(n)}$ 有定义，则 (Gen, Enc, Dec) 是一个消息长度为定长 $\ell(n)$ 的对称密钥加密方案。

窃听不可区分实验

我们之前已经建立起敌手不可区分实验，来等价地描述完善保密加密。现在，为了描述计算安全，我们也定义一个实验。这个实验相比起之前的实验，只考虑PPT敌手；要求敌手判断正确的概率大于0.5的程度是 negl 的。

另外，为了方便，我们要求信息 $m_0, m_1$ 相等。

窃听不可区分实验 $\PrivKA(n)$：
1. 给定输入 $1^n$ 给敌手 $\AA$，$\AA$ 输出一对长度相等的信息 $m_0, m_1$.
2. 运行 $\Gen(1 ^ n)$ 生成一个密钥 $k$，选择一个随机比特 $b$，计算 $\def\la{{\leftarrow}} c\la \Enck(m _ b)$ 并交给 $\AA$. 这里的 $c$ 称为挑战密文。
3. $\AA$ 输出一个比特 $b^ \prime$.
4. 若 $b=b ^ \prime$，则实验输出为 1；否则为 $0$. 若 $\PrivKA(n) =1$，则称 $\AA$ 成功。

上面只限制了挑战明文的长度相等。如果是分析定长的加密方案，则添加约束条件，要求 $m_0, m_1$ 长度等于 $\ell(n)$.

接下来，我们就可以利用窃听不可区分实验，来定义计算安全性：如果在上面的实验中，任何 PPT 敌手的成功概率高于 0.5 的部分可忽略，则这个加密方案是安全的。

如果对于所有 PPT 敌手 $\AA$，存在一个可忽略函数 $\def\negl{{\textsf{negl}}} \negl$ 使得 $$\Pr[\PrivKA(n) = 1] \leq \frac12 + \negl(n)$$ 则对称加密方案 $\Pi=(\Gen, \Enc, \Dec)$ 是在窃听者存在的情况下不可区分的加密。

之所以称之为“窃听者存在情况下”，是因为 $\AA$ 只能收到单个挑战密文，与发送方没有更多的交互。这也就是说，$\AA$ 只有窃听的能力。

语义安全

对于一个对称密钥方案 $(\Gen, \Enc, \Dec)$，若对于所有 PPT 敌手 $\AA$，存在一个 PPT $\def\AAp{{\AA ^ \prime}} \AAp$，使得对于所有有效可采样的分布 $X=(X _ 1, \cdots)$ ，以及所有多项式时间可计算的函数 $f, h$，存在一个可忽略函数 $\negl$ 满足 $$\left | \Pr[\AA(1 ^ n, \Enck(m), h(m) ) = f(m)] -\Pr[\AAp (1 ^ n, h(m)) = f(m)] \right | \leq \negl(n)$$ 则称其为窃听者存在的情况下是语义安全的。

上面的公式中，$h(m)$ 可以代表对 $m$ 的先验知识。如果一个方案是语义安全的，那么拥有密文的 $\AA$ 并不比没有密文的 $\AAp$ 高明（具体而言，在猜测某个关于 $m$ 的函数时，正确率是相等的），说明密文本身没有泄露关于明文的任何信息。

不难发现，语义安全是非常强的安全性。但其定义十分复杂，难以直接利用。但我们可以将之转化为窃听不可区分实验：

一个对称密钥加密方案，具备窃听者存在情况下的不可区分性，当且仅当它在窃听者存在的情况下语义安全。

从而，我们只需要证明一个加密算法是窃听者不可区分的，就能证明它是语义安全的。这大大简化了我们的工作。

伪随机性

一个伪随机的字符串，是看起来很像真正取自均匀分布的字符串（前提是，这个“看”的过程实在多项式时间内运行）。如果说一个长度为 $l$ 的字符串的分布 $\def\DD{{\mathcal{D}}} \DD$ 是伪随机的，那么意味着 $\DD$ 与均匀分布是不可区分的。更准确地说：对于任何多项式时间算法，分辨出一个字符串是 $\DD$ 的样本还是均匀分布的样本，是不可行的。

关于伪随机性在密码学中的作用，有一个直观的例子：考虑一个加密方案，如果密文是伪随机的，则在任何 PPT 敌手的角度上看，这个密文与真正的随机串没有任何区别：从而不会携带关于明文的任何信息。

伪随机发生器(PRG)

如果没有多项式时间的区分器能把一个 $\DD$ 的样本与一个真随机的字符串区分开来，则这个分布 $\DD$ 是伪随机的。一个伪随机发生器是一个确定性算法，接受一个较短的种子，将其扩展成为一个长的伪随机字符串。

令 $\ell(\cdot)$ 为多项式，令 $G$ 为确定多项式时间算法。这个算法满足：对于任何输入 $\def\b{{\lb 0, 1 \rb}} \def\bn{{\lb 0, 1 \rb ^ n}} s\in \bn$，$G$ 输出一个长度为 $\ell(n)$ 的字符串。如果满足下面的两个条件，则称 $G$ 是一个伪随机发生器：
1. 扩展性：对于每个 $n$，有 $\ell(n) > n$.
2. 伪随机性：对于所有的 PPT 区分器 $\def\DD{{\mathcal{D}}} \DD$ 来说：$$\Big|\Pr[D(r) = 1] - \Pr [D(G(s)) =1] \Big| \leq \negl(n)$$ 其中 $r$ 是从 $\b ^ {\ell(n)}$ 中均匀随机选择的；$s$ 是从 $\bn$ 中均匀随机选择的。

可见，一个 PRG 接受短的种子，扩充到 $\ell(n)$ 位长度，且对于任何 PPT 来说，无法区分“随机种子的 PRG 的输出”与“真随机串”。我们称 $\ell(\cdot)$ 为 $G$ 的扩展系数。

由于 $n$ 往往比 $\ell(n)$ 小很多，故 PRG 实际能输出的数的个数，要远远少于 $\b ^ {\ell(n)}$. 这样来看，如果敌手的计算能力是无限的，那他可以不停地运行 PRG 来得到 PRG 所能产生的比特串的表，然后对于所有在表里的就输出 1；不在表里的就输出 0. 最终成功率会相当高。

伪随机数是真随机数在计算能力上的松弛。正因为敌手没有无限的计算能力，伪随机数才能骗过所有的 PPT 敌手。

显然，一个伪随机数发生器的种子，必须均匀选取，对区分器保密。另外，实践上，种子应该足够长，使得攻击者没办法在可行时间内暴力枚举所有种子。

目前，我们还不知道伪随机发生器是否真的存在。但我们倾向于认为存在，而且已经造出了许多在现实生活中可用的发生器。

用 PRG 构造定长加密方案

首先，令 $G$ 是一个扩展因子为 $\ell$ 的PRG. 构造加密方案如下：

Gen：随机选择 $k \in \bn$
Enc： $c := G(k) \oplus m$
Dec： $m := G(k) \oplus c$

也就是把一次一密方案修改一下，用于异或的流改用 PRG 来生成。密文、明文的长度都是 $\ell(n)$.

现在我们来证明它是语义安全的，亦即窃听不可区分的。

考虑任意的 PPT 敌手 $\AA$，定义 $\def\eps{{\varepsilon}} \eps$：$$\eps(n) \triangleq \Pr[\PrivKA(n) = 1] - \frac12$$

显然，如果 $\AA$ 能攻破 $\Pi$（可以判断出密文来源），那么 $\eps(n)$ 是不可忽略的，反之亦然。

接下来，我们构造一个针对 $G$ 的区分器 $\DD$ 如下：

$\DD$ 获取到输入 $ \def\bln{\b ^ {\ell(n)}} w\in \bln$，然后 $\DD$ 进行如下操作：

运行 $\AA(1 ^ n)$，$\AA$ 产生一对消息 $m_0, m_1$ 交回给 $\DD$.

$\DD$ 随机选择一个比特 $b$，令 $c := w \oplus m_b$.

把 $c$ 发给 $\AA$，$\AA$ 猜测 $c$ 是源于 $m_0$ 还是 $m_1$，将猜测结果 $\def\bp{{b ^ \prime}} \bp$ 交给 $\DD$. 如果 $\bp = b$，则 $\DD$ 输出 1；否则输出 0.

现在，我们来分析这个 $\DD$ 的行为。一共只有两种可能：

如果 $w$ 是随机选择的，此时 $\AA$ 完全等同于做了一次一密，从而 $\def\tPi{{\widetilde\Pi}}\Pr[\DD(w) = 1] = \Pr[\PrivK ^ {\eav} _ {\AA, \tPi} = 1] = \frac12$，其中 $\tPi$ 是长度为 $\ell(n)$ 的一次一密方案。

如果 $w$ 是取自伪随机发生器的，则此时 $\AA$ 的行为完全与题设中的 $\Pi$ 一致——加密方案是异或上 $G(k)$，故 $\AA$ 的成功概率是 $\frac12 + \eps(n)$. 此时 $$\Pr[D(w) = 1] = \Pr[D(G(k)) = 1] = \Pr[\PrivKA(n) = 1] = \frac12 + \eps(n)$$

综上，我们得到 $\Big | \Pr[D(w) = 1] - \Pr[D(G(k)) = 1] \Big |= \eps(n)$，按照 PRG 的性质，$\eps(n) = \negl$，从而 $\AA$ 无法攻破 $\Pi$，故 $\Pi$ 是语义安全的。

处理变长信息

我们显然很希望造出一共伪随机发生器，来生成任意长度的比特流。具体而言，我们希望变长 PRG 接受两个输入：种子 $s$ 和长度 \ell$，然后 $G$ 输出一个长度为 $\ell$ 的伪随机字符串。

一个确定的多项式时间算法 $G$，如果满足以下三个条件，则它是一个输出长度可变的伪随机发生器：

令 $s$ 是一个字符串，$\ell > 0$. 则 $G(s, 1 ^ \ell)$ 输出一个长度为 $\ell$ 的字符串。

$\forall s, \ell, \def\ellp{{\ell ^ \prime}} \ellp$，有 $\ell < \ellp$，且字符串 $G(s, 1 ^ \ell)$ 是 $G(s, 1 ^ \ellp)$ 的前缀。

定义 $\def\Gells{{G_\ell(s)}} \Gells \triangleq G(s, 1 ^ {\ell(|s|)})$，也就是说：对于每个多项式 $\ell$，我们都可以给出一个扩展因子为 $\ell$ 的伪随机发生器 $\Gells$. 这个过程是通过可变长度的 PGR，造出定长的 PRG.

任何定长 PRG，都可以转化为不定长 PRG. 利用不定长 PRG，显然可以构造出一个不定长的私钥加密方案：利用 $G(k, 1 ^ {|m|})$ 来异或明文就行了。它可以支持任意长度的加密，而且也是语义安全的。

流密码

上面介绍的利用 PRG 的异或方案，称为流密码。想要执行加密，是先生成一个伪随机的比特流，然后用这个比特流来与明文异或，产生密文。由于流密码方案与生成比特流的方案是绑定的，我们以后直接用“流密码”来简称伪随机比特串发生器。

实际应用中，有 RC4 等流密码方案。RC4 不太安全，LFSR 非常不安全。目前来看，主张采用分组密码来进行加密；如果一定要用流密码，一般用分组密码造一个流出来。

多次加密的安全性

我们之前的讨论，全部是基于“敌手收到单个密文”的情况。但现实中，监听信道的窃听者往往可以听到多组密文，我们引入多消息窃听实验来对应这种情形。

多消息窃听实验 $\def\PrivKM{{\PrivK ^ {\textsf{mult}} _ {\AA, \Pi} }} \PrivKM(n)$：

敌手 $\AA$ 获取安全参数 $1 ^ n$，输出一对消息向量 $\vec M _ 0 = (m _ 0 ^ 1, \cdots, m _0 ^ t)$ 以及 $\vec M _ 1 = (m _ 1 ^ 1, \cdots, m _1 ^ t)$. 对于所有 $i$，需要满足 $|m _ 0 ^ i| = |m _ 1 ^ i|$（对应位置的明文必须等长）。

运行 $\Gen(1 ^ n)$ 生成密钥 $k$，选择随机比特 $b$.
计算密文 $c ^ i \la \Enck(m _ b ^ i)$，将密文向量 $\vec C = (c ^ 1, c^2, \cdots c ^ t)$ 发给 $\AA$.

$\AA$ 输出一个比特 $\bp$.

若 $\bp =b$，则实验输出 1；否则输出 0.

利用这个多消息窃听实验，可以定义多次加密不可区分性。定义方法与窃听不可区分性一致：

对于一个对称密钥加密方案 $\Pi$，若对于所有 PPT 敌手 $\AA$ 有 $$\Pr\left [ \PrivKM(n) = 1 \right ] \leq \frac12 + \negl$$ 则称 $\Pi$ 具备多次加密不可区分性。

显然，vernam 加密方法如果总是采用相同密钥，则它满足窃听不可区分性，但不满足多次加密不可区分性。构造方法如下：

$\AA$ 输出 $M_0 = (0 ^ n, 0 ^ n), M_1 = (0^n, 1^n)$
$\AA$ 对于返回的加密结果，只需要看看 $c^1$ 是否等于 $c^ 2$，如果相等则输出 $\bp = 0$，否则输出 $\bp = 1$.

容易证明，$\AA$ 的成功概率是 100%.

概率加密

上面的例子已经证明了重放攻击的巨大威力。事实上，不难看出，如果相同的明文总会被加密成相同的密文，那么上面这个例子始终可以攻击成功。

我们从而发现，任何确定性的加密方案，对于多次加密来讲，都是不安全的。

令 $\def\GED{{(\Gen,\Enc,\Dec)}} \Pi=\GED$ 为一个加密方案，若 $\Enc$ 是密钥和消息的一个确定性的函数，则 $\Pi$ 不具备窃听者存在情况下的多次加密不可区分性。

从而，要想做到多次加密不可区分，必须当相同的消息多次加密时，每次都产生不同的密文。

流密码安全多次加密方案

一般有两种基于流密码的多次方案，分别为同步模式和非同步模式。

同步模式：双方使用密钥流的不同部分来加密每个信息。在这个模式下，双方必须同步通讯，来得知流的多少位已经被使用。这个算法虽然是确定性的，但在每一次加密过程中，密钥是互不重复的，因此对于每次加密来说，相同的明文也会被加密成不同的密文。

非同步模式：双方可以独立进行加密，无需维护状态。但是，这里需要 PRG 有两个输入：一个种子 $s$ 以及一个初始向量 $IV$. 如果两个 $IV$ 不一样，那么 PRG 的生成结果也不一样。

在非同步模式下，加密方法为 $$\Enck(m) := \langle IV, G(k,IV) \oplus m \rangle$$ 其中 $IV$ 是随机选择，与异或结果一起输出。攻击者虽然能得到 $IV$，但由于没有种子 $k$，故仍然无法解密。

选择明文攻击(CPA)安全性

现在我们来考虑更强的攻击，即 CPA 攻击。敌手 $\AA$ 允许访问一个 oracle，这个 oracle 能采用密钥 $k$ 加密信息并返回给敌手（敌手不知道 $k$）。

计算机科学常用 $\def\OO{{\mathcal{O}}}\def\AO{{\AA^{\mathcal{O}(\cdot)}}} \AO$ 来表示 $\AA$ 访问 oracle $\OO$ 的过程。因此在这里，我们可以用 $\def\AE{{\AA ^ {\Enck(\cdot)}}} \AE$ 来表示 $\AA$ 访问密钥为 $k$ 的加密 oracle.

如果 $\Enc$ 过程是随机的，那么 oracle 每次回答一个询问，都会引入随机性。CPA 安全要求：即使敌手可以访问加密 oracle，敌手仍然不能区分两个任意消息的加密。

CPA不可区分实验 $\def\PrivKC{{ \PrivK_{\AA,\Pi} ^ {\textsf{cpa}} }} \PrivKC(n)$：

运行 $\Gen(1 ^ n)$ 生成密钥 $k$.

给敌手输入 $1 ^ n$，敌手可以访问 $\def\Enckd{\Enck(\cdot)} \Enckd$，输出一对长度相等的信息 $m_0, m_1$.

选择一个随机比特 $b$，计算出 $c \la \Enck(m _ b)$ 交给 $\AA$. $c$ 称为挑战密文。

敌手 $\AA$ 可以继续访问 oracle. 最后输出一个比特 $\bp$.

若 $\bp = b$，则试验输出 1；否则输出 0. 若 $\PrivKC(n) = 1$，则认为敌手 $\AA$ 成功。

由此可以定义CPA 安全性。

一个对称密钥加密方案 $\Pi=\GED$，如果对于所有 PPT 敌手 $\AA$，有 $$\Pr\Big[ \PrivKC(n) =1 \Big] \leq \frac12 + \negl(n)$$ 则称 $\Pi$ 具有在选择明文攻击(CPA)条件下的不可区分性。

显然，“CPA安全”是比“窃听不可区分”更强的性质。任何确定性的加密方案，都不可能具有 CPA 安全性。换句话来讲，加密过程必须有随机性。

另有一点需要指出：单次加密 CPA 安全性，等价于多次加密 CPA 安全性。想要证明方案 $\Pi$ 是多次加密 CPA 安全的，只需证明它是单次加密 CPA 安全的。

如果一个定长的加密方案是 CPA 安全的，我们只需要使用它来加密字符串的各个块，就能得到一个变长的加密方案。显然这也是 CPA 安全的。

伪随机函数

为了构造 CPA 安全的加密方案，我们有必要开始考虑伪随机函数(PRF)。接下来讨论的伪随机函数，用途都是把长度为 $n$ 的字符串映射到等长的字符串。

伪随机函数是带密钥的函数。一个带密钥的函数 $F$ 是双输入函数，$F:\b ^ * \times \b ^ * \to \b ^ *$，一个输入是密钥 $k$，另一个就叫输入。一般而言，密钥只选择一次，而会有很多个输入，故在选定密钥之后，我们关注单输入函数 $\def\Fk{{F _ k}} \Fk(x) \triangleq F(k,x)$.

为讨论方便，我们只研究输入长度、输出长度、密钥长度都相等的 PRF. 如果存在一个确定的多项式时间算法，能够在给定 $k,x$ 的情况下计算出 $\Fk(x)$，则称 $F$ 是有效的（加密方、解密方当然需要 $F$ 是可以计算的，才能用于加密）。

如果函数 $\Fk$ 无法与一个从“拥有同样定义域、值域的函数集合”中均匀随机选出来的函数相区分，那么我们认为 $\Fk$ 是看上去很随机的。换句话讲：如果没有 PPT 敌手可以区分 $\Fk$ 和随机选择的 $f$，则称 $F$ 是伪随机的。

$f$ 是从高达 $2 ^ {n\cdot 2 ^ n}$ 个候选函数里面选出来的，而 $F$ 是从 $2 ^ n$ 个函数里面选出来的。但 $F$ 的行为，对于任何 PPT 区分器来说，都应该看起来和真随机选择的 $f$ 相同。

第一章 密码学概述