什麼是隨機數字產生器?

隨機數字產生器(RNG)是產生隨機數或偽隨機數的系統。下一個數字能否真正被預測,取決於產生器的類型。有些產生器依賴物理過程,有些用演算法計算數字,還有一些演算法被設計成:即使有人看過它們的輸出,也無法預測接下來會出現什麼。看起來隨機與不可預測是兩種不同的性質,本文的大部分內容講的正是這一區別。

硬體隨機數產生器

硬體隨機數產生器(HRNG)也稱真隨機數產生器(TRNG),它的數字來自物理過程。最古老的硬體隨機源就在我們眼前:拋出的硬幣、擲出的骰子、輪盤。力學可以完整地描述其中每一種,但製作精良的輪盤在實踐中仍然無法預測,因為每次旋轉起始狀態的微小差異會放大成完全不同的結果。

現代硬體產生器則測量微觀現象:電子電路中的散粒雜訊和熱雜訊、大氣雜訊、量子效應。它們是良好的熵源——熵即可以測量的不可預測性——但物理源本身並不完美:它可能有偏差、可能隨時間漂移,也可能失效,因此必須評估和監控其品質,並在必要時對輸出作進一步處理,NIST SP 800-90B 等標準描述的正是這些。硬體源用於最需要保證的地方——首先是密碼學,它們為傳輸層安全性協定(TLS)等協定背後的金鑰提供不可預測的初始材料。

偽隨機數產生器

物理設備之外的另一種選擇是演算法。偽隨機數產生器(PRNG)產生的序列看起來隨機,卻完全由一個稱為種子(seed)的初始值決定。把同一個種子交給同一個演算法,每次都會得到同一個序列。在結果必須不可預測、而種子或內部狀態又可能被猜出或重建的場合,這是弱點;在結果必須可重現的場合,這又是優點——模擬或測試可以原樣重新執行。PRNG 還速度快、成本低、易於實作,因此大多數軟體都依賴它們。著名的演算法家族包括線性同餘產生器(LCG)、xorshift 產生器和梅森旋轉演算法。

梅森旋轉演算法

梅森旋轉演算法(Mersenne Twister)由松本真(Makoto Matsumoto)和西村拓士(Takuji Nishimura)於 1997 年發表,是使用最廣泛的偽隨機數產生器之一,也是許多程式語言的預設選擇。它的名字來自其週期——序列開始重複之前的長度——在標準變體 MT19937 中,這一週期是梅森質數 219937 − 1。它能通過大多數隨機性統計檢驗,很適合用於模擬。但它並不是為保守秘密而設計的:根據 624 個連續的 32 位元輸出,任何人都能重建它的內部狀態並預測之後的每一個值,因此不能把它用於金鑰、密碼或任何必須保持不可預測的東西。

密碼學安全產生器與熵

許多應用同時需要兩樣東西:演算法的速度和物理源的不可預測性。答案是密碼學安全偽隨機數產生器(CSPRNG)。它仍然是 PRNG,但其構造使得看到部分輸出也沒有切實可行的方法預測其餘部分;它的種子來自真實的熵源,並定期重新播種。來自物理源的種子並不能讓普通 PRNG 變得安全,演算法本身必須為此而設計。熱雜訊或硬體事件的時間等物理源提供少量真正的隨機性,CSPRNG 則以快得多的速度由此得到一長串數值。這種組合正是作業系統提供給其上運行的程式的東西,也是如今「隨機數字產生器」在實踐中通常所指的含義。它用來產生加密金鑰、工作階段權杖和密碼。

瀏覽器中的隨機數

JavaScript 為網頁提供兩種內建的獲取隨機值的方式,它們屬於不同的類別。Math.random() 是普通的 PRNG:語言標準把演算法交給各瀏覽器自行決定,對安全性不作任何承諾——用於動畫沒問題,用於可能有人質疑的抽籤則不合適。另一種是 Web Crypto API。它的 crypto.getRandomValues() 方法返回密碼學強度的隨機值,由以作業系統的熵為種子的 CSPRNG 產生。

我們的線上隨機數字產生器每次抽取都使用 Web Crypto API,數字在您的瀏覽器中產生,而不是在伺服器上。本站其他產生器也由同一隨機源驅動,無論您是擲骰子、拋硬幣還是產生密碼。

從隨機位元到指定範圍內的數字

密碼學安全的產生器只是公平抽取的一半。它提供原始位元,程式還要把它們轉換成您所需範圍內的數字——偏差正是可能在這裡混進來。假設隨機源以相等的機會給出 0 到 9 的值,而您需要一個 0 到 5 的數字。取除以 6 的餘數看起來很自然,但這樣 0、1、2、3 各有兩種出現方式,而 4 和 5 只有一種,於是 0 到 3 中每個數字的機會是 20%,4 和 5 各只有 10%。消除這種偏差的一種方法是捨棄不合適的值並重新抽取;隨機數字資料對此有詳細說明。

還有兩件事常讓人意外。重複是正常的:從 1 到 10 中獨立抽取一個整數、每個數字機率相等時,剛抽出的數字再次出現的機會與其他任何數字一樣,都是 1/10。不重複的抽取是另一種抽取,並不「更隨機」。而且,僅有公平的產生器並不能讓整個過程公平:參與者名單和嘗試次數同樣重要,我們的如何隨機抽取獲獎者一文對此有說明。