伪随机数生成算法

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

 

**PRNG** 是仿真（例如蒙特卡洛方法）、電子遊戲（例如過程生成）以及密碼學等應用的核心。加密程序不能從以前的輸出中預測輸出，而要採用更複雜的、不具有簡單 PRNGs 線性特性的算法。

PRNG 的核心是良好的統計特性，通常需要嚴格的數學分析來證明 PRNG 生成的序列足夠接近真隨機以滿足預期用途。

## 周期性

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

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

## 確定性生成器的潛在問題

在實踐中，許多常見的 PRNG 會顯示出導致統計模式檢測測試失敗的情況。John von Neumann 警告不要把 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 et al. (2007) 描述了這種情況：「如果所有因為 LCG 而受質疑的科學論文從書架上消失，那麼每一個架子上都會有一個拳頭大小的空隙」。

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

1997 年發明的 Mersenne Twister，避免了很多問題。Mersenne Twister 方法的周期長達 219937−1，被證明在 623 個維度上是均勻分布的（對於 32 位數值），同時它的運行速度比其他統計方法快。

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

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

德國 Federal Office for Information Security (_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. 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)