檢視偽隨機數生成器的原始碼

{| class="wikitable" style="float:right; margin: -10px 0px 10px 20px; text-align:left"
|<center>'''偽隨機數生成器'''<br><img src="https://img-blog.csdn.net/20181013154745228?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" width="280"></center><small>[https://www.itread01.com/content/1544816374.html 圖片來自itread01]</small> 
|}

'''伪随机数生成器'''（pseudo random number generator，'''PRNG'''），又被称为'''确定性随机比特生成器'''（deterministic random bit generator，'''DRBG'''），是一个生成[[數字列表|数字序列]]的算法，其特性近似于[[随机数]]序列的特性。PRNG生成的序列并不是[[真随机]]，因此它完全由一个初始值决定，这个初始值被称为PRNG的随机种子|Random seed（seed，但这个种子可能包含真随机数）。尽管接近于真随机的序列可以通过[[硬件随机数生成器]]生成，但伪随机数生成器因为其生成速度和可再现的优势，在实践中也很重要。


'''PRNG'''是[[模拟]]（例如，[[蒙特卡洛方法]]<ref>[https://wiki.mbalib.com/zh-tw/%E8%92%99%E7%89%B9%E5%8D%A1%E7%BD%97%E6%96%B9%E6%B3%95 蒙特卡洛方法]，mbalib</ref> ）、[[电子游戏]]（例如[[过程生成]]）以及[[密码学]]等应用的核心。加密应用程序要求不能从以前的输出中预测输出，而且更复杂的、不具有简单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方法的周期长达2<sup>19937</sup>−1，被证明在623个维度上是均匀分布的（对于32位数值），同时它的运行速度比其他统计方法快。

在2003年，[[George Marsaglia]]提出了[[xorshift]]生成器家族，它也基于线性递归。这种生成器的运行速度非常快，再结合非线性操作，通过了强有力的统计测试。

在2006年，[[Well Equidistributed Long-period Linear|WELL]]家族的生成器被提出。WELl生成器在某些方面提高了Mersenne Twister的质量，Mersenne Twister具有非常大的状态空间，而且从含有大量0值的状态空间中的恢复非常缓慢。
aphically secure pseudorandom number generators==

==密码安全的伪随机数生成器==

适合于加密应用程序的PRNG称为'''加密安全的PRNG'''（'''CSPRNG'''）。CSPRNG的一个必要条件是不知道初始种子的敌人在分辨生成器的输出序列和真随机序列时只有可忽略的优势。换句话说，若PRNG只需要通过特定统计测试时，则CSPRNG必须通过种子规模的多项式复杂度内的所有统计测试。尽管这一性质的证明超出了计算复杂性理论目前的技术水平，大量的证据如下，把CSPRNG规约到计算困难的数学问题，例如整数分解。通常，在一个算法被认证为CSPRNG之前需要多年的检验。
CSPRNG的类别包括：

* [[stream cipher]]s
* 技术模式或输出反馈模式的块加密
* 保证密码安全的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测试（不同长度运行的频率）、来自于[[Federal Office for Information Security|BSI]]的longruns测试、autocorrelation测试。
* K3 - 给定任何子序列，任何攻击者都无法计算后续序列或者生成器的内部状态
* K4 - 给定生成器的内部状态，任何攻击者都无法计算之前的序列或者生成器之前的状态

对于密码学应用，只有满足K3和K4标准的生成器是可以接受的。

== 周期性 ==
A PRNG can be started from an arbitrary initial state using a [[random seed|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 [[bit]]s. 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，这一点尤其明显。

== 參考文獻 == 
{{reflist}}
[[Category: 310 數學總論]]