伪随机数生成器查看源代码讨论查看历史
 |
伪随机数生成器（pseudo random number generator，PRNG），又被称为确定性随机比特生成器（deterministic random bit generator，DRBG），是一个生成数字序列的算法，其特性近似于随机数序列的特性。PRNG生成的序列并不是真随机，因此它完全由一个初始值决定，这个初始值被称为PRNG的随机种子|Random seed（seed，但这个种子可能包含真随机数）。尽管接近于真随机的序列可以通过硬件随机数生成器生成，但伪随机数生成器因为其生成速度和可再现的优势，在实践中也很重要。
PRNG是模拟（例如，蒙特卡洛方法[1] ）、电子游戏（例如过程生成）以及密码学等应用的核心。加密应用程序要求不能从以前的输出中预测输出，而且更复杂的、不具有简单PRNGs线性特性的算法是必要的。
良好的统计特性，是PRNG的核心。通常，需要严格的数学分析来证明PRNG生成的序列足够接近真随机以满足预期用途。John von Neumann警告不要把PRNG错误地解释为真随机数生成器，还开玩笑说：“任何使用算术方法生成随机数的人，都是有罪的”。
确定性生成器的潜在问题
在实践中，许多常见的PRNG会显示出导致统计模式检测测试失败的工件。
- 某些种子状态的周期比预期的短(在这种情况下，这种种子状态可以称为“弱”)；
- 生成的大量数字分布不均匀；
- 连续值的关联性；
- 输出序列的维数分布差；
- 某些值出现的位置之间的距离与随机序列分布的距离不同。
在很多领域，21世纪之前的很多依赖于随机选择、蒙特卡洛模拟或者以其他方式依赖PRNG的研究工作，由于使用了质量较差的PRNGs，其可靠性比可能的结果要低得多。即使在今天，即使在今天，有时也需要谨慎，如下面的来自International Encyclopedia of Statistical Science（2010，）的警告所示:The list of widely used generators that should be discarded is [long] ... Check the default [PRNG] of your favorite software and be ready to replace it if needed. This last recommendation has been made over and over again over the past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago.
举例来说，考虑一下广泛使用的编程语言Java。Java仍然使用线性同馀方法 (LCG)来实现PRNG。然而LCGs的质量很差。
第一个避免了主要问题而且运行速度很快的PRNG是1998年发布的Mersenne Twister。此后还开发了其他高质量的PRNG。
基于线性递归的生成器
在20世纪下半叶，PRNG的标准算法由线性同馀方法（LCG）构成。众所周知，LCG的质量是不够的，但也没有更好的方法。Press etal. (2007) 描述了这种情况：“如果所有因为LCG而受质疑的科学论文从书架上消失，那么每一个架子上都会有一个拳头大小的空隙”。
伪随机生成器构造的重大进展，是在二元域中引入的线性递归技术，这种生成器和线性反馈移位寄存器有关。
1997年发明的Mersenne Twister，避免了很多问题。Mersenne Twister方法的周期长达219937−1，被证明在623个维度上是均匀分布的（对于32位数值），同时它的运行速度比其他统计方法快。
在2003年，George Marsaglia提出了xorshift生成器家族，它也基于线性递归。这种生成器的运行速度非常快，再结合非线性操作，通过了强有力的统计测试。
在2006年，WELL家族的生成器被提出。WELl生成器在某些方面提高了Mersenne Twister的质量，Mersenne Twister具有非常大的状态空间，而且从含有大量0值的状态空间中的恢复非常缓慢。 aphically secure pseudorandom number generators==
密码安全的伪随机数生成器
适合于加密应用程序的PRNG称为加密安全的PRNG（CSPRNG）。CSPRNG的一个必要条件是不知道初始种子的敌人在分辨生成器的输出序列和真随机序列时只有可忽略的优势。换句话说，若PRNG只需要通过特定统计测试时，则CSPRNG必须通过种子规模的多项式复杂度内的所有统计测试。尽管这一性质的证明超出了计算复杂性理论目前的技术水平，大量的证据如下，把CSPRNG规约到计算困难的数学问题，例如整数分解。通常，在一个算法被认证为CSPRNG之前需要多年的检验。 CSPRNG的类别包括：
- stream ciphers
- 技术模式或输出反馈模式的块加密
- 保证密码安全的PRNG，例如微软的密码学应用编程接口函数CryptGenRandom，Yarrow algorithm（集成进Mac OS X和FreeBSD）以及Fortuna
- 组合PRNG把多个PRNG算法组合在一起以移除可检测的非随机性
- 基于数学难题假设的设计，例如Micali–Schnorr generator、Naor-Reingold伪随机函数、Blum Blum Shub算法，这些算法具有较强的安全性。相比于传统方法，这些算法的速度非常缓慢，对于许多应用是不实际的。
通用PRNG。已经证明，密码安全的PRNG可以通过单向函数构造。然而，这些构造在实际应用中非常缓慢，主要用于理论研究。 有证据表示，NSA向NIST认证的伪随机生成器Dual_EC_DRBG注入了非对称后门 大多数使用PRNG的密码算法的安全性是基于下面的假设：PRNG和真随机序列的分辨是不可行的。
BSI评估标准
德国Federal Office for Information Security (Bundesamt für Sicherheit in der Informationstechnik, BSI)制订了四条评估确定性随机生成器的标准。如下：
- K1 - 产生的随机数序列彼此不同的概率应该是很高的
- K2 - 根据某些统计测试，无法分辨产生的序列和真随机序列。这些测试包括： monobit测试（序列中的0和1的数量相等）、poker测试（ chi-squared测试的特殊情况）、runs测试（不同长度运行的频率）、来自于BSI的longruns测试、autocorrelation测试。
- K3 - 给定任何子序列，任何攻击者都无法计算后续序列或者生成器的内部状态
- K4 - 给定生成器的内部状态，任何攻击者都无法计算之前的序列或者生成器之前的状态
对于密码学应用，只有满足K3和K4标准的生成器是可以接受的。
周期性
A PRNG can be started from an arbitrary initial state using a seed state. It will always produce the same sequence when initialized with that state. The period of a PRNG is defined thus: the maximum, over all starting states, of the length of the repetition-free prefix of the sequence. The period is bounded by the number of the states, usually measured in bits. However, since the length of the period potentially doubles with each bit of "state" added, it is easy to build PRNGs with periods long enough for many practical applications.
PRNG通过设定随机种子|Random seed可以从任意初始值开始生成。同样的初始值总是生成同样的序列。PRNG的周期定义为：所有初始值的最大长度的无重复前缀序列。周期受状态数的限制，通常用比特位数表示。然而，每增加一个比特位，周期长度就可能增加一倍，所以构建周期足够长的PRNG对于许多实际应用程序来说是很容易的。
如果PRNG的内部状态包含n位，那么它的周期不会超过2n，甚至可能非常短。对于大多数PRNG，周期长度的计算并不需要遍历整个周期。线性反馈移位寄存器（LFSR）的周期通常正好是2n−1。线性同馀方法的周期可以通过因式分解进行计算。 尽管PRNG在达到周期之后会出现重复的结果，但重复序列的出现并不意味着到达了一个周期，因为它的内部状态可能比输出要大很多。对于输出为1位的PRNGs，这一点尤其明显。