《A Graduate Course in Applied Cryptography》chapter 5 Chosen Plaintext Attack

待我称王封你为后i 2022-09-04 03:55 113阅读 0赞

原文教材 与 参考资料：

Boneh Dan , Shoup Victor . A Graduate Course in Applied Cryptography\[J\].

该书项目地址（可以免费获取）：http://toc.cryptobook.us/

博客为对该书的学习笔记，并非原创知识，帮助理解，整理思路。

选择明文安全CPA，我个人理解是从语义安全SS上衍生出来的一种安全模型，故而在深入理解CPA语义安全时应当重新考虑一下语义安全模型。

### **语义安全模型定义：** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

![20210813150707515.png][]

语义安全模型的概念，要实现SS安全，必须保证每次加密的秘钥是随机产生的（极低概率相同），并且多秘钥的SS模型也是安全的。

抵抗多秘钥攻击的SS模型描述如下，证明采用的"多层讨论”技术。

SSmulti-key attack安全模型如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

如上所述，用户使用对称加密算法，针对不同文件使用不同的秘钥进行加密，是可以保证语义安全的，但是这样会导致 大量的秘钥需要保密管理。那是否能够使用同一个秘钥加密所有的文件依然保持安全呢？或者说是在保持一个秘钥的情况下，依然保持安全？

答案是否定的，如果依然使用同一个秘钥那么SS安全必定是不安全的，只要对m1,m0稍作处理，就能够攻破这个SS游戏。

所以，我们需要一个新的安全模型来保持这个新的安全定义，这个新的安全定义就是CPA安全，也称之为语义安全抵抗选择明文攻击，简称CPA安全。

### CPA安全定义： ###

![2021081316583080.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

1. 挑战者选择一个固定的秘钥K。

2. 敌手提交一系列的请求给挑战者，然后挑战者进行加密，并将加密内容发送给敌手。

3. 由敌手输出猜测的比特。

这里需要明确的是，任何的确定性加密都不是CPA安全的，所有CPA安全的加密都是概率加密方案。

### CPA安全方案的构造 ###

CPA安全的构造方案还是比较多的，在该书中，总共提到多种构造方案，这里我们仅仅看一种通过用构造方案。

使用基本的组件：

![20210813172134412.png][]

思路：使用PRF的秘钥作为加密方案E，D的秘钥，方案描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

这里实质上是通过引入每次加密消息的随机数x, 引入了概率的内容，使得即使在秘钥k\`不变的情况下，每次加密不同的消息获得结果也是不同的。

### CPA安全证明 ###

定理：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

对于这种类似通用构造，得到以上的安全定理，可以看到的是，通用构造的安全性需要使用所用组件的安全性来刻画，对于CPA敌手在这个实验中，存在PRF敌手和SS敌手满足上述不等式，这个安全性证明如何来呢？

从安全定理给出的这个式子，我们就可窥见到部分的证明思路，必须将这几个敌手的安全实验整合进CPA安全的实验，从而推导出CPA的优势表达式，即为CPAadv = |Pr\[W0\] - Pr\[W3\]|。

那么，首先构造CPA模型的Game0即为CPA的比特猜测版本优势, 然后继续构造Game1/2/3，最终Game3等同于SS模型的比特猜测版本，即为从CPA安全模型逐步过渡到SS模型，这几个游戏的挑战者是不相同的，然后证明相邻游戏的之间是可以忽略的，又因为原始分组加密是SS安全的，那么对于CPA安全模型的W1事件而言，此时敌手的优势Pr\[W3\] = 1/2。所以CPAadv = |Pr\[W0\] - 1/2|。 Game3 == SS == 1/2 === W3

**Game 0:**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6][]Game 0 就是一个比特猜测版本的CPA游戏，是一个详细的该方案CPA模型描述，式子5.7定义了CPA敌手此时的优势。

接着，我们将Game0中的F替换为一个完全随机的函数f，替换这个步骤的原因应该是为了具体的得到概率计算值，Game1描述如下，Game0 和 Game1这里依然可以理解为不可区分的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7][]

因为引入了PRF这个安全的组件，那么PRF敌手Bf将被作为如下处理，BF敌手此处扮演敌手A的挑战者，然后BF同时与安全PRF挑战者交互，这样就将BF敌手引入到了我们这个CPA安全的模型中，其中BF敌手在本实验中作用描述如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8][]

Game2 中主要是将 f 随机函数实现，使用一个表格对函数的输入、输出进行记录与控制：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9][]通过模拟实现这个随机函数 f 我们可以直接的看到，W1和W2的概率是相同的，因为PRF是安全的，并且这种实现方式是完全可以模拟一个随机函数 f 的，进一步我们删除Game 2 中的检查点功能，得到Game3。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 10][]

接着，这里利用之前说到的Difference lemma , 将Game2 和Game3 整合到同一个概率空间下，那么很容易得到下述公式：

![2021081623283561.png][]

显然，在Game3中，每次使用不同的秘钥加密不同的消息，实质上就是多秘钥攻击实验，那么，我们又可以得到如下：

![20210816233034115.png][]

此时，我们得到了这个CPA证明最为重要且关键的点，如何把MSSadv敌手B与我们的CPA实验关联起来？

最为直接的方式：使用MSS敌手来做CPA敌手的挑战者，由MSS敌手代替CPA敌手向CPA挑战者交互，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 11][]

因此，得到

![20210816233633677.png][]

得证。

单词表：

glean: <vi/t> 拾，收集           devise: 设计

snoop: <vt>  窥探                  follow from: 由...产生

diligently: <adv> 勤奋            scenario: 方案

devastating: <adj/v> 毁灭

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20220829/6583ba83ba104d5d9cb4423f35cf3af6.png
[20210813150707515.png]: /images/20220829/4bd10b46cec047c69d9d8ab78ce0ff79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20220829/ca18c01cf5114854a273caf28ad270bb.png
[2021081316583080.png]: /images/20220829/b47058f3d1954fff837e669a83a5ba78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20220829/0740937a01a74c7ba3339b8980d1817e.png
[20210813172134412.png]: /images/20220829/8b2a83c65ea94b13ad7d483f70cc5f33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210813173020975.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20220829/60db9e8e43f8483289987cc410d0f77e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20220829/650dbee869d2445b811c2adbfc74bf70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6]: /images/20220829/1bc725ecb255409a9ec68f9a5abbcda0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7]: /images/20220829/f840181c5c56411aaa75c421ee2ad5bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8]: /images/20220829/8f27be6a4db94d5db8f7b3fc459a8df6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9]: /images/20220829/7972da7bbe3f40019a51f55dc7a25a24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 10]: /images/20220829/4e5cc49140044c7d8b13944bb61e2fda.png
[2021081623283561.png]: /images/20220829/3dc3f6e65abd44a9b32c59e3ca6b2247.png
[20210816233034115.png]: /images/20220829/d6a7ef85b10e4324a7f6fc5bf1132031.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 11]: /images/20220829/b31fdf4a8cb54ee085fd274039581517.png
[20210816233633677.png]: /images/20220829/fc570465ee954982a76374e444a632c2.png