伪随机性与基于伪随机性的窃听难以分辨的私钥加密机制

伪随机性

意义

• 利用较短的随机种子能够生产出较长的一个伪随机串
• 一个较短长度的密钥就可以被用来加密很长的消息，并突破了完美保密性。

伪随机发生器

定义

G被定义为一种确定性多项式时间算法；
其中l(\cdot)是一个多项式；
其输出及其满足的条件：
对于所有s \in \{0, 1\}^n, G(s) = \{0, 1\}^{l(n)}

1. 

扩展性：\forall n, l(n) \gt n

2. 

伪随机属性是指：对于所有多项式时间的区分器D来说，在计算复杂度方面满足以下条件：存在一个可忽略的小概率函数negl(n)，使得D(r)输出结果与G(s)之间的区别不超过negl(n)。这里r是在均匀分布下从{0,1}^{{l(n)}空间中选取的一个随机样本，并且s是从{0,1}}n空间中独立选取的一个均匀分布样本值

称G为伪随机发生器，l(\cdot)为G的扩展系数

理解

1. 

G为什么是确定性算法？

我们的目标是利用短小精悍的密钥生成大量伪随机序列以实现加密功能。为了避免存储过长的安全键我们只需管理较短的安全键进而我们采用 G(k) \oplus m 的方式进行加密与解密操作。若函数 G 无法保证在不同输入下产生唯一输出则会导致整个