伪随机数生成器

伪随机数生成器（pseudo random number generator，PRNG），又被称为确定性随机比特生成器（deterministic random bit generator，DRBG），^[1]是一个生成数字序列的算法，其特性近似于随机数序列。伪随机数生成器生成的序列并不是真随机，因此它的每一个数完全由一个初始值决定，这个初始值被称为随机种子（英语：Random seed）（seed种子有时使用接近于真随机的硬件随机数生成器生成）。尽管接近于真随机的序列可以通过硬件随机数生成器生成，但伪随机数生成器因为其生成速度和可再现的优势，在实践中显得尤为重要。^[2]

PRNG是仿真（例如蒙特卡洛方法）、电子游戏（例如过程生成）以及密码学等应用的核心。加密程序不能从以前的输出中预测输出，而要采用更复杂的、不具有简单PRNGs线性特性的算法。

PRNG的核心是良好的统计特性，通常需要严格的数学分析来证明PRNG生成的序列的准确性足够接近真随机以满足预期用途。

周期性

PRNG可以使用随机种子（英语：Random seed）（和种子状态）从任意初始状态启动，使用同一状态进行初始化时，它将始终生成相同的序列。PRNG的周期定义为：序列的无重复前缀长度在所有起始状态中的最大值。周期受状态数的限制，通常用比特位数表示。然而，每增加一个比特位，周期长度就可能增加一倍，所以构建周期足够长的PRNG对于许多实际应用程序来说是很容易的。

如果PRNG的内部状态包含n位，那么它的周期不会超过2ⁿ，甚至可能非常短。对于大多数PRNG，周期长度的计算并不需要遍历整个周期。线性反馈移位寄存器（LFSR）的周期通常正好是2ⁿ−1。線性同餘方法的周期可以通过因式分解进行计算。 尽管PRNG在达到周期之后会出现重复的结果，但重复序列的出现并不意味着到达了一个周期，因为它的内部状态可能比输出要大很多。对于输出为1位的PRNGs，这一点尤其明显。

确定性生成器的潜在问题

在实践中，许多常见的PRNG会显示出导致统计模式检测测试失败的情况。John von Neumann警告不要把PRNG错误地解释为真随机数生成器，还开玩笑说：“任何使用算术方法生成随机数的人，都是有罪的”。^[3]

• 某些种子状态的周期比预期的短(在这种情况下，这种种子状态可以称为“弱”)；
• 生成的大量数字分布不均匀；
• 连续值的关联性；
• 输出序列的维数分布差；
• 某些值出现的位置之间的距离与随机序列分布的距离不同。

在很多领域，21世纪之前的很多依赖于随机选择、蒙特卡洛模拟或者以其他方式依赖PRNG的研究工作，由于使用了品质较差的PRNGs，其可靠性比可能的结果要低得多。^[4] 即使在今天，有时也需要谨慎，如下面的来自International Encyclopedia of Statistical Science（2010，^[5]）的警告所示:

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。^[6][7] 然而LCGs的质量很差。

第一个避免了主要问题而且运行速度很快的PRNG是1998年发布的Mersenne Twister。此后还开发了其他高质量的PRNG。

基于线性递归的生成器

在20世纪下半叶，PRNG的标准算法由線性同餘方法（LCG）构成。众所周知，LCG的质量是不够的，但也没有更好的方法。Press et al. (2007) 描述了这种情况：“如果所有因为LCG而受质疑的科学论文从书架上消失，那么每一个架子上都会有一个拳头大小的空隙”。^[8]

伪随机生成器构造的重大进展，是在二元域中引入的线性递归技术，这种生成器和线性反馈移位寄存器有关。

1997年发明的Mersenne Twister，^[9]避免了很多问题。Mersenne Twister方法的周期长达2¹⁹⁹³⁷−1，被证明在623个维度上是均匀分布的（对于32位数值），同时它的运行速度比其他统计方法快。

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

在2006年，WELL家族的生成器被提出。^[11] WELl生成器在某些方面提高了Mersenne Twister的质量，Mersenne Twister具有非常大的状态空间，而且从含有大量0值的状态空间中的恢复非常缓慢。

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

主条目：密码学安全伪随机数生成器

适合于加密应用程序的PRNG称为加密安全的PRNG（CSPRNG）。CSPRNG的一个必要条件是不知道初始种子的敌人在分辨生成器的输出序列和真随机序列时只有可忽略的优势。换句话说，若PRNG只需要通过特定统计测试时，则CSPRNG必须通过种子规模的多项式复杂度内的所有统计测试。尽管这一性质的证明超出了计算复杂性理论目前的技术水平，大量的证据如下，把CSPRNG规约到计算困难的数学问题，例如整数分解。^[12] 通常，在一个算法被认证为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可以通过单向函数构造。^[13]然而，这些构造在实际应用中非常缓慢，主要用于理论研究。 有证据表示，NSA向NIST认证的伪随机生成器Dual_EC_DRBG注入了非对称后门。^[14]

大多数使用PRNG的密码算法的安全性是基于下面的假设：PRNG和真随机序列的分辨是不可行的。

BSI评估标准

德国Federal Office for Information Security (Bundesamt für Sicherheit in der Informationstechnik, BSI)制订了四条评估确定性随机生成器的标准。^[15] 如下：

• K1 - 产生的随机数序列彼此不同的概率应该是很高的
• K2 - 根据某些统计测试，无法分辨产生的序列和真随机序列。这些测试包括： monobit测试（序列中的0和1的数量相等）、poker测试（ chi-squared测试的特殊情况）、runs测试（不同长度运行的频率）、来自于BSI^[15] 和NIST,^[16]的longruns测试、autocorrelation测试。
• K3 - 给定任何子序列，任何攻击者都无法计算后续序列或者生成器的内部状态
• K4 - 给定生成器的内部状态，任何攻击者都无法计算之前的序列或者生成器之前的状态

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

数学定义

给定

• ${\displaystyle P}$  - ${\displaystyle \left(\mathbb {R} ,{\mathfrak {B}}\right)}$ 上的概率分布，其中${\displaystyle {\mathfrak {B}}}$ 是实数集上的Borel set
• ${\displaystyle {\mathfrak {F}}}$  - 非空子集${\displaystyle {\mathfrak {F}}\subseteq {\mathfrak {B}}}$ ，例如 ${\displaystyle {\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$ 
• ${\displaystyle A\subseteq \mathbb {R} }$  - 非空集合

称一个函数${\displaystyle f:\mathbb {N} _{1}\rightarrow \mathbb {R} }$ （${\displaystyle \mathbb {N} _{1}=\left\{1,2,3,\dots \right\}}$ 是正整数的一个子集）为一个伪随机生成器，当且仅当：

• ${\displaystyle f\left(\mathbb {N} _{1}\right)\subseteq A}$ 
• ${\displaystyle \forall E\in {\mathfrak {F}}\quad \forall 0<\varepsilon \in \mathbb {R} \quad \exists N\in \mathbb {N} _{1}\quad \forall N\leq n\in \mathbb {N} _{1},\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n}}-P(E)\right|<\varepsilon }$ 

相關條目

•  数学主题

• 随机数生成
• 随机性
• 偽亂數二進位數列
• 硬件随机数生成器
• Random.org

參考資料

1. Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles. Recommendation for Key Management (PDF). NIST Special Publication 800-57. NIST. July 2012 [19 August 2013]. （原始内容 (PDF)于2013-06-26）. 
2. Pseudorandom number generators. Khan Academy. [2016-01-11]. （原始内容于2020-11-26）. 
3. Von Neumann, John. Various techniques used in connection with random digits (PDF). National Bureau of Standards Applied Mathematics Series. 1951, 12: 36–38 [2019-02-25]. （原始内容 (PDF)于2020-11-06）. 
4. Press et al. (2007), chap.7
5. L'Ecuyer P. (2010), "Uniform random number generators", International Encyclopedia of Statistical Science (editor—Lovric M.) Springer.
6. Random (Java Platform SE 8) （页面存档备份，存于互联网档案馆）, Java Platform Standard Edition 8 Documentation.
7. Random.java （页面存档备份，存于互联网档案馆） at OpenJDK.
8. Press et al. (2007) §7.1
9. Matsumoto, Makoto; Nishimura, Takuji. Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator (PDF). ACM Transactions on Modeling and Computer Simulation (ACM). 1998, 8 (1): 3–30 [2019-02-25]. doi:10.1145/272991.272995. （原始内容 (PDF)于2019-09-25）. 
10. Marsaglia, George. Xorshift RNGs. Journal of Statistical Software. July 2003, 8 (14) [2019-02-25]. （原始内容于2015-09-02）. 
11. Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto. Improved long-period generators based on linear recurrences modulo 2 (PDF). ACM Transactions on Mathematical Software. 2006, 32 (1): 1–16 [2019-02-25]. doi:10.1145/1132973.1132974. （原始内容 (PDF)于2020-08-11）. 
12. Song Y. Yan. Cryptanalytic Attacks on RSA. Springer, 2007. : 73. ISBN 978-0-387-48741-0. 
13. Pass, Rafael. Lecture 11: The Goldreich-Levin Theorem (PDF). COM S 687 Introduction to Cryptography. [20 July 2016]. （原始内容 (PDF)于2019-07-12）. 
14. Matthew Green. The Many Flaws of Dual_EC_DRBG. [2019-02-25]. （原始内容于2016-08-20）. 
15. Schindler, Werner. Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik: 5–11. 2 December 1999 [19 August 2013]. （原始内容 (PDF)于2018-01-19）. 
16. . FIPS. NIST: 4.11.1 Power–Up Tests. 1994-01-11 [19 August 2013]. （原始内容存档于2013-05-27）. 

參考書目

• Barker E., Kelsey J., Recommendation for Random Number Generation Using Deterministic Random Bit Generators （页面存档备份，存于互联网档案馆）, NIST SP800-90A, January 2012
• Brent R.P., "Some long-period random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
• Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
• Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, Springer-Verlag.
• Knuth D.E.. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
• Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. ISBN 9780691025469
• von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
• Peterson, Ivars. The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. 1997. ISBN 0-471-16449-6. 
• Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
• Viega J., "Practical Random Number Generation in Software （页面存档备份，存于互联网档案馆）", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

外部連結

• TestU01 （页面存档备份，存于互联网档案馆）: A free, state-of-the-art (GPL) C++ Random Number Test Suite.
• DieHarder （页面存档备份，存于互联网档案馆）: A free (GPL) C Random Number Test Suite.
• "Generating random numbers （页面存档备份，存于互联网档案馆）" (in embedded systems) by Eric Uner (2004)
• "Analysis of the Linux Random Number Generator （页面存档备份，存于互联网档案馆）" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006)
• "Better pseudorandom generators （页面存档备份，存于互联网档案馆）" by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan (Microsoft Research, 2012)