密码学复习笔记

第一章 密码学概述

对称密钥加密概述

通讯双方预先共享某种秘密信息(密钥,或称对称密钥 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}$ 来定义。显然,若一个对称加密算法是有效的,必须满足 DecEnc 的逆运算,亦即 $$\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$ 的函数。

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

  1. “有效的算法”,其运行时间应该是 $n$ 的多项式级别。我们把多项式时间内运行的概率算法称为概率多项式算法。概率多项式时间简写为 PPT.
  2. “小的成功概率”,应该比任何关于 $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$. 公式化地,步骤如下:

  1. 指定某个 PPT 敌手 $\AA$ 来攻击 $\Pi$. 将敌手的成功概率表示成 $\varepsilon(n)$.
  2. 构造一个 PPT 算法 $\AA^\prime$,这个算法调用 $\AA$,试图解决难题 $X$. 在这里,$\AA^\prime$ 将子程序 $\AA$ 视为一个黑盒。$\AA^\prime$ 接受问题 $X$ 的输入,然后模拟出 $\Pi$ 的环境,调用 $\AA$;如果 $\AA$ 成功攻破了由 $\AA^\prime$ 模拟出来的 $\Pi$ 实例,则 $\AA^\prime$ 解决难题 $X$,成功率不可忽略(i.e. 至少为多项式的倒数)。
  3. 如果 $\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$ 进行如下操作:

  1. 运行 $\AA(1 ^ n)$,$\AA$ 产生一对消息 $m_0, m_1$ 交回给 $\DD$.
  2. $\DD$ 随机选择一个比特 $b$,令 $c := w \oplus m_b$.
  3. 把 $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$,如果满足以下三个条件,则它是一个输出长度可变的伪随机发生器:

  1. 令 $s$ 是一个字符串,$\ell > 0$. 则 $G(s, 1 ^ \ell)$ 输出一个长度为 $\ell$ 的字符串。
  2. $\forall s, \ell, \def\ellp{{\ell ^ \prime}} \ellp$,有 $\ell < \ellp$,且字符串 $G(s, 1 ^ \ell)$ 是 $G(s, 1 ^ \ellp)$ 的前缀。
  3. 定义 $\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)$:

  1. 敌手 $\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|$(对应位置的明文必须等长)。
  2. 运行 $\Gen(1 ^ n)$ 生成密钥 $k$,选择随机比特 $b$.
    计算密文 $c ^ i \la \Enck(m _ b ^ i)$,将密文向量 $\vec C = (c ^ 1, c^2, \cdots c ^ t)$ 发给 $\AA$.
  3. $\AA$ 输出一个比特 $\bp$.
  4. 若 $\bp =b$,则实验输出 1;否则输出 0.

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

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

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

  1. $\AA$ 输出 $M_0 = (0 ^ n, 0 ^ n), M_1 = (0^n, 1^n)$
  2. $\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)$:

  1. 运行 $\Gen(1 ^ n)$ 生成密钥 $k$.
  2. 给敌手输入 $1 ^ n$,敌手可以访问 $\def\Enckd{\Enck(\cdot)} \Enckd$,输出一对长度相等的信息 $m_0, m_1$.
  3. 选择一个随机比特 $b$,计算出 $c \la \Enck(m _ b)$ 交给 $\AA$. $c$ 称为挑战密文。
  4. 敌手 $\AA$ 可以继续访问 oracle. 最后输出一个比特 $\bp$.
  5. 若 $\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$ 相同。