密碼學安全偽亂數生成器- 維基百科 - Wikipedia

密碼學安全偽亂數生成器（亦作密碼學偽亂數生成器，英文：Cryptographically secure pseudo-random number generator，通稱CSPRNG），是一種能夠通過運算得出密碼學 ... 密碼學安全偽亂數生成器 維基百科，自由的百科全書 跳至導覽 跳至搜尋 各種亂數和各類亂數生成器之間的關係 密碼學安全偽亂數生成器（亦作密碼學偽亂數生成器，英文：Cryptographicallysecurepseudo-randomnumbergenerator，通稱CSPRNG），是一種能夠通過運算得出密碼學安全偽亂數的偽亂數生成器。

相較於統計學偽亂數生成器和更弱的偽亂數生成器，CSPRNG所生成的密碼學安全偽亂數具有額外的偽隨機屬性。

[1] CSPRNG常被作為密碼學原件，用以搭建更複雜的密碼學應用。

如，可變長CSPRNG和XOR函式搭配即構成串流加密法的編解碼方法。

目次 1隨機性 1.1統計學偽隨機性 1.2密碼學安全偽隨機性 1.2.1可忽略函數 1.3真隨機性 2開放問題 3相關條目 4註解 5參考 隨機性[編輯] 密碼學領域的隨機性一般分為如下三類： 統計學偽隨機性[編輯] 隨機位元序列符合在統計學的隨機的定義。

符合該定義的位元序列的特點是，序列中「1」的數量約等於「0」的數量；同理，「01」、「00」、「10」、「11」的數量大致相同，以此類推。

符合該類別的亂數生成方法的例子有線性同餘偽亂數生成器。

密碼學安全偽隨機性[編輯] 除了滿足統計學偽隨機性外，還需滿足「不能通過給定的隨機序列的一部分而以顯著大於 1 2 {\displaystyle{\frac{1}{2}}} 的概率[注1]在多項式時間內演算出位元序列的任何其他部分」。

符合該類別的密碼學安全偽亂數生成器的例子如Trivium(演算法)中的CSPRNG部分、SHA-2家族函式和計數器亦可被繫結以構建類似強度的CSPRNG。

可忽略函式[編輯] 由可忽略速度增長的函式是可忽略函式。

可忽略函式的更準確的定義如下：當輸入趨近於無窮大時，一個函式的增長速度小於任何多項式函式的反函式，則該函式是可忽略函式。

換言之， lim x → ∞ μ ( x ) p o l y ( x ) = 0 {\displaystyle\lim_{x\to\infty}{\mu(x)\overpoly(x)}=0} 。

比如說，我們知道，在輸入趨近於無窮大時，任何指數函式的增長速度大於任何多項式函式，因此，任何指數函式的反函式的增長速度一定小於任何多項式函式的反函式。

指數函式的反函式是對數函式，因此，所有的對數函式都是可忽略函式。

真隨機性[編輯] 除滿足以上兩點，還需要具備「不可重現性」。

換言之，不能通過給定同樣的資料而多次演算出同一串位元序列。

由於電腦演算法均具備確定的特性，所以真亂數無法由演算法來生成。

[1]真亂數的例子有放射性物質在某一時間點的衰變速度、某一地區的本底輻射值[注2]、正確使用設計良好的骰子所獲得的輸出等。

開放問題[編輯] CSPRNG本質上屬於一種單向函式。

一個可用的CSPRNG必須要滿足給定種子易於計算輸出，而給定輸出無法容易地計算種子。

但是，由於從種子到輸出的變換是容易的，因此檢查一個種子的正確性是非常容易的。

換言之，一個設計良好的CSPRNG從輸出求種子的問題必須是NP問題，但必須不是P問題。

由於在數學上面，P=NP與否是尚未有定論的難題，因此設計良好的CSPRNG是否存在是一個開放性問題。

如果有一天P=NP得到證明，那麼，「輸出求種子的問題必須是NP問題，但必須不是P問題」這一條件就無法滿足，這直接導致CSPRNG不再存在，也導致依賴強壯CSPRNG的所有密碼學應用的強壯性不復存在。

相關條目[編輯] 亂數 偽亂數生成器 可忽略函式，幫助理解「非顯著大於1/2」這一概念。

多項式函式、反函式，幫助理解多項式時間和多項式函式的概念。

單向函式 註解[編輯] ^顯著大於1/2定義為，大於1/2的部分是一個關於CSPRNG的可能的內部狀態的數量的以可忽略速度增長的函式的輸出。

所有的CSPRNG在執行時均具有被稱為「內部狀態」的資料，這部分資料的作用之一是保證了在一定輸出範圍內，CSPRNG「知道」自己走在哪一步上，以避免其輸出重複的值，從而破壞偽隨機性。

如果CSPRNG的可能的內部狀態過少，敵手（攻擊者）將可以通過窮舉內部狀態並與位元序列匹配，得到CSPRNG的輸出。

由於可變長CSPRNG內部狀態的下一狀態步進演算法一般為固定且公開的，一旦敵手獲知CSPRNG在某一時間點的內部狀態，就（至少）可以演算出其之後的狀態。

這與「不能通過給定的隨機序列的一部分演算出其他部分」這一定義相衝突。

因此內部狀態過少的偽亂數生成器往往不在討論範圍中。

^這是一個簡化的說法。

實際上，只有放射性物質在某一時刻的衰變概率恰好為0.5時，其衰變資料才是真亂數。

如果衰變概率不為0.5，那麼就可以通過統計歷史位元序列來猜測下一時間段中衰變發生的可能性，導致位元流可被預測。

參考[編輯] ^1.01.1JonathanKatzandYehudaLindell,現代密碼學——原理與協定(IntroductiontoModernCryptography:PrinciplesandProtocols),ISBN9787118070651 閱論編密碼學 密碼學歷史 密碼分析 密碼學主題列表 對稱密鑰加密 區塊加密法 串流加密法 公開金鑰加密 密碼雜湊函式 訊息鑑別碼 亂數 隱寫術 分類 主題 專題 取自「https://zh.wikipedia.org/w/index.php?title=密码学安全伪随机数生成器&oldid=71884810」 分類：​密碼算法密碼學密碼原語偽隨機數生成器隱藏分類：​使用ISBN魔術連結的頁面有藍鏈卻未移除內部連結助手模板的頁面 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他語言 DeutschEnglishEspañolفارسیעבריתItaliano日本語PortuguêsРусскийShqipУкраїнська 編輯連結