可证明安全复习

本文最后更新于:2021年10月5日 中午

  • 之前写过前两章英文版的笔记,现在把这门课的复习大纲整理了一下。
  • 相关的参考教程是《Introduction To Modern Cryptography》,其中文版是《现代密码学——原理与协议》。中文版的翻译一言难尽,尤其是到了后面的规约部分。因此建议还是优先考虑英文版。
  • 前两章的英文笔记可以参见 Introduction To Modern Cryptography

可证明安全

第一章:引言

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

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

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

第二章:完美保密

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

  • 完美保密:

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

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

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

    则该方案是完美保密的。

  • 完美不可区分:

    (窃听不可区分实验)PrivKA,Πeav\text{PrivK}^{eav}_{\mathcal{A},\Pi}

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

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

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

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

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

掌握一次一密的原理

  • 一次一密方案

    (一次一密)

    1. 令整数 l>0l > 0,设明文空间 M\mathcal{M},密钥空间 K\mathcal{K} 和密文空间 C\mathcal{C} 都等于 {0,1}l\left\{0,1\right\}^l(即长度为 ll 的二进制比特串的集合);
    2. 密钥产生算法 Gen\text{Gen}k={0,1}lk=\left\{0,1\right\}^l 中依据均匀分布选择一个二进制比特串。;
    3. 加密算法 Enc\text{Enc}:给定一个密钥 k{0,1}lk\in \left\{0,1\right\}^l 和一个明文 m{0,1}lm \in \left\{0,1\right\}^l,输出 c:=kmc:=k\oplus m
    4. 解密算法 Dec\text{Dec}:给定一个密钥 k{0,1}lk\in \left\{0,1\right\}^l 和一个密文 c{0,1}lc \in \left\{0,1\right\}^l,输出 m:=kcm:=k\oplus c
  • 安全性证明

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

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

    1. Gen\text{Gen} 产生的任意密钥 kKk\in \mathcal{K} 的概率都是 1K\frac{1}{|\mathcal{K}|}
    2. 对任意明文 mMm \in \mathcal{M} 和任意密文 cCc\in \mathcal{C},只存在唯一的密钥 kKk\in \mathcal{K} 使得 Enck(m)Enc_k(m) 输出 cc

掌握一次一密的优缺点

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

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

第三章:单钥加密

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

  • 具体方法 Concrete Approach

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

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

  • 渐进方法 Asymptotic Approach

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

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

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

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

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

  • 不可区分安全 EAV-secure

    (窃听不可区分实验)PrivKA,Πeav(n)\text{PrivK}^{eav}_{\mathcal{A},\Pi}(n)

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

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

    (窃听不可区分安全定义 1)如果对于所有的 PPT 敌手 A\mathcal{A},存在一个可忽略函数 neglnegl 使得:

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

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

  • 定义2:定义 3.9

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

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

    (不可区分安全定义 2)如果对于所有的 PPT 敌手 A\mathcal{A},存在一个可忽略函数 neglnegl 使得:

    Pr[output(PrivKA,Πeav(n,0))=1]Pr[output(PrivKA,Πeav(n,1))=1]negl(n)|\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 不可区分实验)PrivKA,Πcpa(n)\text{PrivK}^{cpa}_{\mathcal{A},\Pi}(n)

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

    (选择明文攻击条件下的不可区分)如果对于所有的 PPT 敌手 A\mathcal{A},存在一个可忽略函数 neglnegl 使得:

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

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

  • CCA(选择密文攻击) 安全

    (CCA 不可区分实验)PrivKA,Πcca(n)\text{PrivK}^{cca}_{\mathcal{A},\Pi}(n)

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

    (选择密文攻击条件下的不可区分)如果对于所有的 PPT 敌手 A\mathcal{A},存在一个可忽略函数 neglnegl 使得:

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

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

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

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

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

    1. (扩展性)对于每个 nn 来说,满足 l(n)>nl(n) > n
    2. (伪随机性)对所有 PPT 的区分器 DD 来说,存在一个可忽略函数 neglnegl,满足

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

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

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

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

    则称 FF 是一个伪随机函数。

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

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

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

    (构造方法)令 FF 是伪随机函数,定义一个消息长度为 nn 的对称密钥加密方案如下:

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

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

    • textDetext{De}c: 输入一个密钥 k{0,1}nk \in\{0,1\}^{n}, 以及一个密文 c=r,sc=\langle r, s\rangle, 输出明文消息 m:=Fk(r)sm:=F_{k}(r) \oplus s_{\circ}

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

  • CBC 模式

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

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

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

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

第四章:消息认证码

  • 掌握MAC定义、安全性

    • 定义:定义4.1

    • 安全性:定义4.2

      • strong MAC:PROPOSITION 4.4

  • 掌握CBC-MAC,以及安全性

    • 定义:CONSTRUCTION 4.11

    • 安全性

第五章:杂凑函数

  • 掌握杂凑函数的安全性,包括Preimage Resistance、 Second preimage resistance、collision resistance, 安全定义以及三者之间的关系
    • 公式化定义和三者的关系见习题 5.1
      • 抗碰撞性包含了次原像抗性,但无法保证原像抗性。相反,次原像攻击包含碰撞攻击
  • 掌握随机预言模型以及如何在ROM下设计密码方案
    • 定义:随机预言机是一部预言机,对任何输入都回传一个真正均匀随机的输出,不过对相同的输入,该预言机每次都会用同一方法输出。
    • 性质
      1. 均匀分布:If x has not been queried to H, then the value of H(x) is uniform.
        • 均匀分布性:预言机的输出在取值空间内均匀分布,无碰撞
    • 设计密码方案:P178-P179

第九章:密码学难题

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

    • DL

    • CDH

    • DDH

    • DL>CDH>DDH

第十一章:公钥加密

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

    • PKE 安全

    • CPA 安全

    • CCA 安全

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

    • P382 的 THEOREM 11.6 的证明,可以参考 P385
  • 理解Hybrid Encryption的原理

    • 其中公钥加密方案是CPA安全的,私钥加密方案是窃听者存在安全的,那么混合加密方案是CPA安全的公钥加密方案

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

    • EI Gamal

    • 安全性

    • 为何不是CCA安全

    ![](D:\WorkspaceFolder\可证明安全技术\img\EIGamal 为什么不是CCA.png)

第十二章:电子签名

  • 掌握签名安全定义

    • 数字签名

    • 数字签名安全

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

    • RSA-FDA 方案

      SignFDHN,d(M)\operatorname{SignFDH}_{N, d}(M)
      yHFDH(M)y \leftarrow H_{F D H}(M)
      return ydmodNy^{d} \bmod N
      Verify FDHN,e(M,x)F D H_{N, e}(M, x) yxemodN;yHFDH(M)y \leftarrow x^{e} \bmod N ; y^{\prime} \leftarrow H_{F D H}(M)
      if y=yy=y^{\prime} then return 1 else return 0 .

    • 安全性证明

      • 课本的标准证明(ROM)

      • CSDN 上的证明

        1. 角色:仿真器 II,攻击者 FF
          仿真器I拥有公钥 (n,e)(n,e) 随机选择 yy,仿真器需要利用攻击者的能力解决RSA求逆问题,即需计算出

        2. 仿真器 II 执行hash询问如下(仿真器将 yy 嵌入到自己的hash询问应答中):

        3. 签名询问如下:

        4. 最后攻击者给出签名挑战(即敌手给出消息 mim_i 的有效签名即 x=h(mi)dx=h(m_i)^d ,这里我们假设敌手已经进行过hash询问即列表中存储的 hi=h(mi)h_i=h(m_i)

        5. 我们假设攻击者已经询问过关于 mim_i 的hash询问(如果没有,则仿真器进行hash询问,敌手只能对挑战的 mim_i 进行hash询问,不能进行签名询问)。即,列表中一定有关于mi的信息 (mi,hi,ri)(m_i,h_i,r_i)
          如果说 mim_i 的hash询问为 hi=yrieh_i=yr_i^e,则 x=hid=yidrix=h_i^d=y_i^d r_i,则 yid=x/riy_i^d =x / r_i.
          假设敌手在执行了 qsq^s 次签名询问后终止,成功伪造签名的概率为 aa,则RSA求逆问题的优势为
          Adv=pqs(1p)aAdv=p^{q^s} (1-p) a,即表示在 qsq^s 次没有失败的签名询问后,敌手以概率 aa伪造签名,且此时以 (1p)(1-p) 的概率对应的是 hi=yrieh_i=yr_i^e

          PS:签名询问过程中之所以要终止的原因是因为仿真器需要保证每一个询问的签名值=hidh_i^d,符合FDH签名约束。

      • 论文的标准证明


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!