当前位置 博文首页 > zmrlinux：《A Graduate Coursse in Applied Cryptography》chap
原文教材：
????????Boneh Dan , Shoup Victor . A Graduate Course in Applied Cryptography[J].
????????该书项目地址（可以免费获取）：http://toc.cryptobook.us/
????????系列博客为对该教材的学习笔记（只包括我认为重要的东西）
?
该书的3.3节内容比较简单，只说到了两个部分内容：
第一: two time pad 是不安全的加密协议，很简单类似这种流密码的秘钥不能反复使用。?
? ? ? ? ?这种不安全的状况描述如下：
? ? ? ? ??
? ? ? ? ? ? ?
? ? ? ? ?此时，破解m1与m2的异或值是比较简单的。
第二：one time pad 是可延展的。
? ? ? ? 这种不安全的状况描述如下：
? ? ? ? ? ? ? ??
? ? ? ? 敌手在消息传递过程中进行恶意修改，可能会导致接受方获取到被修改的内容，称之为可延展的。
该书本节主要讨论了构造PRG的方法。
3.4.1? A parallel? construction
本节主要描述了一种构造随机数生成器的方法，很简单直接将多个PRG并行组合成为一个新的随机数生成器，描述如下：
这种随机数发生器被称为 n-wise parallel composition of G , n宽的并行随机数发生器。
此时，我们证明该构造是安全的，类似之前的思路，首先给出一个安全性定理描述：
? ? ? ?如果G是安全的PRG，那么G`也是安全的。那么，问题来了。如何证明该方案是安全的？使用类似之前提到的办法，我们设计两个实验，
在实验0中，使用所有并行的随机数生成器来生成随机数，在实验1中，使用所有真正的随机数来代替这些伪随机数发生器。思路与本书
Attack Game 3.1 相同。但是，这里又存在一个问题，并行构造的随机数生成器内部是由多个伪随机数生成器构成的，我们无法证明如果有
部分被替换为真随机数，部分没有被替换成随机数的这种情况。
? ? ? ?此时，我们将敌手看成是对于整个方案攻击的敌手，如果存在一个敌手A能够攻击成功组合的伪随机数生成器G`, 那么久存在一个敌手B能够攻击成功一个单独的伪随机数生成器G。
? ? ??
? ? ?此时我们得到敌手攻击该方案的优势至少为：PRGadv[A,G`] = PRGadv[B,G]。即，A攻击G`的优势至少应该和B攻击G的优势相等。
? ? ? 然而，此时我们还不能知道这样的证明是否合理与正确，进一步分析，从实例化的角度来看，我们假设组合的伪随机数生成器中由两个伪随机数生成器构成。
? ? ? 那么，根据语义安全攻击游戏Game3.1。我们得到两个攻击游戏Game0 和 Game1。
? ? ? Game0：
? ? ? ? ?
? ? ?在Game0中，所有的并行随机数生成器由伪随机数生成器构成,定义p0 为敌手A输出1的概率。
? ? ?Game1:
? ? ? ? ? ?
? ? ?在Game1中，将其中一个随机数生成器替换为真随机数，首先，我们考虑第一个问题，Game1实验并没有完全替换两个随机数生成器为什么？因为在完全被替换成为随机数之前，
该实验存在一个中间的状态，即为一个为真随机数一个是伪随机数发生器。这种情况，我们也必须考虑到。所以，实验1应该是被用来描述这种中间状态，也称之为"hybrid"实验。直觉上，
如果G是安全的，那么敌手也是无法察觉到有什么不同的。此时，定义p1为敌手在这个实验中输出为1的概率。
定义：
? ? ? ?
? ? ? 如果G是安全的PRG那么这个值就是可以忽略的，我们还可以构造一个敌手B1，B1的运行过程如下：
? ? ? ? ? ? ? ??
? ?当r是由伪随机数生成的，那么相当于Game0; 当r是由真随机选取的，那么该实验相当于Game1.
? ?则显然敌手B1的优势为 |p1 - p0|。
继续，我们构造游戏Game1，如语义安全的定义可得，将所有内部两个实验全部替换为伪随机数生成器，就得到了Game1的运行过程，如下所示：
定义p2 为得到敌手A输出1的概率。与上文思路相同，我们可以得到一个敌手B2，其优势定义为：
现在，我们会以一下敌手A的总体优势计算结果，表示如下:
? ? ??
以上是按照语义安全的第一种概念进行的定义，由于我们知道关于语义安全定义还有一种比特猜测版本的定义，以下给出n = 2时，比特猜测版本的证明方式.
定义W0为在实验0输出1的概率，定义W1为在实验1输出1的概率。如果B选的的是B1那么相当于进行的是Game0与Game1的实验，如果B选的是B2那么相当于进行的是Game1与Game2的实验。
计算W0事件的概率为：
计算W1事件的概率为：
因此，由语义安全定义可以得到敌手B获胜的概率为：
定理3.2的一般化证明
证明思路：证明的思路与方法，实际上与上文类似，即为不断的替换伪随机数生成器为真实随机数。然后直到所有的PRG组件都被替换。
在这个过程中证明亦有两种思路，第一种是构造n个敌手来对这n+1个游戏进行攻击，然后分析其中的敌手优势概率。但是这里存在一个问题
n个敌手本质上不是一个静态变量，类似于上文的分析是比较困难的。此处采用构造一个统一敌手的方式进行证明。
证明：
? ? ? ? ?敌手A为一个有效的PRG敌手。定义n+1个混合游戏（hybrid games）。Hybird j 是一个敌手A与挑战者之间的游戏，由一组n个数组成。
其中前j个为真实随机数，n-j个为伪随机数发生器生成的随机数，最后敌手A输出0或者1。工作过程如下图所示：
定义p0为敌手A在实验1下输出1的概率，pn为敌手A在实验0下输出1的概率，pj 为敌手A在hybird j 下输出1的概率。
下图展示了j的不同与hybird j 取值的区别：
根据语义安全的定义，我们得到敌手A的概率为：
敌手B的运行过程如下图所示：
定义这个模型下的概率时间内容：
因此我们得到概率结果：
证明完毕。
?
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: 与此相反，比较起来
?
cs