斯坦福大学密码学公开课——Stream Ciphers (1)

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的例子。

1. Linear congruential generator
2. Glibc Random

Negligible vs. Non-Negligible

废话不多说，直接上图...

neg & non-neg

上面的定义是在实际中的理解，并不是严格密码学定义，仅仅只是经验值而已。
根据这个定义，有几个例子可以帮助理解它的含义：

Examples

对于最后一个例子，其说的是只要出现了non-negligible，即便在其他分布都是negligible的情况下，也应该被规划为non-neg。

PRG是被一个安全系数所约束，其实越大，PRG就越安全，seed length 和 输出的密文长度也会更长。

下面是严格意义上的关于PRG的预测性的定义：

image