可证明安全复习

• 之前写过前两章英文版的笔记，现在把这门课的复习备忘整理了一下。

• 相关的参考教程是《Introduction To Modern Cryptography》（Second Edition），其中文版是《现代密码学——原理与协议》。中文版的翻译一言难尽，尤其是到了后面的规约部分。因此建议还是优先考虑英文版。
• 前两章的英文笔记可以参见 Introduction To Modern Cryptography

可证明安全

第一章：引言

掌握现代密码学的三个原则

• 原则 1——形式化定义：解决任何密码学问题的第一步是形式化的表述严格且精确的安全定义
  • 如果特定的敌手不能完成特定的攻破，则对任务的一个密码学方案是安全的
• 原则 2——精确假设：当密码学构造方案的安全性依赖于某个违背证明的假设时，这种假设必须精确地陈述，而且，所假设的要尽可能地少
• 原则 3——安全证明：密码学构造方案应当伴随有严格的安全证明，跟随符合原则 1 的安全定义，以及与原则 2 陈述的假设有关
  • 规约：若给定假设 X 是正确的，根据给定的定义，构造方案 Y 是安全的

理解可证明安全的含义，区分可证明安全和现实安全的关系

第二章：完美保密

掌握完美保密、完美不可区分两种概念及等价性

• 完美保密：

  • 当明文和密文上的分布是独立的，方案才是完美保密的

  （完美保密）对明文空间为 $\mathcal{M}$ 的加密方案 $(\text{Gen}, \text{Enc}, \text{Dec})$ 若下列条件成立：
  若对 $\mathcal{M}$ 上任意的概率分布，任何明文 $m\in \mathcal{M}$，任何密文 $c\in \mathcal{C}$ 且 $\Pr{[C=c]} > 0$，有

  $\Pr{[M=m|C=c]}=\Pr{[M=m]}$

  则该方案是完美保密的。

• 完美不可区分：

  （窃听不可区分实验）$\text{PrivK}^{eav}_{\mathcal{A},\Pi}$：

  1. 敌手 $\mathcal{A}$ 输出一对信息 $m_0,m_1\in \mathcal{M}$；
  2. 由 $\text{Gen}$ 产生一个随机密钥 $k$，并且从 $\left\{0,1\right\}$ 中随机选择一个比特 $b$。然后，一个挑战密文 $c\leftarrow \text{Enc}_k(m_b)$ 被计算出来并交给 $\mathcal{A}$；
  3. $\mathcal{A}$ 输出一个比特 $b'$；
  4. 如果 $b'=b$，定义实验输出为 1，否则为 0。当 $\text{PrivK}^{eav}_{\mathcal{A},\Pi}=1$ 时，称 $\mathcal{A}$ 成功。

  （完美不可区分）对明文空间为 $M$ 的加密方案 $(\text{Gen}, \text{Enc}, \text{Dec})$ 若下列条件成立：
  若对所有敌手都满足：

  $\Pr{[\text{PrivK}^{eav}_{\mathcal{A},\Pi}=1]}=\frac{1}{2}$

  则该方案是完美不可区分的。

• 等价性：完美保密和完美不可区分的定义等价，具体的证明可见英文版习题 2.5

掌握一次一密的原理

• 一次一密方案

  （一次一密）

  1. 令整数 $l > 0$，设明文空间 $\mathcal{M}$，密钥空间 $\mathcal{K}$ 和密文空间 $\mathcal{C}$ 都等于 $\left\{0,1\right\}^l$（即长度为 $l$ 的二进制比特串的集合）；
  2. 密钥产生算法 $\text{Gen}$ 从 $k=\left\{0,1\right\}^l$ 中依据均匀分布选择一个二进制比特串。；
  3. 加密算法 $\text{Enc}$：给定一个密钥 $k\in \left\{0,1\right\}^l$ 和一个明文 $m \in \left\{0,1\right\}^l$，输出 $c:=k\oplus m$；
  4. 解密算法 $\text{Dec}$：给定一个密钥 $k\in \left\{0,1\right\}^l$ 和一个密文 $c \in \left\{0,1\right\}^l$，输出 $m:=k\oplus c$。

• 安全性证明

  • 利用完美保密定义
  • 利用香农定理

  （香农定理）设加密方案 $(\text{Gen}, \text{Enc}, \text{Dec})$ 的明文空间为 $\mathcal{M}$，且 $|\mathcal{K}|=|\mathcal{M}|=|\mathcal{C}|$，则当且仅当下列条件成立时，此方案是完美保密：

  1. 由 $\text{Gen}$ 产生的任意密钥 $k\in \mathcal{K}$ 的概率都是 $\frac{1}{|\mathcal{K}|}$；
  2. 对任意明文 $m \in \mathcal{M}$ 和任意密文 $c\in \mathcal{C}$，只存在唯一的密钥 $k\in \mathcal{K}$ 使得 $Enc_k(m)$ 输出 $c$。

掌握一次一密的优缺点

• 优点：一次一密是完美保密
• 缺点：
  • 密钥要和密文有一样的长度，因此在应用中的存储和共享都是很困难的
  • 如果重用密钥，就会泄露两条消息异或的结果。

    $\begin{aligned}c \oplus c^{\prime} &=(m \oplus k) \oplus\left(m^{\prime} \oplus k\right) \\&=m \oplus m^{\prime}\end{aligned}$

第三章：单钥加密

掌握具体方法和渐近方法的含义

• 具体方法 Concrete Approach

  • 通过明确限定任意敌手在最多某个特定时间内的最大成功概率，对一个给定的密码学方案的安全性进行量化。

  （具体方法）如果每个运行时问最多为 $t$ 的敌手以最多为 $\varepsilon$ 的概率成功攻破一个方案，则称该方案为 $(t, \varepsilon)$ 安全。

• 渐进方法 Asymptotic Approach

  • 来源于复杂性理论（相关知识备忘可见计算理论备忘，将敌手的运行时间以及成功的概率视为某个参数的函数，而非具体数值。
  • 如果每个 PPT（概率多项式时间）的敌手以可忽略的概率成功攻破一个方案，那么该方案是安全的。

  （渐进方法）如果每个概率多项式时间的敌手 $\mathcal{A}$ 执行某个特定类型的攻击，对于每个多项式 $p(\cdot)$，存在一个整数 $N$：对 $n>N, \mathcal{A}$ 在这次攻击中成功的概率小于 $\frac{1}{p(n)}$，则这个方案是安全的。

• 规约证明：对任意消息长度大于密钥长度加密方案的安全性的无条件证明意味着需要 $\mathcal{P}\neq \mathcal{NP}$。（😵）因此，比起简单地假设给定的方案是正确的，更好的策略是假设某个低层次难题很难解决，然后证明基于这个假设构造的构造的方案是安全的。

掌握窃听不可区分安全两种定义等价性

这里的方案均考虑的对称加密体制

• 不可区分安全 EAV-secure

  （窃听不可区分实验）$\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n)$：

  1. 给定输入 $1^{n}$ 给敌手 $\mathcal{A}$， $\mathcal{A}$ 输出一对长度相等的消息 $m_{0}, m_{1}$；
  2. 由 $\text{Gen}(1^n)$ 产生一个随机密钥 $k$，并且从 $\left\{0,1\right\}$ 中随机选择一个比特 $b$。然后，一个挑战密文 $c\leftarrow \text{Enc}_k(m_b)$ 被计算出来并交给 $\mathcal{A}$；
  3. $\mathcal{A}$ 输出一个比特 $b'$；
  4. 如果 $b'=b$，定义实验输出为 1，否则为 0。当 $\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n)=1$ 时，称 $\mathcal{A}$ 成功。

• 定义1：

  • 说明了 $\mathcal{A}$ 不能判断哪一个明文被加密的概率明显大于随机猜测成功的概率

  （窃听不可区分安全定义 1）如果对于所有的 PPT 敌手 $\mathcal{A}$，存在一个可忽略函数 $negl$ 使得：

  $|\Pr{[\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n)=1]}|\leq \frac{1}{2} + negl(n)$

  则称该方案存在不可区分性。

• 定义2：定义 3.9

  • 说明了 $\mathcal{A}$ 无法判断实验是在 $\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n,0)$ 还是 $\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n,1)$ 中运行。

  （扩展窃听不可区分实验的符号定义）$\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n,b)$，是指使用了一个固定比特 $b$ 而非随机选择的窃听不可区分实验。$output(\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n,b))$ 表示 $\mathcal{A}$ 在 $\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n,b)$ 中的输出比特 $b'$。

  （不可区分安全定义 2）如果对于所有的 PPT 敌手 $\mathcal{A}$，存在一个可忽略函数 $negl$ 使得：

  $|\Pr{[output(\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n,0))=1]}-\Pr{[output(\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n,1))=1]}|\leq negl(n)$

  则称该方案存在不可区分性。

• 等价性：不可区分安全定义 1 和不可区分安全定义 2 等价，具体的证明可见英文版习题 3.4

CPA 安全、CCA安全

• CPA（选择密文攻击）安全

  • 任何确定加密方案都不能抵御选择密文攻击。任何 CPA 安全的加密方案必须是概率性的，即必须将随机性作为加密过程中的一部分来确保相同消息的加密可能是不同的。

  （CPA 不可区分实验）$\text{PrivK}^{cpa}_{\mathcal{A},\Pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 生成密钥 $k$；
  2. 输入 $1^n$ 给敌手 $\mathcal{A}$，敌手 $\mathcal{A}$ 可以访问预言机 $\text{Enc}_k(\cdot)$，输出一对长度相等的消息 $m_0,m_1$；
  3. 从 $\left\{0,1\right\}$ 中随机选择一个比特 $b$。然后，一个挑战密文 $c\leftarrow \text{Enc}_k(m_b)$ 被计算出来并交给 $\mathcal{A}$；
  4. 敌手 $\mathcal{A}$ 继续访问预言机 $\text{Enc}_k(\cdot)$，输出一个比特 $b'$；
  5. 如果 $b'=b$，定义实验输出为 1，否则为 0。当 $\text{PrivK}^{cpa}_{\mathcal{A},\Pi}(n)=1$ 时，称 $\mathcal{A}$ 成功。

  （选择明文攻击条件下的不可区分）如果对于所有的 PPT 敌手 $\mathcal{A}$，存在一个可忽略函数 $negl$ 使得：

  $|\Pr{[\text{PrivK}^{cpa}_{\mathcal{A},\Pi}(n)=1]}|\leq \frac{1}{2} + negl(n)$

  则称该方案存在不可区分性。

• CCA（选择密文攻击） 安全

  （CCA 不可区分实验）$\text{PrivK}^{cca}_{\mathcal{A},\Pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 生成密钥 $k$；
  2. 输入 $1^n$ 给敌手 $\mathcal{A}$，敌手 $\mathcal{A}$ 可以访问预言机 $\text{Enc}_k(\cdot)$ 和 $\text{Dec}_k(\cdot)$，输出一对长度相等的消息 $m_0,m_1$；
  3. 从 $\left\{0,1\right\}$ 中随机选择一个比特 $b$。然后，一个挑战密文 $c\leftarrow \text{Enc}_k(m_b)$ 被计算出来并交给 $\mathcal{A}$；
  4. 敌手 $\mathcal{A}$ 继续访问预言机 $\text{Enc}_k(\cdot)$ 和 $\text{Dec}_k(\cdot)$（但是不允许用挑战密文本身来询问 $\text{Dec}_k(\cdot)$），输出一个比特 $b'$；
  5. 如果 $b'=b$，定义实验输出为 1，否则为 0。当 $\text{PrivK}^{cca}_{\mathcal{A},\Pi}(n)=1$ 时，称 $\mathcal{A}$ 成功。

  （选择密文攻击条件下的不可区分）如果对于所有的 PPT 敌手 $\mathcal{A}$，存在一个可忽略函数 $negl$ 使得：

  $|\Pr{[\text{PrivK}^{cca}_{\mathcal{A},\Pi}(n)=1]}|\leq \frac{1}{2} + negl(n)$

  则称该方案存在不可区分性。

掌握伪随机生成器和伪随机函数的概念、安全性

• 伪随机性：一个伪随机的字符串是多项式时间内均匀分布的字符串。
  • 是真随机性在计算上的松弛。
  • 没有固定的字符串能够被认为是“伪随机的”，伪随机性指的是字符串的分布。
  • 这样，就实现了短密钥（相对短的随机种子）加密一个长消息（长的伪随机字符串）
• 伪随机生成器：

  （伪随机生成器）令 $l(\cdot)$ 为多项式，令 $G$ 为多项式时间算法，该算法满足：对于任何输入 $s\in \left\{0,1\right\}^n$，算法 $G$ 输出一个长度为 $l(n)$ 的字符串。如果满足下面两个条件，则称 $G$ 是一个伪随机生成器：

  1. （扩展性）对于每个 $n$ 来说，满足 $l(n) > n$。
  2. （伪随机性）对所有 PPT 的区分器 $D$ 来说，存在一个可忽略函数 $negl$，满足

  $|\Pr{[D(r)=1]}-\Pr{[D(G(s))=1]}|\leq negl(n)$

  • 其中，$r$ 是从 $\left\{0,1\right\}^l(n)$ 中均匀随机选择，种子 $s$ 是从 $\left\{0,1\right\}^n$ 中均匀随机选择的。
  • 函数 $l(\cdot)$ 被称为 $G$ 的扩展系数。
• 伪随机函数：
  • 从伪随机生成器的字符串分布的随机性，扩展到函数分布的随机性
  • 这里的区分器 $D$ 事实上已经涉及到 Random Oracle，为了方便理解，这里先不做展开

  （伪随机函数）令 $F:\{0,1\}^{*} \times\{0,1\}^{*} \rightarrow\{0,1\}^{*}$ 是有效的、长度保留的、带密钥的函数。如果对所有多项式时间区分器 $D$，存在一个可忽略函数 $negl$，满足：

  $|\Pr{[D^{F_k(\cdot)}(1^n)=1]}-\Pr{[D^{f(\cdot)}(1^n)=1]}|\leq negl(n)$

  则称 $F$ 是一个伪随机函数。

  • $k$ 是从 $\left\{0,1\right\}^n$ 中均匀随机选择的。
  • $f$ 是从将 $n$ 比特字符串映射到 $n$ 比特字符串的函数集合中中均匀随机选择的。

掌握如何构造CPA安全加密方案

• 从任意伪随机函数构造 CPA 安全的加密方案
  • 直接使用 $F_k(m)$ 是不行的，因为 $\text{Enc}_k(\cdot)=F_k(\cot)$ 是一个确定的函数。因此，需要概率性构造——思路是利用伪随机填充 $F_k(r)$ 模仿一次一密

  （构造方法）令 $F$ 是伪随机函数，定义一个消息长度为 $n$ 的对称密钥加密方案如下：

  • $\text{Gen}$：输入 $1^n$，均匀随机地选择 $k\leftarrow \left\{0,1\right\}^n$，并将其作为密钥输出。
  • $\text{Enc}$：输入一个密钥 $k\in \left\{0,1\right\}^n$ 以及一个消息 $m\in \left\{0,1\right\}^n$，均匀随机地选择 $r\leftarrow \left\{0,1\right\}^n$，并输出密文

  $c:=\left\langle r, F_{k}(r) \oplus m\right\rangle$

  • $text{Dec}$: 输入一个密钥 $k \in\{0,1\}^{n}$，以及一个密文 $c=\langle r, s\rangle$，输出明文消息 $m:=F_{k}(r) \oplus s_{\circ}$

理解 CBC 模式、CTR 模式、 理解 Padding Oracle 攻击

• CBC 模式

  • 由公式 $c_i:=F_k(c_{i-1}\oplus m_i), c_0:=IV$ 得到密文 $\langle c_0, c_1, \cdots, c_l \rangle$
  • 从公式上来看，如果 $F$ 为伪随机置换，那么 CBC 加密模式是 CPA 安全的
    • 同理，OFB 模式也是 CPA 安全的
  • $IV$ 必须是随机的，如果仅仅是 $IV += 1$，是不安全的。

• CTR 模式

  • 由公式 $r_i:=F_k(ctr + i), c_i:=r_i \oplus m_I$ 得到密文 $\langle c_0, c_1, \cdots, c_l \rangle$
  • 和 OFB 模式一样，对解密不要求 $F$ 可逆，甚至不要求是置换
  • 从公式上来看，如果 $F$ 为伪随机置换，那么 CTR 加密模式也是 CPA 安全的

尽管流密码更有效，但是在实践中，分组密码不仅更好理解，而且可以防止因为乱用导致的不安全问题（例如相同的伪随机序列被使用两次）。因此，推荐使用分组密码。

• Padding Oracle 攻击
  • CBC 模式对密码块链接进行解密需要先解密所有密文组，再验证填充，随后移除填充，最后再返回解密后的明文信息。
  • 若服务器返回**“填充无效”信息**而非“解密失败”错误，则攻击者可利用服务器本身进行密文填塞来解密（或加密）信息。
  • 攻击方式：
    1. 假设攻击者拥有密文块 $C_1,C_2$，且欲解密 $C_2$ 得到明文块 $P_2$。攻击者可以更改 $C_1$ 的最后一个字节，得到 $C_1'$，此时块 $P_2$ 中的对应字节也会被修改。
    2. 攻击者发送 $(IV, C_1'',C_2)$ 至服务器，服务器随后将返回最后一个解密块的填充是否正确（是否等于 $0x01$）
    3. 如果填充正确，攻击者则能确定 $D_K(C_i)\oplus C_1'$ 的最后一个字节是 $0x01$，即 $D_K(C_2)=C_1'\oplus 0x01$。
    4. 如果填充不正确，攻击者则可以将 $C_1'$ 的最后一个字节更改为下一个可能的值。在最糟糕的情况下，需要 $2^8$ 次来确定最后一个字节。
    5. 在确定了 $P_2$ 的最后一个字节后，攻击者可以使用相同的手段来获取倒数第二个字节。

第四章：消息认证码

掌握MAC定义、安全性

• 定义：定义4.1

  （MAC 定义）消息认证码是一个 PPT 算法的三元组 $(\text{Gen},\text{Mac},\text{Vrfy})$，满足：

  1. 密钥生成算法 $\text{Gen}$：输入参数 $1^n$，输出长度不小于 $n$ 的密钥 $k$。
  2. 标记生成算法 $\text{Mac}$：输入密钥 $k$ 和消息 $m\in \left\{0,1\right\}^*$，输出标记 $t \leftarrow \text{Mac}_k(m)$。该算法具有随机性。
  3. 校验算法：输入密钥 $k$、消息 $m$ 和标记 $t$，输出比特位 $b:=\text{Vrfy}_k(m,t)$，其中 $b = 1$ 表示有效，$b = 0$ 表示无效。
  • 规范验证：对于确定性消息身份验证代码（即 $\text{Mac}$ 是确定性算法），执行验证的规范方法是简单地重新计算标签并检查相等性。换句话说， $text{Vrfy}_k(m,t)$ 首先计算 $t':= \text{Gen}_k(m)$ 然后当且仅当 $t' = t$ 时输出 1。
    • 然而，即使对于确定性 MAC，定义单独的 $\text{Vrfy}$ 算法也很有用，以便明确区分验证消息的语义与验证其真实性。

• 安全性：

  （消息识别码实验/适应性选择消息攻击）$\text{Mac-forge}_{\mathcal{A},\Pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 生成密钥 $k$；
  2. 输入 $1^n$ 给敌手 $\mathcal{A}$，敌手 $\mathcal{A}$ 可以访问预言机 $\text{Mac}_k(\cdot)$，输出一对 $(m, t)$ 的值，并用 $\mathcal{Q}$ 表示所有 $\mathcal{A}$ 对预言机的询问集合；
  3. 当且仅当 $\text{Vrfy}(m, t) = 1, m\notin \mathcal{Q}$ 时，$\text{Mac-forge}_{\mathcal{A},\Pi}(n) = 1$；

  （消息识别码安全性）一个消息识别码 $\Pi = (\text{Gen},\text{Mac},\text{Vrfy})$，如果对所有多项式时间敌手 $\mathcal{A}$ 存在一个可忽略函数 $negl$， 满足

  $|\Pr{[\text{Mac-forge}_{\mathcal{A},\Pi}(n) = 1]}|\leq negl(n)$

  则该消息识别码是适应性选择消息攻击下安全的。

  • strong MAC：安全消息识别码保证了敌手不能对新的消息 $m$ 伪造有效的标记 $t$，但并未限制敌手不能对已验证过的 $m_i$ 伪造有效的标记 t^'。因此，我们将消息识别码实验 $\text{Mac-forge}$ 扩展为强消息识别码实验 $\text{Mac-sforge}$。

    • $\text{Mac-sforge}$ 的变化：将 $\mathcal{Q}$ 由询问集合变成了询问集合及其相关的回应。即：如果 $\mathcal{A}$ 查询 $\text{Mac}_k(m)$ ，收到标记 $t$，则 $(m, t)\in \mathcal{Q}$。 当且仅当 $\text{Vrfy}(m, t) = 1, (m, t)\notin \mathcal{Q}$ 时，$\text{Mac-sforge}_{\mathcal{A},\Pi}(n) = 1$；

      （消息识别码强安全性）一个消息识别码 $\Pi = (\text{Gen},\text{Mac},\text{Vrfy})$，如果对所有多项式时间敌手 $\mathcal{A}$ 存在一个可忽略函数 $negl$， 满足

      $|\Pr{[\text{Mac-sforge}_{\mathcal{A},\Pi}(n) = 1]}|\leq negl(n)$

      则该消息识别码是适应性选择消息攻击下强安全的。

      （从安全到强安全）如果 $\Pi = (\text{Gen},\text{Mac},\text{Vrfy})$ 是使用规范验证的安全消息识别码，那么它也是强安全的。

掌握CBC-MAC，以及安全性

• 构造

  （构造方法）令 $F$ 是一个伪随机函数，固定的长度函数 $l$。基本的 CBC-MAC 构造如下：

  • $\text{Gen}$：输入 $1^n$，均匀选择 $k\leftarrow \left\{0, 1\right\}^n$；
  • $\text{Mac}$：输入密钥 $k$ 和长度为 $l(n)\cdot n$ 的消息 $m$，进行：
    1. 将 $m$ 分块为 $m_1, \cdots, m_l，每个 $m_i$ 的长度为 $n$，并令 $t_0 := 0 ^n$；
    2. 对 $i = 1, \cdots,l$，令 $t_i = F_k(t_{i - 1} \oplus m_i)$；
    3. 输出 $t_i$ 作为标记。
  • $\text{Vrfy}$：输入密钥 $k\in \left\{0, 1\right\}^n$、长度为 $l(n)\cdot n$ 的消息 $m$ 和 长度为 $n$ 的标记 $t$，当且仅当 $t=\text{Mac}_k(m)$ 时，输出 1。

• 安全性

  （CBC-MAC 的安全性）令 $l$ 是一个多项式。如果 $F$ 是一个伪随机函数，那么上述构造方法就是一个长度为 $l(n)\cdot n$ 消息的定长 MAC。该 MAC 是适应性选择消息攻击下安全的。

第五章：杂凑函数

掌握杂凑函数的安全性，包括Preimage Resistance、 Second preimage resistance、collision resistance 定义以及三者之间的关系

• 碰撞

  （碰撞发现实验）$\text{Hash-coll}_{\mathcal{A},\ pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 生成密钥 $s$；
  2. 敌手输入 $s$ 并输出 $x$ 和 $x'$；
  3. 当且仅当 $x \neq x'$ 且 $H^s(x) = H^s(x')$ 时，实验的输出被定义为 1.这种情况下，称 $\mathcal{A}$ 发现了一个碰撞。

  （抗碰撞定义）对散列函数 $\Pi=(\text{Gen}, H)$，如果对于所有的概率多项式时间敌手 $\mathcal{A}$，存在着一个可忽略的函数 $negl$，满足

  $|\Pr{[\text{Hash-coll}_{\mathcal{A},\ pi}(n) = 1]}|\leq negl(n)$

  则该散列函数是抗碰撞的。

• 抗原像的非公式化定义

  • 抗原像：如果给定输入 $s$ 和 $y = H^s(x)$，对概率多项式时间的敌手来说，能够找到一个 $x'$ 使得 $H^s(x') = y$ 是不可行的，就称该散列函数的抗原像的。
  • 抗第二原像：如果给定输入 $s$ 和 $x$，对于概率多项式时间的敌手来说，找到 $x \neq x'$ 满足 $H^s(x') = H^s(x)$ 是不可行的，就称该散列函数的抗第二原像的。

• 三者的关系

  • 任何抗碰撞的散列函数都是抗二次原像的
  • 任何抗二次原像的散列函数不一定是抗原像的。
    • 一个非常好的抗二次原像但是不抗原像的例子：Pre-image resistant but not 2nd pre-image resistant?——Reid 's Answer

掌握随机预言模型以及如何在ROM下设计密码方案

（完美的哈希函数）

• 定义：随机预言机是一部预言机，对任何输入都回传一个真正均匀随机的输出，不过对相同的输入，该预言机每次都会用同一方法输出。
• 性质
  1. 均匀分布：预言机的输出在取值空间内均匀分布，无碰撞
  2. 一致性：相同的输入必有相同的输出
  3. 可计算性：输入的计算可在多项式时间内完成
• 设计密码方案
  • 利用随机语言模型构建伪随机函数 $F_{k}(x) \stackrel{\text { def }}{=} H(k \| x)$

第九章：密码学难题

• 掌握DL、CDH、DDH难题/假设，及相互关系

  • DL

    • 通俗理解：给定 $\mathbb{G}, g$ 和 $h = g^a$，寻找 $a$。
    • 公式化定义：

    （离散对数实验） $\text{Dlog}_{\mathcal{A}, \mathcal{G}}(n)$：

    1. 运行 $\mathcal{G}\left(1^{n}\right)$ 而得到 $(\mathbb{G}, q, g)$，其中 $\mathbb{G}$ 是一个阶为 $q$ 的循环群 $(\|q\|=n), g$ 为 $\mathbb{G}$ 的一个生 成元。
    2. 选择 $h \leftarrow \mathbb{G}$ (可以通过选择 $x^{\prime} \leftarrow \mathbb{Z}_{q}$，并且设置 $h:=g^{x^{\prime}}$ 来完成)。
    3. $\mathcal{A}$ 给定 $\mathbb{G}, q, g, h$，输出 $x \in \mathbb{Z}_{q}$ 。
    4. 如果 $g^{x}=h$，定义实验输出为 1,其他情况下输出为 0。

    （离散对数问题定义）如果对于任意概率多项式算法 $\mathcal{A}$，存在一个可忽略函数negl满足

    $\Pr{[\text{DLog}_{\mathcal{A}, \mathcal{G}}(n)=1]} \leq negl(n)$

    则离散对数问题与 $\mathcal{G}$ 相关是困难的。

  • CDH

    • 通俗理解：给定 $\mathbb{G}, g,g^a,g^b$，寻找 $g^{ab}$。
    • 公式化定义：

    选定循环群 $\mathbb{G}$，以及一个生成元 $g \in \mathbb{G}$。给定两个元素 $h_1$ 和 $h_2$，定义 $\text{DH}_g(h_1,h_2) \stackrel{\text { def }}{=} g^{\log_g{h_1}\cdot\log_g{h_2}}$。
    即，当 $h_1=g^x,h_2=g^y$ 时，$\text{DH}_g(h_1,h_2) \stackrel{\text { def }}{=} g^{\log_g{h_1}\cdot\log_g{h_2}} = g^{xy} = h_1^y = h_2^x$。
    （计算 Diffie-Hellman 问题定义）当随机选定 $h_1$ 和 $h_2$ 时计算出 $\text{DH}_g(h_1,h_2)$。

  • DDH

    • 通俗理解：给定 $\mathbb{G}, g, g^{a}, g^{b}$ 和 $T_{x}$。令 $T_{0}$ 是 $\mathbb{G}$ 中随机的一个元素, $T_{1}=g^{a b}$。同时 $x$ 被随机均匀的从 $\left\{0,1\right\}$ 中选择，令敌手找出 $x$。
    • 公式化定义：

    （决策性 Diffie-Hellman 问题定义）如果对任意概率多项式时间算法 $\mathcal{A}$ 存在一个可忽略函数negl, 满足

    $|\Pr{[\mathcal{A}(\mathbb{G}, q, g, g^{x}, g^{y}, g^{z})=1]}-\Pr{[\mathcal{A}(\mathbb{G}, q, g, g^{x}, g^{y}, g^{x y})=1]}| \leqslant negl(n)$

    则 $\text{DDH}$ 与 $\mathcal{G}$ 相关是困难的。
    概率来源于实验中 $\mathcal{G}\left(1^{n}\right)$ 的输出 $(\mathbb{G}, q, g)$，以及随机选择的 $x, y, z \in \mathbb{Z}_{q}$。

  • 强度：DL>CDH>DDH

第十一章：公钥加密

掌握PKE安全定义、CPA安全和CCA安全

• PKE 安全

  （窃听不可区分实验）$\text{PubK}^{eav}_{\mathcal{A},\Pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 生成密钥 $(pk, sk)$；
  2. 输入 $pk$ 给敌手 $\mathcal{A}$，输出一对长度相等的消息 $m_0,m_1$；
  3. 从 $\left\{0,1\right\}$ 中随机选择一个比特 $b$。然后，一个挑战密文 $c\leftarrow \text{Enc}_{pk}(m_b)$ 被计算出来并交给 $\mathcal{A}$；
  4. 敌手输出一个比特 $b'$；
  5. 如果 $b'=b$，定义实验输出为 1，否则为 0。

  （公钥体制的窃听不可区分定义）如果对于所有的 PPT 敌手 $\mathcal{A}$，存在一个可忽略函数 $negl$ 使得：

  $|\Pr{[\text{PubK}^{eav}_{\mathcal{A},\Pi}(n)=1]}|\leq \frac{1}{2} + negl(n)$

  则称该公钥加密方案存在不可区分性。

• CPA 安全

  （CPA 不可区分实验）$\text{PubK}^{cpa}_{\mathcal{A},\Pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 生成密钥 $(pk, sk)$；
  2. 输入 $pk$ 给敌手 $\mathcal{A}$，敌手 $\mathcal{A}$ 可以访问预言机 $\text{Enc}_{pk}(\cdot)$，输出一对长度相等的消息 $m_0,m_1$；
  3. 从 $\left\{0,1\right\}$ 中随机选择一个比特 $b$。然后，一个挑战密文 $c\leftarrow \text{Enc}_{pk}(m_b)$ 被计算出来并交给 $\mathcal{A}$；
  4. 敌手 $\mathcal{A}$ 继续访问预言机 $\text{Enc}_{pk}(\cdot)$，输出一个比特 $b'$；
  5. 如果 $b'=b$，定义实验输出为 1，否则为 0。

  （公钥体制选择明文攻击条件下的不可区分定义）如果对于所有的 PPT 敌手 $\mathcal{A}$，存在一个可忽略函数 $negl$ 使得：

  $|\Pr{[\text{PubK}^{cpa}_{\mathcal{A},\Pi}(n)=1]}|\leq \frac{1}{2} + negl(n)$

  则称该公钥加密方案存在不可区分性。

• CCA 安全

  （CCA 不可区分实验）$\text{PubK}^{cca}_{\mathcal{A},\Pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 生成密钥 $(pk, sk)$；
  2. 输入 $pk$ 给敌手 $\mathcal{A}$，敌手 $\mathcal{A}$ 可以访问预言机 $\text{Dec}(\cdot)$，输出一对长度相等的消息 $m_0,m_1$；
  3. 从 $\left\{0,1\right\}$ 中随机选择一个比特 $b$。然后，一个挑战密文 $c\leftarrow \text{Enc}_{pk}(m_b)$ 被计算出来并交给 $\mathcal{A}$；
  4. 敌手 $\mathcal{A}$ 继续访问解密预言机（但是不能问询挑战密文本身），输出一个比特 $b'$；
  5. 如果 $b'=b$，定义实验输出为 1，否则为 0。

  （公钥体制选择密文攻击条件下的不可区分定义）如果对于所有的 PPT 敌手 $\mathcal{A}$，存在一个可忽略函数 $negl$ 使得：

  $|\Pr{[\text{PubK}^{cca}_{\mathcal{A},\Pi}(n)=1]}|\leq \frac{1}{2} + negl(n)$

  则称该公钥加密方案存在不可区分性。

掌握单比特CPA安全和多比特CPA安全等价证明

• 证明较为复杂，可以参见《Introduction To Modern Cryptography》（Second Edition）P.382 的 THEOREM 11.6 的证明

理解Hybrid Encryption的原理

• 公钥加密方案是 CPA 安全的，私钥加密方案是 EAV 安全的，那么混合加密方案是CPA 安全的公钥加密方案

  （混合加密方案的构造方法）
  令 $\Pi=(\text{Gen}, \text{Enc}, \text{Dec})$ 为一个公钥加密方案, $\Pi^{\prime}=(\text{Gen}^{\prime}, \text{Enc}^{\prime}, \text{Dec}^{\prime})$ 为一个对称密 钥加密方案, 构造一个公钥加密方案 $\Pi^{\text{hy}}=(\text{Gen}^{\text{hy}}, \text{Enc}^{\text{hy}}, \text{Dec}^{\text{hy}})$ 如下:

  • $\text{Gen}^{\text{hy}}$：输入 $1^n$ 执行 $\text{Gen}1^n$，并输出公钥和私钥 $(pk, sk)$。
  • $\text{Enc}^{\text{hy}}$：输入公钥 $pk$ 和消息 $m \in \left\{0, 1\right\} ^ *$，执行以下操作
    1. 随机选择 $k \leftarrow\{0,1\}^{n}$。
    2. 计算出 $c_{1} \leftarrow \text{Enc}_{p k}(k)$ 和 $c_{2} \leftarrow \text{Enc}_{k}^{\prime}(m)$。
    3. 输出密文 $\left(c_{1}, c_{2}\right\rangle$。
  • $text{Dec}^{\mathrm{hy}}$：输入私钥 $sk$ 和密文 $\left\langle c_{1}, c_{2}\right\rangle$，执行以下操作
    1. 计算 $k:=\text{Dec}_{s k}\left(c_{1}\right)$。
    2. 输出消息 $m:=\text{Dec}_{k}^{\prime}\left(c_{2}\right)$

掌握El Gamal加密的原理和为何不是CCA安全

• EI Gamal

  （El Gamel 方案的构造方法）
  定义如下的公钥加密方案:

  • Gen: 输入 $1^{n}$，执行 $\mathcal{G}\left(1^{n}\right)$ 来获得 $(\mathbb{G}, q, g)$。然后选择随机的 $x \leftarrow \mathbb{Z}_{q}$ 并且计算 $h:=g^{x}$。公钥是 $(\mathbb{G}, q, g, h)$，私钥是 $(\mathbb{G}, q, g, x)$。
  • Enc: 输入公钥 $pk=(\mathbb{G}, q, g, h)$ 和消息 $m \in \mathbb{G}$，选择随机的 $y \leftarrow \mathbb{Z}_{q}$，并且输出密文 $\left\langle g^{y}, h^{y} \cdot m\right\rangle$。
  • Dec: 输入私钥 $sk=(\mathbb{G}, q, g, x)$ 和密文 $\left\langle c_{1}, c_{2}\right\rangle = \left\langle g^{y}, h^{y} \cdot m\right\rangle$，输出 $m=c_{2} / c_{1}^{x}$。

• 安全性

  如果 $\text{DDH}$ 问题相对于 $\mathcal{G}$ 来说是困难的, 则 El Gamal 加密方案在选择明文攻击情况下有不可区分的加密。

  • 上述定理的证明需要使用规约

• 为何不是 CCA 安全

  • 例如敌手 $\mathcal{A}$ 拦截了使用公钥 $pk= \langle\mathbb{G}, q, g, h\rangle$ 加密消息 $m$ 的密文 $c=\left\langle c_{1}, c_{2}\right\rangle = = \left\langle g^{y}, h^{y} \cdot m\right\rangle$。如果敌手计算 $c_2':=c_2\cdot m'$，则很容易找到密文 $c^{\prime}=\left\langle c_{1}, c_{2}^{\prime}\right\rangle$ 是消息 $m \cdot m^{\prime}$ 的密文。这导致了选择密文攻击的可能。
  • 教科书式的 RSA 同样不是 CCA 安全

第十二章：电子签名

掌握签名安全定义

• 数字签名

  （数字签名定义）一个数字签名方案是由 PPT 算法组成的三元组 $(\text{Gen},\ text{Sign},\text{Vrfy})$，满足下列条件：

  1. $\text{Gen}$：以 $1^n$ 作为输入，输出一对密钥 $(pk, sk)$，分别称为公钥和私钥。
  2. $\text{Sign}$：以私钥 $sk$ 和消息 $m \in \left\{0, 1\right\}^*$ 作为输入。输出一个签名 $\sigma \leftarrow \text{Sign}_{sk}(m)$。
  3. $\text{Vrfy}$：以一个公钥 $pk$、消息 $m$ 和一个签名 $\sigma$ 作为输入，输出一位 $b:=\text{Vrfy}_{pk}(m, \sigma)$。当 $b = 1$ 时表示签名有效。

  • 该方案需要对任意 $n$，对于所有由 $\text{Gen}(1^n)$ 输出的 $(pk, sk)$，以及任意 $m\in \left\{0, 1\right\}^*$，必须满足

  $\text{Vrfy}_{pk}(m,\text{Sign}_{pk}(m))=1$

• 数字签名安全

  （数字签名实验） $\text{Sig-forge}_{\mathcal{A},\Pi}(n)$：

  1. 运行 $\text{Gen}(1^n)$ 得到密钥 $(pk, sk)$。
  2. 将 $pk$ 和访问 “签名预言机” $\text{Sign}(\cdot)$ 的权利给敌手 $\mathcal{A}$。然后敌手输出 $(m, \sigma)$。设 $\mathcal{Q}$ 表示为 $\mathcal{A}$ 在执行期间问询签名的消息的集合。
  3. 当且仅当 $\text{Vrfy}_{pk}(m, \sigma) = 1$ 且 $m\neq \mathcal{Q}$ 时，实验输出定义为 1。

  （数字签名安全性）一个签名方案 $\Pi = (\text{Gen},\text{Mac},\text{Vrfy})$，如果对所有多项式时间敌手 $\mathcal{A}$ 存在一个可忽略函数 $negl$， 满足

  $|\Pr{[\text{Sig-forge}_{\mathcal{A},\Pi}(n) = 1]}|\leq negl(n)$

  则该签名方案是适应性选择消息攻击下安全的。

掌握RSA-FDH原理及安全性证明，要掌握归约主要步骤和概率计算

• RSA-FDH 方案

  （构造方法）令 $H$ 是函数，其定义域为 $\left\{0, 1\right\}^*$，值域为 $\mathbb{Z}_N^*$。构造一个签名方案：

  • $\text{Gen}$：输入 $1^n$，运行 $\text{GenRSA}(1 ^ n)$ 来计算 $(N,e,d)$，令 $H$ 的值域为 $\mathbb{Z}_N^*$。公钥为 $\langle N, e\rangle$，私钥为 $\langle N, d\rangle$。
  • $\text{Sign}$：输入一个私钥 $\langle N, d\rangle$ 以及一个消息 $m\in \left\{0,1\right\}^n$，计算 $\sigma:=[H(m)^d\pmod N]$。
  • $\text{Vrfy}$：输入一个公钥 $\langle N, e\rangle$，以及一个消息 $m$ 和一个签名 $\sigma$。当且仅当 $\sigma^{e} \stackrel{?}{=} H(m) \bmod N$ 时， 输出 1。
• 安全性

  如果 RSA 与 GenRSA 相关是困难的，并且 $H$ 为随机预言机，那么么 RSA-FDH 的构造方案是适应性选择消息攻击下存在不可伪造的。