《A Graduate Coursse in Applied Cryptography》chapter 3 Stream ciphers （2）

淡淡的烟草味﹌ 2023-01-22 01:54 54阅读 0赞

# **《A Graduate Coursse in Applied Cryptography》chapter 3  Stream ciphers （2）** #

原文教材：

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

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

系列博客为对该教材的学习笔记（只包括我认为重要的东西）

### 3.3 Stream cipher limitations: attacks on the one time pad ###

该书的3.3节内容比较简单，只说到了两个部分内容：

第一: two time pad 是不安全的加密协议，很简单类似这种流密码的秘钥不能反复使用。

这种不安全的状况描述如下：

![20210517110748820.png][]

![20210517110808778.png][]

此时，破解m1与m2的异或值是比较简单的。

第二：one time pad 是可延展的。

这种不安全的状况描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

敌手在消息传递过程中进行恶意修改，可能会导致接受方获取到被修改的内容，称之为可延展的。

### 3.4 Composing PRGs ###

该书本节主要讨论了构造PRG的方法。

3.4.1  A parallel  construction

本节主要描述了一种构造随机数生成器的方法，很简单直接将多个PRG并行组合成为一个新的随机数生成器，描述如下：

![20210518111922567.png][]

这种随机数发生器被称为 n-wise parallel composition of G , n宽的并行随机数发生器。

此时，我们证明该构造是安全的，类似之前的思路，首先给出一个安全性定理描述：

![20210518112314892.png][]

如果G是安全的PRG，那么G\`也是安全的。那么，问题来了。如何证明该方案是安全的？使用类似之前提到的办法，我们设计两个实验，

在实验0中，使用所有并行的随机数生成器来生成随机数，在实验1中，使用所有真正的随机数来代替这些伪随机数发生器。思路与本书

Attack Game 3.1 相同。但是，这里又存在一个问题，并行构造的随机数生成器内部是由多个伪随机数生成器构成的，我们无法证明如果有

部分被替换为真随机数，部分没有被替换成随机数的这种情况。

此时，我们将敌手看成是对于整个方案攻击的敌手，如果存在一个敌手A能够攻击成功组合的伪随机数生成器G\`, 那么久存在一个敌手B能够攻击成功一个单独的伪随机数生成器G。

![20210518145345358.png][]

此时我们得到敌手攻击该方案的优势至少为：PRGadv\[A,G\`\] = PRGadv\[B,G\]。即，A攻击G\`的优势至少应该和B攻击G的优势相等。

然而，此时我们还不能知道这样的证明是否合理与正确，进一步分析，从实例化的角度来看，我们假设组合的伪随机数生成器中由两个伪随机数生成器构成。

那么，根据语义安全攻击游戏Game3.1。我们得到两个攻击游戏Game0 和 Game1。

**Game0：**

![20210518150045231.png][]

在Game0中，所有的并行随机数生成器由伪随机数生成器构成,定义p0 为敌手A输出1的概率。

**Game1:**

![2021051815024529.png][]

在Game1中，将其中一个随机数生成器替换为真随机数，首先，我们考虑第一个问题，Game1实验并没有完全替换两个随机数生成器为什么？因为在完全被替换成为随机数之前，

该实验存在一个中间的状态，即为一个为真随机数一个是伪随机数发生器。这种情况，我们也必须考虑到。所以，实验1应该是被用来描述这种中间状态，也称之为"hybrid"实验。直觉上，

如果G是安全的，那么敌手也是无法察觉到有什么不同的。此时，定义p1为敌手在这个实验中输出为1的概率。

定义：

![20210518153916236.png][]

如果G是安全的PRG那么这个值就是可以忽略的，我们还可以构造一个敌手B1，B1的运行过程如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

当r是由伪随机数生成的，那么相当于Game0; 当r是由真随机选取的，那么该实验相当于Game1.

则显然敌手B1的优势为 |p1 - p0|。

继续，我们构造游戏Game1，如语义安全的定义可得，将所有内部两个实验全部替换为伪随机数生成器，就得到了Game1的运行过程，如下所示：

![20210518155514536.png][]

定义p2 为得到敌手A输出1的概率。与上文思路相同，我们可以得到一个敌手B2，其优势定义为：![20210518160327893.png][]

现在，我们会以一下敌手A的总体优势计算结果，表示如下:

![20210518161418739.png][]

以上是按照语义安全的第一种概念进行的定义，由于我们知道关于语义安全定义还有一种比特猜测版本的定义，以下给出n = 2时，比特猜测版本的证明方式.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

定义W0为在实验0输出1的概率，定义W1为在实验1输出1的概率。如果B选的的是B1那么相当于进行的是Game0与Game1的实验，如果B选的是B2那么相当于进行的是Game1与Game2的实验。

计算W0事件的概率为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

计算W1事件的概率为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

因此，由语义安全定义可以得到敌手B获胜的概率为：

![20210518170051266.png][]

**定理3.2的一般化证明**

证明思路：证明的思路与方法，实际上与上文类似，即为不断的替换伪随机数生成器为真实随机数。然后直到所有的PRG组件都被替换。

在这个过程中证明亦有两种思路，第一种是构造n个敌手来对这n+1个游戏进行攻击，然后分析其中的敌手优势概率。但是这里存在一个问题

n个敌手本质上不是一个静态变量，类似于上文的分析是比较困难的。此处采用构造一个统一敌手的方式进行证明。

*证明*：

敌手A为一个有效的PRG敌手。定义n+1个混合游戏（hybrid games）。Hybird j 是一个敌手A与挑战者之间的游戏，由一组n个数组成。

其中前j个为真实随机数，n-j个为伪随机数发生器生成的随机数，最后敌手A输出0或者1。工作过程如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

定义p0为敌手A在实验1下输出1的概率，pn为敌手A在实验0下输出1的概率，pj 为敌手A在hybird j 下输出1的概率。

下图展示了j的不同与hybird j 取值的区别：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6][]

根据语义安全的定义，我们得到敌手A的概率为：

![2021051817205378.png][]

敌手B的运行过程如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7][]

定义这个模型下的概率时间内容：

![20210518173006747.png][]

因此我们得到概率结果：

![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][]

证明完毕。

### 单词表： ###

amusing: 有趣的                                               spirit : <n.v> 精神 鼓励

cable: <n>电缆 <vt>电报                                  incrementally: <adv> 增加

Even worse: 更糟的是                                      expansion rate： 扩张率

intercepts: 摒弃，窃听                                     merit： <n>有点价值  <v>值得

composing: 组成                                              instantiate: <v>实例化

As it turn out: 其实，结果，事实证明              esoteric <adj> 只有内行才懂的；深奥的，限于小圈子的

sequential : <adj> 连续，相继                         explicitly<adv> 明确的，明白的

positive ：<adj/n> 积极，正的                        a hint of : 少许，一点点

linguistic: 语言的                                             In contrast: 与此相反，比较起来

[20210517110748820.png]: /images/20221020/5f06851dc3ae47e4a534609eccd0d130.png
[20210517110808778.png]: /images/20221020/9b89de5790444bab93a16e617dfaa5a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221020/3fde4604be9b4147afad08739fd0bb43.png
[20210518111922567.png]: /images/20221020/4e9f22cb4add4dfb99cc6857a8dcc799.png
[20210518112314892.png]: /images/20221020/ceffc8dff9d74477a7c96ec8ce191192.png
[20210518145345358.png]: /images/20221020/32963d0429bb416e9bc4150698c8053f.png
[20210518150045231.png]: /images/20221020/ad8170c06cdb465f86c6d28751aa2183.png
[2021051815024529.png]: /images/20221020/c6e3fdcbac034019b64f94d279c61b49.png
[20210518153916236.png]: /images/20221020/2a38da2b1dd94cc880704da488c977b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221020/1c9a685322cf4312b952fd3bd18d9aeb.png
[20210518155514536.png]: /images/20221020/96ab6363e02e49a2ac7b9c6cecd9f948.png
[20210518160327893.png]: /images/20221020/b9769d987d0445f29813aa6c6f7b6aac.png
[20210518161418739.png]: /images/20221020/db477e5677934d37a37076ff58252116.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221020/5ad4efda921b40078478d7dd569b84b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221020/18b7ae72a7874460bf44b4483337b71e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221020/f3e2d33f65324d4b8bfddd1fcf69a26b.png
[20210518170051266.png]: /images/20221020/3bf32a1d240848849eec480336e4ea57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20221020/ec54bc9b66ba4f288cb1c74500f78c25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6]: /images/20221020/2e99ae085264413d89aaa27ca75132a2.png
[2021051817205378.png]: /images/20221020/1ba55128731249e29484b87a57b69750.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7]: /images/20221020/0d3dc744bdde42eb83fa77b130dfb03e.png
[20210518173006747.png]: /images/20221020/385110e8bab34869837f4f5717e4af84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8]: /images/20221020/0914b3c187f949bea3a09a8185c54317.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9]: /images/20221020/69d918b9f9594961bc73b2bb5a8bc72f.png