3.3 随机数生成器

真随机数生成器（TRNG）

真随机数生成器（TRNG）的突出特点就是她的输出不可复制的。例如，如果我们抛 100 次硬币并将这 100 次结果记作一个 100 位长的序列：地球上几乎没有人可以产生与这 100 位相同的序列。真随机数生成器都是基于物理过程，主要的例子包括抛硬币、掷骰子、半导体声音、数字电路中的时钟抖动和放射性衰变。密码学中通常使用 TRNG 生成会话密钥，然后在 Alice 和 Bob 之间进行分发或用于其他用途。

###（通用的）伪随机数生成器（PRNG）
伪随机数生成器从一个初始种子开始通过各种计算得到序列。通常，伪随机数序列是递归执行以下计算得到的：

s_0 = seed\\ s_{i +1} = f(s_i), i = 0, 1, ...

此表达式的一个推广形式就是s_{i+1} = f( s_i, s_{i-1}, …,s_{i-t})所示的生成器，其中 t 是一个固定的整数。最常见的例子就是线性同余生成器：

s_0 = seed s_{i+1} = as_i + b\ mod\ m, i = 0, 1, ...

其中，a，b，m 都是整型常量。注意：PRNG 并不是真正意义上的随机，因为它们可以计算出来，因此可以称为是计算确定的。
对 PRNG 的一个一般要求就是：它必须拥有良好的统计特性，意味着它的输出近乎与真随机数序列相同。

加密安全的伪随机数生成器

加密安全的伪随机数生成器（CSPRNG）是 PRNG 的一个特例，它拥有以下额外的属性：CSPRNG 是一种不可预测的 PRNG。通俗地说，这意味着给定密钥序列s_i, s_{i+1},…, s_{i+n-1} 的 n 个输出位（其中 n 为一个整数），得到后续位s_{i+n}, s_{i+n+1}…在计算上是不可行的。更准确的定义为：给定密钥序列中的 n 个连续位，不存在一个时间复杂度为多项式的算法使得成功预测下一个位s_{n+1}的概率超过 50% 。CSPRNG 的另一个属性是，给出上述序列，计算任何之前的位s_{i-1}, s_{i-2},…在计算上都是不可行的。
注意：只有在密码学中才要求 CSPRNG 具有不可预知性。在几乎所有的计算科学或计算机工程的情况中都需要伪随机数，但并不要求其具有不可预知性