一千萬個為什麽

搜索

在理論上是否在實踐中使用了合理的偽隨機生成器?


據我所知,實際上偽隨機數生成的大多數實現使用諸如線性移位反饋寄存器(LSFR)或這些“Mersenne Twister”算法之類的方法。雖然他們通過了許多(啟發式)統計測試,但沒有理論上保證它們看起來是偽隨機的,比如所有有效可計算的統計測試。然而,這些方法在各種應用中被不加選擇地使用,從加密協議到科學計算再到銀行業務(可能)。我覺得有點令人擔憂的是,我們幾乎無法保證這些應用程序是否按預期工作(因為任何類型的分析都可能假設真正的隨機性作為輸入)。

另一方面,復雜性理論和密碼學提供了非常豐富的偽隨機性理論,我們甚至有偽隨機生成器的候選構造,這將使用候選單向函數欺騙您可以提出的任何有效的統計測試。

我的問題是:這個理論是否已經實踐了?我希望對於隨機性的重要用途,例如密碼學或科學計算,使用理論上合理的PRG。

順便說一句,我可以找到一些有限的分析,當使用LSFR作為隨機源時,快速排序等流行算法的效果如何,並且顯然它們運行良好。請參閱Karloff和Raghavan的“隨機算法和偽隨機數”

最佳答案

“理論上合理的”偽隨機生成器的概念並沒有很好地定義。畢竟,沒有偽隨機生成器具有安全性證明。我不知道我們可以說基於分解大整數的硬度的偽隨機生成器比使用AES作為偽隨機生成器“更安全”。 (事實上​​,有一種感覺它不太安全,因為我們知道量子因子算法而不是量子算法來打破AES。)

我們所做的數學證明是各種合成結果,說如果你以某種方式組合塊密碼或散列函數,你可以獲得偽隨機生成器或偽隨機函數。一些此類結果在實踐中被廣泛使用,例如 HMAC 。但是,實現PRG的結果並且假設基本組件是一個普通的單向函數而開始的結果確實不足以用於應用程序(這至少部分是inherent )。因此,通常我們需要假設PRG /流密碼/塊密碼/散列函數作為基本原語,並開始從中構建其他內容。這個問題實際上並不是漸近分析,因為基本上所有加密減少(萊文的普遍PRG除外)都可以具體化,因此在具體假設下給出具體的保證。

但即使它們不是基於單向函數,也有一種感覺,即AES等結構在“理論上是合理的”,因為: (1)有關於其安全性的正式猜想。 (2)有人試圖反駁這些猜想,並從中得出啟示。

事實上,人們都知道,對於許多應用來說,使用不滿足上述(1)和(2)的PRFR(例如LSFR)並不明智。

轉載註明原文: 在理論上是否在實踐中使用了合理的偽隨機生成器?

猜你喜歡