偽隨機數生成器

偽隨機數生成器（英語：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^{n}$ ，甚至可能非常短。對於大多數PRNG，周期長度的計算並不需要遍歷整個周期。線性反饋移位寄存器（LFSR）的周期通常正好是 $2^{n}-1$ 。線性同餘方法的周期可以通過因式分解進行計算。儘管PRNG在達到周期之後會出現重複的結果，但重複序列的出現並不意味着到達了一個周期，因為它的內部狀態可能比輸出要大很多。對於輸出為1位的PRNGs，這一點尤其明顯。

確定性生成器的潛在問題

在實踐中，許多常見的PRNG會顯示出導致統計模式檢測測試失敗的情況。約翰·馮諾依曼警告不要把PRNG錯誤地解釋為真隨機數生成器，還開玩笑說：「任何使用算術方法生成隨機數的人，都是有罪的」。^[3]

某些種子狀態的周期比預期的短(在這種情況下，這種種子狀態可以稱為「弱」)；
生成的大量數字分布不均勻；
連續值的關聯性；
輸出序列的維數分布差；
某些值出現的位置之間的距離與隨機序列分布的距離不同。

在很多領域，21世紀之前的很多依賴於隨機選擇、蒙特卡洛模擬或者以其他方式依賴PRNG的研究工作，由於使用了品質較差的PRNGs，其可靠性比可能的結果要低得多。^[4] 即使在今天，有時也需要謹慎，如下面的來自國際統計科學百科全書（英語：International Encyclopedia of Statistical Science）的警告所示^[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] 然而其的品質很差。

第一個避免了主要問題而且運行速度很快的PRNG是1998年發布的Mersenne Twister。此後還開發了其他高品質的PRNG。

基於線性遞歸的生成器

在20世紀下半葉，PRNG的標準算法由線性同餘方法（LCG）構成。眾所周知，LCG的質量不優，但也沒有更好的方法。Press et al. (2007) 描述了這種情況：「如果所有因為LCG而受質疑的科學論文從書架上消失，那麼每一個架子上都會有一個拳頭大小的空隙」。^[8]

偽隨機生成器構造的重大進展，是在二元域中引入的線性遞歸技術，這種生成器和線性反饋移位寄存器有關。

1997年發明的梅森旋轉算法，避免了很多問題^[9]。梅森旋轉算法的周期長達 $2^{19937}-1$ ，被證明在623個維度上是均勻分布的（對於32位數值），同時它的運行速度比其他統計方法快。

在2003年，George Marsaglia提出了xorshift生成器家族，^[10]它也基於線性遞歸。這種生成器的運行速度非常快，再結合非線性操作，通過了強有力的統計測試。

在2006年，WELL家族的生成器被提出。^[11] WELl生成器在某些方面提高了梅森旋轉算法的質量，梅森旋轉算法具有非常大的狀態空間，而且從含有大量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評估標準

德國聯邦信息安全辦公室(德語：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標準的生成器是可以接受的。

數學定義

給定

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

稱一個函數 $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ （ $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ 是正整數的一個子集）為一個偽隨機生成器，當且僅當：

$f\left(\mathbb {N} _{1}\right)\subseteq A$
$\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$

參考資料

^ 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）.
^ Pseudorandom number generators. Khan Academy. [2016-01-11]. （原始內容存檔於2020-11-26）.
^ 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）.
^ Press et al. (2007), chap.7
^ L'Ecuyer P. (2010), "Uniform random number generators", International Encyclopedia of Statistical Science (editor—Lovric M.) Springer.
^ Random (Java Platform SE 8) （頁面存檔備份，存於網際網路檔案館）, Java Platform Standard Edition 8 Documentation.
^ Random.java （頁面存檔備份，存於網際網路檔案館） at OpenJDK.
^ Press et al. (2007) §7.1
^ 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）.
^ Marsaglia, George. Xorshift RNGs. Journal of Statistical Software. July 2003, 8 (14) [2019-02-25]. （原始內容存檔於2015-09-02）.
^ 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）.
^ Song Y. Yan. Cryptanalytic Attacks on RSA. Springer, 2007. : 73. ISBN 978-0-387-48741-0.
^ Pass, Rafael. Lecture 11: The Goldreich-Levin Theorem (PDF). COM S 687 Introduction to Cryptography. [20 July 2016]. （原始內容存檔 (PDF)於2019-07-12）.
^ Matthew Green. The Many Flaws of Dual_EC_DRBG. [2019-02-25]. （原始內容存檔於2016-08-20）.
^ ^15.0 ^15.1 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）.
^ Security requirements for cryptographic modules. 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)

[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.

[GoldreichLevinNotes-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）.

[bsi_ais20-15] 15.0 ^15.1 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] Security requirements for cryptographic modules. FIPS. NIST: 4.11.1 Power–Up Tests. 1994-01-11 [19 August 2013]. （原始內容存檔於2013-05-27）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

周期性