Randomness

我在哪裡可以找到具有已知熵的數據樣本,以了解 NIST SP 800-90B 在其上的表現如何?

  • January 23, 2021

我想要一個來自具有已知熵的源的真實隨機數據樣本。甚至產生足夠數量的真正隨機數據都不容易——更不用說知道源的熵了。例如,我獲取真正隨機數據的唯一機會是等待/dev/random.

我正在旋轉我的硬碟驅動器並儘可能地使用系統來為核心提供足夠的熵。同時,我正在收集高達 1,000,000 的數據以滿足 NIST SP 800-90B,因為我想使用最先進的熵估計來估計 /dev/random 的熵。(我知道 NIST SP 800-90B 存在各種問題,但我沒有發現任何更好的東西,已經得到了科學界的適當審查。)

我如何旋轉我的系統?

$ while true; do sudo find /; done

我如何收集數據?

$ cat /dev/random >> random.bit

為什麼我不快速收集它/dev/urandom?因為那沒有意義。我想估計熵。我不會從使用 PRNG 處理真正的隨機數據中獲得更多的熵。據我所知,使用 PRNG 可能只會讓估計者更難。(對此有什麼想法嗎?)

您是否知道任何具有尊重熵估計的隨機數據樣本,我可以使用它來查看 NIST SP 800-90B 在它上的表現如何?是否有任何工作可以說明 Linux 的熵/dev/random

這個問題確實要求從具有已知熵率**的源中獲取數據樣本。


我建議從最簡單的開始:熵率為零的源。可以輕鬆獲得前兆字節的範例:

  • 僅在零處產生字節的源。
  • 一個源增量循環超過 256 個字節。
  • 由長度增加的字節串的 SHA-256 散列組成的源,按字典順序排列。
  • /dev/random/dev/urandom修改為用零替換其內置 PRNG 的輸入。
  • 產生字節的源 $ \pi $ (例如使用貝拉德的方法)。

NIST SP 800-90B 測試無助於將最後三個與具有一定熵的源區分開來。這說明這些(或類似的)測試即使完全沒有熵也不能可靠地檢測到,除非對源的性質做出一些假設。


我們可以使用輕度調節的光源。很容易用麥克風在發出噪音的東西前面製作一個(風扇會做),由 ADC 採樣(PC 的聲音輸入會做),以及通過一些光照條件饋送的一些樣本的字節(比如: 團體 $ n $ 16 位採樣並輸出模 256 的和 $ 2n $ 字節)。這更適合 NIST SP 800-90 的設計用途。看看麥克風前置放大器的增益,麥克風的位置和參數會很有趣 $ n $ ,都影響結果。不過,這個來源沒有已知的熵率。


我們可以製造一個具有偏差但(可能)獨立字節和已知偏差分佈的源,導致(至多)一個肯定已知的熵。一種方法是採用/dev/urandom(或任何輸出無法與完美的真正隨機源區分的源),將字節按兩個分組以形成整數 $ [0\ldots2^{16}) $ , 並輸出它的高位字節,除非整數小於 $ k $ , 對於某個參數 $ k\in[0\ldots2^8] $ . 這導致具有字節零的源具有機率 $ (2^8-k)/(2^{16}-k) $ , 和其他 $ 2^8/(2^{16}-k) $ . 位/字節的熵很容易計算為 $ k $ ,然後去(對於 $ k $ 取決於 $ 100 $ ): 位/字節熵

在實踐中,你不會從這個練習中學到任何東西。NIST SP 800-90B 中的熵猜測方法,即使它們是最先進的,也很容易被愚弄。可以安全地假設源的真實熵並不比這些測試告訴你的高很多,但它很容易低得多。即使是像 Mersenne twister 這樣的非加密 PRNG 的輸出,以 0 或目前 POSIX 時間為種子,也可能通過所有測試。

如果您有 Kolmogorov 複雜性預言機,將 /dev/random 或 RAND 百萬位數的輸出提供給它以查看其他分析可能遺漏的內容會很有趣。但是詢問 Kolmogorov 預言和現實世界的熵猜測算法之間的區別就像詢問上帝和你六歲的孩子之間的區別一樣。

引用自:https://crypto.stackexchange.com/questions/84219