Randomness

字節順序在 NIST SP800-22 測試中是否重要?

  • October 1, 2021

我對隨機性測試套件很好奇。

著名的隨機性測試套件之一 DIEHARDER表示,字節序對於“好的”隨機生成器並不重要。

請注意,這與編寫原始浮點數不同(作為比特流根本不會是隨機的),並且 uint 的“字節順序”對於“好”生成器的零假設應該無關緊要,作為隨機字節以任何順序隨機。

只是一個粗略的猜測,我認為在隨機性測試中 Big-endian 和 Little-endian 沒有區別。因為隨機性測試是關於計算 0 或 1 的數量,檢查比特流的模式等(我閱讀了整篇論文,NIST SP800-22 修訂版 1a。)

但是 NIST SP800-22 中沒有書面文件表明“字節序不影響隨機性測試的目的”。

問題。

  1. NIST SP800-22 論文中是否有任何遺漏的部分說“字節順序無關緊要”?
  2. 我可以在不考慮字節序的情況下測試隨機性嗎?

為什麼我得到這個問題。

Dieharder 輸入文件data/data.pi和帶有 ASCII 字元的 NIST SP800-22 輸入文件有很好的範例。

而且我還發現 Dieharder 將文件(ASCII)讀取為 Little-Endian,NIST 將文件(ASCII)讀取為 Big-Endian。你可以在 stackoverflow 中看到我是如何發現的

但是,由於字節順序,我必須製作兩個輸出文件。一種是大端,另一種是小端。這可能會浪費時間和記憶體。所以我想知道“Endianness 在 NIST SP800-22 測試套件中是否重要?”

Endianness¹ 可以影響隨機性測試的結果,並將結果從通過更改為失敗,反之亦然(拋出不同的生成器執行可能會產生相同的效果,但程度要小一些)。但是,如果字節序顯著影響測試的結果,那麼(假設測試是正確的並且正確使用)

  • 生成器壞了,因為其中一個 to 版本明顯未能通過測試,並且生成器輸出處的任何固定位交換與隨機無法區分會產生與隨機無法區分的生成器
  • 並且測試對其輸入的輕微重新排序很敏感,這表明測試過度專業化。

因此,我的建議是忽略隨機測試輸入中的字節順序問題。

相反,質疑執行 Dieharder 或 NIST SP800-22 的動機。這在不合標準的加密論文中很常見,尤其是那些直覺地說明加密對Lena做了什麼的論文。但是這種測試的成功並不是對某些加密或 PRNG 或包含後處理狀態的 TRNG 質量的爭論或(更糟糕的證明/展示)。為此,有必要對 TRNG 的加密、PRNG 或源+後處理中使用的方法進行分析。


¹ 那是在測試的生成器的輸出和/或測試程序的輸入處以字節、字或整數為單位的大端、小端或其他端的位順序。例如,NIST Statistical Test Suite 的函式(此處convertToBits為文件 src/utilities.c )根據大端約定將字節轉換為位(與非同步串列通信中最常見的順序相反)。如果在數學上定義為輸出比特流(例如A5-1)的生成器的實現在字節模式下通過該測試以提高效率,那麼這在理論上很重要。

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