密碼學安全偽隨機數生成器

密碼學安全偽隨機數生成器（亦作密碼學偽隨機數生成器，英文：Cryptographically secure pseudo-random number generator，通稱CSPRNG），是一種能夠通過運算得出密碼學安全偽隨機數的偽隨機數生成器。相較於統計學偽隨機數生成器和更弱的偽隨機數生成器，CSPRNG所生成的密碼學安全偽隨機數具有額外的偽隨機屬性。^[1]

CSPRNG常被作為密碼學原件，用以搭建更複雜的密碼學應用。如，可變長CSPRNG和XOR函數搭配即構成流密碼的編解碼方法。

隨機性

密碼學領域的隨機性一般分為如下三類：

統計學偽隨機性

隨機比特序列符合在統計學的隨機的定義。符合該定義的比特序列的特點是，序列中「1」的數量約等於「0」的數量；同理，「01」、「00」、「10」、「11」的數量大致相同，以此類推。符合該類別的隨機數生成方法的例子有線性同餘偽隨機數生成器。

密碼學安全偽隨機性

除了滿足統計學偽隨機性外，還需滿足「不能通過給定的隨機序列的一部分而以顯著大於 ${\frac {1}{2}}$ 的概率^{[注 1]}在多項式時間內演算出比特序列的任何其他部分」^{[注 2]}。符合該類別的密碼學安全偽隨機數生成器的例子如Trivium (算法)中的CSPRNG部分、SHA-2家族函數和計數器亦可被綁定以構建類似強度的CSPRNG。

可忽略函數

由可忽略速度增長的函數是可忽略函數。可忽略函數的更準確的定義如下：當輸入趨近於無窮大時，一個函數 $\mu :\mathbb {R} \to \mathbb {R}$ 的輸出小於任何多項式函數的反函數，則該函數是可忽略函數。換言之， $\lim _{x\to \infty }{|\mu (x)|-{\frac {1}{|poly(x)|}}}<0$ 。比如說，我們知道，在輸入趨近於無窮大時，任何指數函數的增長速度大於任何多項式函數，因此，任何指數函數的反函數的增長速度一定小於任何多項式函數的反函數。指數函數的反函數是對數函數，因此，所有的對數函數都是可忽略函數。

真隨機性

除滿足以上兩點，還需要具備「不可重現性」。換言之，不能通過給定同樣的數據而多次演算出同一串比特序列。由於計算機算法均具備確定的特性，所以真隨機數無法由算法來生成。^[1]真隨機數的例子有放射性物質在某一時間點的衰變速度、某一地區的本底輻射值^{[注 3]}、正確使用設計良好的骰子所獲得的輸出等。

開放問題

CSPRNG本質上屬於一種單向函數。一個可用的CSPRNG必須要滿足給定種子易於計算輸出，而給定輸出無法容易地計算種子。但是，由於從種子到輸出的變換是容易的，因此檢查一個種子的正確性是非常容易的。換言之，一個設計良好的CSPRNG從輸出求種子的問題必須是NP問題，但必須不是P問題。

由於在數學上面，P = NP與否是尚未有定論的難題，因此設計良好的CSPRNG是否存在是一個開放性問題。如果有一天P = NP得到證明，那麼，「輸出求種子的問題必須是NP問題，但必須不是P問題」這一條件就無法滿足，這直接導致CSPRNG不再存在，也導致依賴強壯CSPRNG的所有密碼學應用的強壯性不復存在。

註解

^ 顯著大於1/2定義為，大於1/2的部分是一個關於CSPRNG的可能的內部狀態的數量的以可忽略速度增長的函數的輸出。所有的CSPRNG在運行時均具有被稱為「內部狀態」的數據，這部分數據的作用之一是保證了在一定輸出範圍內，CSPRNG「知道」自己走在哪一步上，以避免其輸出重複的值，從而破壞偽隨機性。如果CSPRNG的可能的內部狀態過少，敵手（攻擊者）將可以通過窮舉內部狀態並與比特序列匹配，得到CSPRNG的輸出。由於可變長CSPRNG內部狀態的下一狀態步進算法一般為固定且公開的，一旦敵手獲知CSPRNG在某一時間點的內部狀態，就（至少）可以演算出其之後的狀態。這與「不能通過給定的隨機序列的一部分演算出其他部分」這一定義相衝突。因此內部狀態過少的偽隨機數生成器往往不在討論範圍中。
^ 如果不能以顯著大於1/2的概率計算出比特序列的任何其他部分，那麼就說明無法以顯著大於1/2的概率計算出任何一個其他位置的比特，因此保證每一個比特位都無法在沒有密鑰的情況下僅通過計算得到。
^ 這是一個簡化的說法。實際上，只有放射性物質在某一時刻的衰變概率恰好為0.5時，其衰變數據才是真隨機數。

參考

^ ^1.0 ^1.1 Jonathan Katz and Yehuda Lindell, 現代密碼學——原理與協議 (Introduction to Modern Cryptography: Principles and Protocols), ISBN 9787118070651

[2] 顯著大於1/2定義為，大於1/2的部分是一個關於CSPRNG的可能的內部狀態的數量的以可忽略速度增長的函數的輸出。所有的CSPRNG在運行時均具有被稱為「內部狀態」的數據，這部分數據的作用之一是保證了在一定輸出範圍內，CSPRNG「知道」自己走在哪一步上，以避免其輸出重複的值，從而破壞偽隨機性。如果CSPRNG的可能的內部狀態過少，敵手（攻擊者）將可以通過窮舉內部狀態並與比特序列匹配，得到CSPRNG的輸出。由於可變長CSPRNG內部狀態的下一狀態步進算法一般為固定且公開的，一旦敵手獲知CSPRNG在某一時間點的內部狀態，就（至少）可以演算出其之後的狀態。這與「不能通過給定的隨機序列的一部分演算出其他部分」這一定義相衝突。因此內部狀態過少的偽隨機數生成器往往不在討論範圍中。

[3] 如果不能以顯著大於1/2的概率計算出比特序列的任何其他部分，那麼就說明無法以顯著大於1/2的概率計算出任何一個其他位置的比特，因此保證每一個比特位都無法在沒有密鑰的情況下僅通過計算得到。

[4] 這是一個簡化的說法。實際上，只有放射性物質在某一時刻的衰變概率恰好為0.5時，其衰變數據才是真隨機數。

[Katz-1] 1.0 ^1.1 Jonathan Katz and Yehuda Lindell, 現代密碼學——原理與協議 (Introduction to Modern Cryptography: Principles and Protocols), ISBN 9787118070651

[1]

[注 1]

[注 2]

[注 3]