偽隨機數生成器檢視原始碼討論檢視歷史
 |
偽隨機數生成器（pseudo random number generator，PRNG），又被稱為確定性隨機比特生成器（deterministic random bit generator，DRBG），是一個生成數字序列的算法，其特性近似於隨機數序列的特性。PRNG生成的序列並不是真隨機，因此它完全由一個初始值決定，這個初始值被稱為PRNG的隨機種子|Random seed（seed，但這個種子可能包含真隨機數）。儘管接近於真隨機的序列可以通過硬件隨機數生成器生成，但偽隨機數生成器因為其生成速度和可再現的優勢，在實踐中也很重要。
PRNG是模擬（例如，蒙特卡洛方法[1] ）、電子遊戲（例如過程生成）以及密碼學等應用的核心。加密應用程序要求不能從以前的輸出中預測輸出，而且更複雜的、不具有簡單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方法的周期長達219937−1，被證明在623個維度上是均勻分布的（對於32位數值），同時它的運行速度比其他統計方法快。
在2003年，George Marsaglia提出了xorshift生成器家族，它也基於線性遞歸。這種生成器的運行速度非常快，再結合非線性操作，通過了強有力的統計測試。
在2006年，WELL家族的生成器被提出。WELl生成器在某些方面提高了Mersenne Twister的質量，Mersenne Twister具有非常大的狀態空間，而且從含有大量0值的狀態空間中的恢復非常緩慢。 aphically secure pseudorandom number generators==
密碼安全的偽隨機數生成器
適合於加密應用程序的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的longruns測試、autocorrelation測試。
- K3 - 給定任何子序列，任何攻擊者都無法計算後續序列或者生成器的內部狀態
- K4 - 給定生成器的內部狀態，任何攻擊者都無法計算之前的序列或者生成器之前的狀態
對於密碼學應用，只有滿足K3和K4標準的生成器是可以接受的。
周期性
A PRNG can be started from an arbitrary initial state using a 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 bits. 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，這一點尤其明顯。