偽隨機數生成器

偽隨機數生成器（pseudo random number generator，PRNG），又被稱為確定性隨機位元生成器（deterministic random bit generator，DRBG），是一個生成數字序列的演算法，其特性近似於隨機數序列。偽隨機數生成器生成的序列並不是完全隨機，生成的每一個數完全由一個初始值決定，這個初始值被稱為隨機種子（種子有時使用接近於完全隨機的硬體隨機數生成器生成）。儘管硬體隨機數生成器可以生成接近於完全隨機的序列，但偽隨機數生成器因為其生成速度和可再現的優勢，在實踐中顯得尤為重要。

PRNG多用於仿真（例如蒙地卡羅方法）、電子遊戲（例如程序化生成）以及密碼學等領域。此加密程序不能從以前的輸出中預測輸出，而要採用更複雜的、不具有簡單PRNGs線性特性的演算法。

PRNG的核心是具有良好的統計特性，通常需要嚴格的數學分析來證明其生成結果準確性足夠接近完全隨機，以滿足預期用途。

## 周期性

PRNG可以使用隨機種子從任意的初始狀態啟動，使用同一狀態進行初始化時，它將始終生成相同的序列。PRNG的周期定義為：序列的無重複前綴長度在所有起始狀態中的最大值。周期受狀態數的限制，通常用位元數表示。然而，每增加一個位元，周期長度就可能增加一倍，所以構建周期足夠長的PRNG對於許多實際應用程式來說是很容易的。

如果PRNG的內部狀態包含$n$位，那麼它的周期不會超過$2^n$，甚至可能非常短。對於大多數PRNG，周期長度的計算並不需要遍歷整個周期。線性反饋移位寄存器（LFSR）的周期通常正好是$2^n-1$。線性同餘方法的周期可以通過因式分解進行計算。儘管PRNG在達到周期之後會出現重複的結果，但重複序列的出現並不意味著到達了一個周期，因為它的內部狀態可能比輸出要大很多。對於輸出為1位的PRNG，這一點尤其明顯。

## 潛在問題

在實踐中，許多常見的PRNG會顯示出特定跡象，導致它們無法通過統計學的模式檢測。約翰·馮諾依曼警告，不要把PRNG錯誤地解釋為真隨機數生成器，還開玩笑說：「任何使用算術方法生成隨機數的人，都是有罪的」。這些缺陷包括:

- 某些種子狀態的周期短於預期:在這種情況下，這種種子被稱為「弱種子」。
- 生成的大量數字分布不均勻。
- 連續值之間存在關聯性。
- 輸出序列的空間維度分布不佳。
- 特定值出現的的間距與隨機序列分布的分布特徵不同。

在許多領域，21世紀之前依賴PRNG的研究工作，由於使用了低品質的PRNG，其可靠性遠低於理想。即使在今天，有時也需要謹慎，如下面的來自的警告所示: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。然而其的品質很差。直到 Java 17 版本，Java 的隨機數支援才得到了顯著的升級與改進。

一個避免了主要問題而且運行速度快的著名PRNG是1998年發布的梅森旋轉演演算法。學界也開發了許多在運算效能與統計表現上更高品質的 PRNG。

## 基於線性遞歸的生成器

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

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

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

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

在2006年，WELL家族的生成器被提出。WELl生成器在某些方面提高了梅森旋轉算法的質量，梅森旋轉算法具有非常大的狀態空間，而且從含有大量0值的狀態空間中的恢復非常緩慢。

## 密碼安全的偽隨機數生成器

適合於加密應用程式的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評估標準

德國聯邦資訊安全辦公室(Bundesamt für Sicherheit in der Informationstechnik, BSI)制訂了四條評估確定性隨機生成器的標準。如下：

- K1 - 產生的隨機數序列彼此不同的機率應該是很高的
- K2 - 根據某些統計測試，無法分辨產生的序列和真隨機序列。這些測試包括： monobit測試（序列中的0和1的數量相等）、poker測試（chi-squared測試的特殊情況）、runs測試（不同長度運行的頻率）、來自於BSI 和NIST,的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 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. . Chapter 3. Extensive coverage of statistical tests for non-randomness.
- Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996.
- 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.
- 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)