斯坦福大学密码学公开课——Stream Ciphers (1)
2019-01-01 本文已影响0人
Scaryang
One Time Pad
首先，为了引入Stream Cipher，Dan开始介绍经典的One-Time-Pad.
（ 注：OTP不是stream cipher ）
image
其中，
Review
想让OTP变得更加切合实际的做法是，用伪随机的key来替换随机的key，而使用了这种伪随机码的加密方式，我们就称之为Stream Cipher （SC）。因此，SC不是完美加密的算法，它依赖于特定的伪随机生成器（PRG）。
那么什么是PRG呢？ Dan给出的定义是这样的：PRG是一个函数公式，
PRG is an efficient algorithm which can be computed by a determinstic algorithm.
PRG必须是不可预测的(unpredictable)
Suppose PRG is predictable
只要有一个符号可以根据前面已知的推断出来，那么这种随机生成器就不是安全的。 Dan 在这里给了具体的定义：
OTP的伪随机码版本
给了详细的定义之后，Dan就举了两个weak PRGs的例子。
Negligible vs. Non-Negligible
废话不多说，直接上图...
neg & non-neg
上面的定义是在实际中的理解，并不是严格密码学定义，仅仅只是经验值而已。
根据这个定义，有几个例子可以帮助理解它的含义：
Examples
对于最后一个例子，其说的是只要出现了non-negligible，即便在其他分布都是negligible的情况下，也应该被规划为non-neg。
PRG是被一个安全系数所约束，其实
越大，PRG就越安全，seed length 和 输出的密文长度也会更长。
下面是严格意义上的关于PRG的预测性的定义：
image
