密碼學安全偽亂數生成器

各種亂數和各類亂數生成器之間的關係

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

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

隨機性

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

統計學偽隨機性

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

密碼學安全偽隨機性

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

可忽略函式

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

真隨機性

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

開放問題

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

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

相關條目

• 亂數
• 偽亂數生成器
• 可忽略函式，幫助理解「非顯著大於1/2」這一概念。
• 多項式函式、反函式，幫助理解多項式時間和多項式函式的概念。
• 單向函式