偽隨機函式的統計檢驗
假設我有一個潛在的 Pseudo-Random 函式的實現，並且我想測試我的實現是否至少不包含任何明顯的缺陷。據我了解，在其他加密設置中，使用統計測試來確保加密算法的正確性。我可以對偽隨機函式使用什麼樣的統計測試？
沒有人使用通用統計測試來驗證加密算法的正確性。
- 為了驗證實現的正確性，工程師為他們的程式碼編寫正確性證明，在已知答案測試中執行它，確認隨機輸入的往返等。
這些都不涉及統計測試，因為重點是實現一個特定的數學函式，而不是從分佈中隨機抽樣——事實上，如果你確實使用了通用統計測試，你必須決定在誤報的情況下該怎麼做，這將是一種荒謬的方法來驗證實現確定性數學函式的軟體。
- 為了評估密碼系統的安全性，密碼學家研究專門的統計測試。
假設，按照 Kerckhoffs 的建議，對手知道系統，他們能做的最好的事情是用這些知識來攻擊它？ 通用統計測試，例如 $ \chi^2 $ 測試是愚蠢的，因為他們甚至不知道系統。 例如，下面是一個測試，用於區分統一隨機密鑰下的 256 位 AES-CTR 流和統一隨機 256 位字元串：
- 猜一個關鍵 $ k $ 均勻隨機。
- 檢查字元串是否 $ s = s_1 \mathbin| s_2 $ 是形式 $ \operatorname{AES}_k(0) \mathbin| \operatorname{AES}_k(1) $ . 如果是，猜AES-CTR；如果不是，請猜測統一隨機。
該測試具有顯著優勢 $ 2^{-256} $ （或者 $ 2^{-128} $ 如果您使用 AES-128 而不是 AES-256，我不推薦$$ 1 $$)，因此 AES的最佳區分優勢不能比 $ 2^{-256} $ ，但是很多聰明的密碼分析家還沒有找到比這更好的方法。顯然，你可以花費更多的計算——嘗試兩次，使用兩個不同的鍵 $ k_1 $ 和 $ k_2 $ ——為了線性提高優勢，所以這個數字應該用成本因素來限定。任何假定的偽隨機函式族都應該伴隨著一大群密碼分析家的紙屑，證明未能找到比通用的區分器更好，或者帶有將 PRF 的安全性與某些基礎原語的安全性相關的定理證明。 例如，任何區分器都可以獲得針對 AES 的最佳 PRF 優勢 $ q $ 查詢受到AES的最佳PRP優勢的限制，密碼分析家已經研究了幾十年，加上 $ q(q - 1)/2^{129} $ 因為AES總是一個排列。
所以，把你的通用統計測試扔進垃圾箱。查找關於假定 PRF 的文獻。編寫程式碼正確性的證明。
你是對的。隨機流應該與加密良好的流相同。要測試它，您可以通過它傳遞一個普通的計數器，如 $ F(counter) $ . 輸出應該是偽隨機的。因此，所有 RNG 的第一個停靠港應該是
ent. 很少有“簡單”的設計錯誤可以欺騙耳鼻喉科測試。您最多可以測試 2GB 的數據，典型的通過結果是：-Entropy = 8.000000 bits per byte. Optimum compression would reduce the size of this 1073741824 byte file by 0 percent. Chi square distribution for 1073741824 samples is 271.72, and randomly would exceed this value 22.54 percent of the times. Arithmetic mean value of data bytes is 127.5000 (127.5 = random). Monte Carlo value for Pi is 3.141575564 (error 0.00 percent). Serial correlation coefficient is -0.000034 (totally uncorrelated = 0.0).請注意，您需要至少 500kB 的數據才能使結果有意義。這個例子是來自 /dev/urandom 的 1GB。在您的函式演進的這一點上，另一種選擇是作為Rng-tools套件的一部分的 FIPS 140-2 RNG 測試。它以 20kb 的塊為單位對它們進行測試。很有可能你會知道 $ F $ 在這個階段。
之後，您可以進行更全面的測試，例如 TestU01、Diehard(er)、NIST SP 800-22 等。請注意所需的樣本量，因為某些測試可能非常貪婪，而 Dieharder 就是一個很好的例子. 值得注意的是，您應該預料到某些測試會失敗。不要絕望，因為隨機性是令人討厭的。
您可能還想查看雪崩效應及其計算。這很簡單（基於異或隨機數），如果 $ F $ 正在工作，你會得到一個以 50% 為中心的正常圖形，例如：-
與（以位為單位） $ \sigma = \frac{\sqrt{block width}}{2} $ . 正如我尊敬的朋友所指出的，統計測試並不能解決所有主要安全方面的問題 $ F $ . 但是，它解決了一些問題，並且確實對您的算法機制進行了很好的檢查。
