密碼系統需要隨機性才能安全，因此需要一個元件來提供隨機性，它的職責是在被要求時回傳隨機位元。要做到這件事，你需要兩樣東西：

  • 一個不確定性的來源（或稱熵源，source of entropy），由隨機數產生器（RNG，random number generators）提供。
  • 一個密碼學演算法，從熵源產生高品質的隨機位元，這見於偽隨機數產生器（PRNG，pseudorandom number generators）。

善用 RNG 與 PRNG，正是讓密碼學既實用又安全的關鍵。

RNG：從類比世界取得熵#

隨機性來自環境——類比、混沌、不確定，因而不可預測。隨機性無法單靠電腦演算法產生。

在密碼學中，隨機性通常來自 RNG：一種軟體或硬體元件，利用類比世界的熵，在數位系統中產生不可預測的位元。例如 RNG 可能直接從溫度、聲學噪音、氣流擾動或電性靜電的測量中取樣位元。

遺憾的是，這類類比熵源並非隨時可得，而且它們的熵往往難以估計。

RNG 也可以從執行中的作業系統收割熵，來源包括：

  • 外接的感測器、I/O 裝置
  • 網路或磁碟活動
  • 系統日誌、執行中的行程
  • 使用者活動，例如按鍵與滑鼠移動

這類由系統與人產生的活動可以是不錯的熵源，但它們可能脆弱、可被攻擊者操縱，而且產生隨機位元的速度很慢。

量子隨機數產生器#

量子隨機數產生器（QRNG，quantum random number generators）是一類依賴量子力學現象所生隨機性的 RNG，例如放射性衰變、真空漲落，以及觀測光子的偏振。它們能提供真正的隨機性，而不只是表面上的隨機。

但實務上 QRNG 可能帶有偏差，產生位元的速度也不快。與前述熵源一樣，它們需要額外的元件才能可靠地高速產出。

PRNG：把少量真隨機擴張成大量偽隨機#

PRNG 解決了產生隨機性的難題：它從少量的真隨機位元，可靠地產生大量的人造隨機位元。

一個把滑鼠移動轉成隨機位元的 RNG，在你停止移動滑鼠時就停擺了；而 PRNG 只要被要求，永遠都會回傳偽隨機位元。

PRNG 依賴 RNG，但行為截然不同：

RNGPRNG
來源類比來源數位來源
速度相對慢快
決定性非決定性決定性
熵不保證高熵最大熵
產出真隨機位元看似隨機的位元

本質上，PRNG 把少量不可靠的隨機位元，轉換成一長串適合密碼應用的可靠偽隨機位元。

圖 2-1：RNG 從類比來源產生少量不可靠的位元，PRNG 把它們擴張成一長串可靠的位元

PRNG 如何運作#

PRNG 定期從 RNG 接收隨機位元，並用它們更新一塊大型記憶體緩衝區的內容，這塊緩衝區稱為熵池（entropy pool）。熵池之於 PRNG，就如同實體環境之於 RNG。當 PRNG 更新熵池時，會把池中的位元混合在一起，以協助消除統計偏差。

為了產生偽隨機位元，PRNG 執行一個確定性隨機位元產生器（DRBG，deterministic random bit generator）演算法，把熵池中的一些位元擴張成長得多的序列。

如其名所示，DRBG 是確定性而非隨機化的：給定同一個輸入，你永遠會得到同一個輸出。

PRNG 必須確保它的 DRBG 絕不會收到相同的輸入兩次，才能產生獨一無二的偽隨機序列。

三個操作#

PRNG 在運作過程中執行三個操作：

  • init()：初始化熵池與 PRNG 的內部狀態。它把 PRNG 重設為全新狀態、把熵池重新初始化為某個預設值，並初始化 PRNG 執行 refresh 與 next 時所用的變數與記憶體緩衝區。
  • refresh(R)：用某些資料 R（通常來自 RNG）更新熵池。這個操作常被稱為重新播種（reseeding），其引數 R 稱為種子（seed）。當沒有 RNG 可用時，種子可能是系統中硬編碼的唯一值。refresh 通常由作業系統呼叫。
  • next(N)：回傳 N 個偽隨機位元並更新熵池。它執行 DRBG 並修改熵池，以確保下一次呼叫會產生不同的偽隨機位元。next 通常由應用程式呼叫或請求。

安全考量：向前與向後#

PRNG 應該保證兩件事：

  • 回溯抗性（backtracking resistance，也稱前向保密／forward secrecy）：已經產生過的位元不可能被還原。
  • 預測抗性（prediction resistance，後向保密／backward secrecy）：未來的位元不可能被預測。

如何達成回溯抗性： PRNG 應確保 refresh 與 next 更新狀態時所做的變換是不可逆的。如此一來，即使攻擊者攻破系統、取得熵池的當前值，也無法判定池的先前值或先前產生的位元。

如何達成預測抗性： PRNG 應定期以攻擊者未知且難以猜測的 R 值呼叫 refresh，藉此防止攻擊者判定熵池的未來值——即使整個池已被攻破。

即使所用的 R 值清單已知，你仍需要知道 refresh 與 next 呼叫的順序，才能重建出熵池。

Fortuna#

Fortuna 是 Windows 使用的一種 PRNG 建構，最初由 Niels Ferguson 與 Bruce Schneier 於 2003 年設計。它取代了 Yarrow（Kelsey 與 Schneier 於 1998 年的設計），而 Yarrow 現在用於 macOS 與 iOS 作業系統。

內部記憶體#

  • 32 個熵池 P₁, P₂, ..., P₃₂，其中 Pᵢ 每 2ⁱ 次重新播種才使用一次。
  • 一把金鑰 K 與一個計數器 C（各 16 位元組），構成 Fortuna 之 DRBG 的內部狀態。

三個操作#

  • init()：把 K 與 C 設為零，並清空 32 個熵池 Pᵢ（i = 1...32）。
  • refresh(R)：把資料 R 附加到其中一個熵池。系統決定用哪些 RNG 產生 R 值，且應定期呼叫 refresh。
  • next(N)：用一個或多個熵池的資料更新 K，選哪些熵池主要取決於 K 已經被更新過幾次。接著以 K 為金鑰加密 C，產生所要求的 N 個位元；若加密 C 得到的位元不夠，Fortuna 就繼續加密 C + 1、C + 2，直到位元足夠。

實作陷阱#

Fortuna 的操作看起來相當簡單，但正確實作它很難。

  • 細節必須全對：熵池如何挑選、next 中該用哪種密碼、沒有收到熵時該如何反應等等。規格雖然定義了多數細節，卻沒有提供完整的測試套件來檢查實作是否正確，這使得你很難確保自己的 Fortuna 實作行為符合預期。

  • 即使實作正確也可能失敗：例如 Fortuna 可能察覺不到 RNG 未能產生足夠的隨機位元，結果就是產出品質較低的偽隨機位元，甚至完全停止供應。

  • 種子檔可能外洩：Fortuna 的種子檔用於在 RNG 尚不可用時（例如系統重開機後、系統 RNG 還沒記錄到任何不可預測事件之前）透過 refresh 呼叫餵入熵。但若同一個種子檔被用了兩次，Fortuna 會產生兩次相同的位元序列。因此種子檔用完後應被抹除，以確保不會被重複使用。

  • 共用種子檔的兩個實例會同步：若兩個 Fortuna 實例因共用種子檔而處於相同狀態（意味它們的熵池資料相同，包含相同的 C 與 K），那麼 next 操作在兩個實例中會回傳相同的位元。

密碼學 PRNG vs. 非密碼學 PRNG#

PRNG 分成密碼學用與非密碼學用兩種。

  • 非密碼學 PRNG 的設計目標是為科學模擬或電玩遊戲這類應用產生均勻分布。它們只關心位元機率分布的品質，不關心可預測性。
  • 密碼學 PRNG 則是不可預測的，因為它們同時也關心用來產出良好分布位元之底層運算的強度。

遺憾的是，多數程式語言暴露出來的 PRNG 都是非密碼學的：libc 的 rand 與 drand48、PHP 的 rand 與 mt_rand、Python 的 random 模組、Ruby 的 Random 類別等等。預設就用非密碼學 PRNG 是災難的配方，因為它經常最終被用在密碼應用裡。

案例：Mersenne Twister#

Mersenne Twister（MT）演算法是一個非密碼學 PRNG，在本書寫作時被 PHP、Python、R、Ruby 及許多其他系統採用。MT 會產生均勻分布、無統計偏差的隨機位元，但它是可預測的：給定 MT 產出的少數幾個位元，就很容易推出接下來會是哪些位元。

延伸：Mersenne Twister 為何不安全——線性的代價

MT 演算法比密碼學 PRNG 簡單得多。它的內部狀態是一個陣列 S，由 624 個 32 位元的字組成。這個陣列初始為 S₁, S₂, ..., S₆₂₄，並依下式演進為 S₂, ..., S₆₂₅，再到 S₃, ..., S₆₂₆，依此類推：

S(k+624) = S(k+397) ⊕ A( (S(k) ∧ 0x80000000) ∨ (S(k+1) ∧ 0x7fffffff) )

其中 ⊕ 是逐位元 XOR（C 語言的 ^），∧ 是逐位元 AND（C 的 &），∨ 是逐位元 OR（C 的 |）。A 是一個函式：若 32 位元字 x 的最高位元為 0，則轉換成 x >> 1；否則轉換成 (x >> 1) ⊕ 0x9908b0df。

關鍵觀察：S 的位元彼此之間只透過 XOR 互動。∧ 與 ∨ 從不把 S 的兩個位元結合在一起，只把 S 的位元與常數 0x80000000、0x7fffffff 的位元結合。

因此 S₆₂₅ 的任何位元都可以表示成 S₃₉₈、S₁、S₂ 之位元的 XOR，而任何未來狀態的任何位元，都可以表示成初始狀態 S₁, ..., S₆₂₄ 之位元的 XOR 組合。

由於初始狀態恰好有 624 × 32 = 19,968 個位元，任何輸出位元都可以表示成一個至多 19,969 項（19,968 個位元加一個常數位元）的方程式——大約只有 2.5 KB 的資料。反過來也成立：初始狀態的位元可以表示成輸出位元的 XOR。

線性即不安全#

我們把位元的 XOR 組合稱為線性組合（linear combination）。例如 X ⊕ Y ⊕ Z 是線性組合，而 (X ∧ Y) ⊕ Z 不是，因為其中有 AND。

  • 在 X ⊕ Y ⊕ Z 中翻轉 X 的一個位元，結果必定跟著改變，無論 Y 與 Z 的值為何。
  • 在 (X ∧ Y) ⊕ Z 中翻轉 X 的一個位元，只有當 Y 在同一位置的位元是 1 時，結果才會改變。

結論是：線性組合是可預測的，因為你不需要知道位元的值，就能預測它們的變動會如何影響結果。

相較之下，若 MT 演算法在密碼學上是強的，它的方程式就會是非線性的，不只涉及單一位元，還會涉及位元的 AND 組合（乘積），例如 S₁S₁₅S₁₈₂ 或 S₁₇S₂₅₆S₂₅₇S₃₅₄S₄₉₈S₆₀₁。這些位元的線性組合至多包含 624 個變數，非線性組合卻允許多達 2^624 個變數——這樣的方程式別說解了，連完整寫下來都不可能。（作為對照，2^305 這個小得多的數字，是可觀測宇宙的估計資訊容量。）

關鍵在於：線性變換導致短方程式（大小與變數數量相當），容易求解；非線性變換則導致指數級大小的方程式，實際上無法求解。密碼學家的任務，就是設計出只用少量簡單運算就能模擬這種複雜非線性變換的 PRNG 演算法。

線性只是眾多安全準則之一。非線性雖然必要，但單靠非線性並不能讓一個 PRNG 在密碼學上安全。

統計檢定的無用#

TestU01、Diehard 或美國國家標準暨技術研究院（NIST）的測試套件這類統計檢定套件，是檢驗偽隨機位元品質的一種方式。這些檢定取一份 PRNG 產出的偽隨機位元樣本（比方說 1 MB），計算位元中某些樣式分布的統計量，再與完美均勻分布下的典型結果比較。例如有些檢定會計算 1 位元與 0 位元的數量，或 8 位元樣式的分布。

但統計檢定與密碼學安全性大致無關，而且要設計出一個能騙過任何統計檢定的密碼學弱 PRNG 是完全可能的。

當你對隨機產生的資料執行統計檢定，通常會得到一堆統計指標，典型是 p 值（p-value）。這些結果不總是容易解讀，因為它們很少單純到只有「通過」或「失敗」。

若你的初步結果看起來異常，先別緊張：那可能是某種偶然的偏離，或是你測試的樣本太少。

要確認你看到的結果正常，請與同樣大小的可靠樣本做比較。例如用 OpenSSL 工具產生一份：

openssl rand <number of bytes> -out <output file>
Backward 熵：不確定性的度量 真實世界的 PRNG Forward