《A Graduate Course in Applied Cryptography》chapter 4 Block ciphers （3）

深藏阁楼爱情的钟 2022-09-03 15:15 17阅读 0赞

原文教材 与 参考资料：

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

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

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

# 4.5 Constructing block ciphers from PRFs #

使用PRFs 构造分组密码，该书此处提出的使用PRF构造分组密码称为Luby-Rackoff 构造，该构造也作为实用分组密码设计的一种判定。

方案描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

输入加密信息（u, v）

使用三个秘钥K1，K2，K3进行变换运算（运算为F，一种安全的PRF运算）

输出加密后的信息（x, y）, 解密方案正好是相反的变换，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

**安全定理：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

对于该分组方案的BC敌手，存在一个PRF敌手，满足上式，从这个等式可以看到，由于首先假设存在安全的PRF所以PRF敌手的优势应是可以忽略的，N的长度是超多项式的，所以后边两项常数项是可以忽略的，那么剩下的就需要证明BC敌手优势小于右边即可，这些安全定理往往是先推出结论再写出整个定理的结果。

证明思路：

使用随机函数替换PRF函数，构造一个新的算法，即为整个新的算法模拟为实验1，原始的方案为实验0，这样就能得到BC敌手攻击游戏（直觉上，有了整个游戏我们就可以继续推导BC敌手的优势，直到完成上述表达式）。

** 安全定理证明：**

定义存在一个BC敌手，构造一个完整的安全游戏，此时敌手最多进行Q次询问，最终的目的是得到BC敌手在该方案下的优势是可以忽略的。首先证明PRF敌手优势是可以忽略的，N此处依然是定义为超多项式的，此处定义敌手A为A0，A0的设定如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

A0最多进行Q次询问，并且不会询问相同的内容，其优势和原始的敌手A是一样的。

构造游戏Game0/1/2/3，这里敌手是一样的，但是不同游戏面临的挑战者是不同的，然后使用Switching 引理得到BC敌手的优势，然后可以证明每两个游戏敌手之差是可以忽略的，最后可以得到Game0 和 Game3 之间的关系，最后能够得到的就是BC敌手优势描述：

![20210809175813777.png][]

Game0/1/2/3游戏描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

Game0 是显然的，就是BC攻击游戏实验0，不存在两个相同的输入（u,v）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

Game 1，将PRF函数改变为三个随机选择的函数，敌手A0不应该察觉出这种替换，此处将三个函数f作为一个整体的函数，然后构造一个新的敌手B\`，B\`可以通过调用A0来实现，得到下述结论：

![20210809200957582.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6][]

Game2 中将函数f2 f3 使用表格构造一个新的实现，这样可以保证f2 和 f3 输出的是一个唯一值，这就实现了一个置换的功能，此时Game2和Game1完全等价，Pr\[W2\] = Pr\[W1\]，亦可以认为Game2为Game1的一种实现。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7][]Game3 和 Game2是完全相同的，唯一不同是Game3删除了X，Y的唯一性检查，为了便于分析，将Game2,3放在统一概率空间下进行运算，如果要将两个游戏放在统一个概率空间下，两个实验最需要统一的就是开始随机函数f1的选择与Xi,Yi的选择，现在定义统一的概率空间如下：

![20210809203324760.png][]

敌手的随机选择此处使用掷硬币的方式，挑战者的随机空间定义为统一的f1, Xi, Yi，此后，Game2/3的概率空间将可以放到同一概率空间下，此时两个游戏的不同就是挑战者给与敌手的回复不同，此处我们还需要明确这些随机选择是互相独立的：

![20210809203938932.png][]

断言1：在Game3中，上述随机值为互相独立的，现在设定掷硬值Coins, 以及f1是固定的，显然Coins 和 f1一定是相互独立的。(u1,v1) 是固定值，那么w1也是固定的（由u1,v1生成w1）。在这个条件概率下Xi，Yi的选择依然是均匀独立分布的，由于后续的值均是由x1,y1计算得到的，所以后续的u2, v2.........都是均匀独立的。

定义Z1事件为wi = wj 在Game3中，Z2事件定义为xi = xj 在Game3中，定义Z = Z1 U Z2。Z只在Game3中定义，因为Game2中xi 和 wi 的计算方式并不相同。如果Z没有发生，那么Game2 和 Game3 是完全相同的。如果Z发生，那么Game2 和 Game3 将会立刻被区分。

![20210809210317638.png][]

断言2的证明，当Z不发生时，Game2 和 Game3 是相同的输出。因为请求（u1,v1）的计算取决于掷硬币Coin，所以u1,v1,x1,y1,w1都有一样的值在这两个游戏中。又因为(u2,v2) 仅仅依赖于Coin和（x1,y1），与之前的断言证明类似这就是一个归纳的推导，u2, v2, w2则也具有相同的输出在游戏中。因为Z不发生，所以就不会产生想用的x和y。因此，对于i = 1,...,Q 这些变量都具有相同的值在这个游戏中。

根据Difference Lemma (Theorem 4.7) 以及断言2，可以得到下式：

![20210809212036860.png][]

此时将Game2 和 Game3 统一在了同一概率空间下：那么到底需要怎样的修改才能把两个游戏统一在同一概率空间下呢？

1. 统一敌手的随机选择与询问输入。

2. 统一挑战者的随机选择与初始变量信息。

3. 两个游戏中不同挑战者的回复信息不需要做任何的修改，即两个游戏还是有区别的。

4. 如果Z发生了，那么将立刻会发现两个游戏的不同，否则这两个函数的输出就是相同的。

![20210809214127987.png][]

此时，Pr\[W3\]  和 Pr\[W2\]得以联系起来小于等于Pr\[Z\]。

进一步，计算Pr\[Z1\], Pr\[Z2\]概率：

![2021080921450275.png][]，![20210809214520316.png][]

由于断言1和2，且敌手并不会进行两次同样的询问，那么在这个概率空间下，我们有：

![20210809220021824.png][]

所以由：

![20210809220152254.png][]

![20210809220320784.png][]

![2021080922040143.png][]

![20210809220531978.png][]

![20210809220822606.png][]

最终得到：![20210809220629761.png][]

#  4.7 The ideal cipher model  #

理想密文模型：

分组密码被使用应用在多种密码学构造中，有时很难说证明一个理论或者方案是安全的在标准的假设下。因此产生了一些启发式的技术，被叫做理想密文模型。在该书之前一直讨论的内容中，将分组的核心变换定义为一种置换，然而每次实验都要随机的生成一种置换，这是一个比较复杂且计算量比较大的过程。所以，基于真实的分组密文构建一种启发式的模型。启发式的理想密文模型仅仅好于没有安全证明，但是并不能保证没有其他专门被设计的攻击存在。

形式化定义：

假设有些密码学协议S使用O(E,D)，更为重要的是S调用O(E,D)算法但是不能看到其内部实现。早这种情况下，定义S将O作为谕言机（oracle）。

我们想要去分析S的安全性，首先定义我们感兴趣的属性X，然后建模为一种由挑战者和敌手组成的游戏。在挑战者给与敌手的请求回复中，挑战者计算多种不同的既定函数，然后要求Oracle运行在特定的时刻。此时这个游戏定义敌手优势为Xadv\[A,S\]，那么意味着敌手对X属性的安全性。

如果我们想要继续分析S在理想密文的安全性，那么攻击游戏将要进行一定的修改，存在敌手和挑战者都能访问的语言机，对于上述分组密码的场景下，就是他们都能够访问一个随机选择的置换Oracle。

具体的游戏修改为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9][]

1. 在游戏开始时，挑战者选择一个随机的置换，对于每一个K。

2. 除了标准的请求，敌手A还可以提交一种理想请求(ideal cipher queries)，这里存在两个类型的请求，一个是置换请求，一个是逆置换请求。

3. 在标准请求中，挑战者使用随机选择的置换Oracle替换原来的E，D加解密算法。

这里理想密文请求使得敌手具备线下评估E和D的计算能力。

**单词表：**

To simplify things a bit： 把事情简化一点

so as to : 为了

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20220829/2c20e24aea3943f9af00373adf22e31a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20220829/5f7e986fa1d944bcb5c5511ec222d116.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20220829/60c1ed984e7b494cb6ee3e46706d5a03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20220829/ed782c22039241648e520864a177897b.png
[20210809175813777.png]: /images/20220829/ca9e24e817554b8fb3a6d482c6578cb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20220829/ca125afbc72c4bc2a099887900e07fe9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20220829/5a55d1a6fcdb41a6a9dfed3f5336ec0e.png
[20210809200957582.png]: /images/20220829/125d1eb9e66b48f78a39ba527fdd06e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6]: /images/20220829/183d22f31d764c9395699e150dba9253.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7]: /images/20220829/903a687c70fb41ddb4668ff5fe2d3edf.png
[20210809203324760.png]: /images/20220829/7cae982b7a4a4cf49169ac08a255c8f2.png
[20210809203938932.png]: /images/20220829/846f9999f5d24738aee8792361180115.png
[20210809210317638.png]: /images/20220829/afcc0c13573647b6bd21f0ec76c5910f.png
[20210809212036860.png]: /images/20220829/7a45ba4052bf4ea2a6778cf8913adb6e.png
[20210809214127987.png]: /images/20220829/bc67c0da0e664af49326cd0cc0d894dc.png
[2021080921450275.png]: https://img-blog.csdnimg.cn/2021080921450275.png
[20210809214520316.png]: /images/20220829/443df904e31f474bb0e43f8deb34b38c.png
[20210809220021824.png]: /images/20220829/02da6d9eef8746a2b8b8de648113ae52.png
[20210809220152254.png]: /images/20220829/ea2d3a824e0d42b3abf4de7791c3915d.png
[20210809220320784.png]: /images/20220829/bed95ff197ae422aa2c21626f24e2a4b.png
[2021080922040143.png]: /images/20220829/0a28c732f1474f3caf5804926ae7f4da.png
[20210809220531978.png]: /images/20220829/c1f07f369f6846f2aa63f3e5f2a4be29.png
[20210809220822606.png]: /images/20220829/dc653d43a8ab471fb15e8041e2c8ee95.png
[20210809220629761.png]: /images/20220829/5c261535780f4e0b9ec344aa70050f30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8]: /images/20220829/af6a291afa8f4c5f816f567c4b362ac0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9]: /images/20220829/ceea4b5333f1477d80e01dda87a9a609.png