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

One Time Pad

首先，为了引入Stream Cipher，Dan开始介绍经典的One-Time-Pad.
（注：OTP不是stream cipher ）

image

其中，

M = G = \{0,1\}^{n}, K = \{0,1\}^{n}

k的长度和消息的长度是一样的；（这也是OPT的最大的问题，如果我要加密1GB的数据，那么就需要同样大小的key对其加密）

C := E(k,m) = k \oplus m;

D(k,c) := k \oplus c;

因此，给定一组明文和密文，我们就能推断出这次加密的密钥；很明显，OPT是在密码学定义上是安全的；
这里，Dan引出了香农定理，详情可以参考笔记introruction to modern cryptography

Pseudorandom Generators

上一章节的回顾如下：

Review

想让OTP变得更加切合实际的做法是，用伪随机的key来替换随机的key，而使用了这种伪随机码的加密方式，我们就称之为Stream Cipher （SC）。因此，SC不是完美加密的算法，它依赖于特定的伪随机生成器（PRG）。

那么什么是PRG呢？ Dan给出的定义是这样的：PRG是一个函数公式，
$G : \{0,1\}^{s} \rightarrow \{0,1\}^{n}, n \gg s$
PRG is an efficient algorithm which can be computed by a determinstic algorithm.

PRG必须是不可预测的(unpredictable)

Suppose PRG is predictable
$\exists i : G(k)|_{1,2...i} \rightarrow G(K)|_{i+1,...,n}$

只要有一个符号可以根据前面已知的推断出来，那么这种随机生成器就不是安全的。 Dan 在这里给了具体的定义：

OTP的伪随机码版本

给了详细的定义之后，Dan就举了两个weak PRGs的例子。

Negligible vs. Non-Negligible

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

neg & non-neg

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

Examples

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

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

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

image

最后编辑于：2019.01.01 21:55:38

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

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