6.2.2. The Blum Blum Shub Sequence Generator (Blum Blum Shub序列生成器)

6.2.2. The Blum Blum Shub Sequence Generator (Blum Blum Shub序列生成器)

已经证明可以从大整数的因式分解和其他密码学困难问题构建伪随机序列生成器 [NIST_11]。因为这些建立在NP-complete问题的假定难度上, 所以它们可以说比基于专门密码算法 (如DES或AES) 的伪随机数生成器具有更强的理论基础。

Blum, Blum, Shub伪随机序列生成器 [BBS] 就是这样一个例子。它使用最初来自熵的种子来设置状态, 然后迭代一个简单的函数以产生连续的数字。该函数, 对于内部状态值X, 是

X     = ( X  ^ 2 ) mod M
 n+1       n

其中M是难以因式分解的两个大质数的乘积。输出可以是X的最低有效位。

应选择M和种子, 以便序列不会快速收敛到短循环或单个值。[BBS]中给出了详细信息。

与OFB/CTR技术相比, 使用此生成器的一个缺点是它的速度要慢几个数量级。