RNG 未能通過 NIST SP800-22 重新啟動測試？

我有硬體 RNG 生成的 1,000,000 字節的數據樣本。該設備通過了 ENT 測試套件、NIST SP800-22、DIE HARDER 和 TestU01 的認證。

我已經通過 SP800-90B_EntropyAssessment ( github.com/usnistgov/SP800-90B_EntropyAssessment ) 測試了我的樣本。最小熵估計是7.88237在我執行重新啟動測試之後。

我的範例在重新啟動測試時失敗，程序顯示

驗證失敗，未授予熵估計。

“NIST SP 800-90B 中熵估計器的分析和改進” (PDF) 說

隨機性具有三個特徵：不可預測性、無偏性和不可重複性，並且不可重複性通過重啟測試來驗證。

我想知道我的 RNG 是否未能通過重新啟動測試，這是否意味著它根本沒有提供熵？

失敗的測試似乎是NIST SP 800-90B (2 nd Draft)的 3.1.4 (Restart Tests) 中的一個，特別是 3.1.4.3 (Sanity Check - Most Common Value in the Rows and Columns)，失敗於

546 如果F大於U，則測試失敗。

不能斷定一個失敗的生成器根本沒有熵。很可能是它有一些缺陷，但仍會輸出相當數量的熵，使其完全可用於播種 CSPRNG。

注意：此測試需要通過重新啟動源並收集 1000 個符號獲得 1000 個樣本。如果問題的 10 6個字節是由硬體 RNG 生成而沒有重新啟動它，那麼測試被濫用（如果它成功了，那將毫無意義）。但這種濫用不能成為測試失敗的原因。

---

RNG 的輸出失敗是一個常見的事件Randomness Rest。四種原因的任意組合都可能發生這種情況：

1. 使用Randomness Rest（或收集RNG 的輸出，但鑑於其他測試已通過，這不太可能）；例如， RNG 輸出的格式、大小..與所使用參數的Randomness Rest不同。可能性是無止境。這被診斷為3。
2. 厄運。所有有用的隨機性測試都應該有一定的誤報率，有一定的機率：任何好的測試記錄的 P 值。我的讀數是 1%。假設這一點，如果可能的話，使用相同的參數重新執行Randomness Rest，以及一些新的 RNG 輸出。如果接下來的兩個測試失敗，我們可以很有信心地排除厄運。否則（即如果某些成功），我們可以懷疑運氣不好（或 1.），我們應該使用表單順序分析決定。作為一個粗略的近似值：再執行 997 個測試，計算 1000 個失敗的測試數量（應該在 10 的數量級），如果超過 27 個，則高度自信地拒絕壞運氣（仍然懷疑一些問題並徹底調查如果超過 15）。
3. 隨機性測試中的錯誤（無論是實施，還是定義，如果那是草稿或沒有經過嚴格審查）。檢測這一點的一般方法是對由簡單（因此希望正確且可以接受的快速）CSPRNG（下面給出一個）生成的文件執行*隨機性測試。*失敗的比例應該與記錄的 P 值有關。
4. 有缺陷的 RNG。在消除所有其餘部分後得出結論。

---

這是一個簡單的偽隨機序列生成器：

// Simple generator of cryptographically secure pseudorandom sequence.
// The 64-bit block cipher TEA is used in CFB mode to encipher
// plaintext consisting of the block number.
#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>

// For a different sequence, change these arbitrary 32-bit constants,
// used as key for the TEA block cipher.
// Note: in David Wheeler and Roger Needham's TEA, each key has 3 other
// equivalents, as the high-order bits of K0/K1 and K2/K3 cancel out.
#define K0 0x7638d4f2
#define K1 0xabe32749
#define K2 0x56b81d0e
#define K3 0x4ed51d62

// output size, multiple of 8
#define OUTPUT_SIZE 1000000

int main(void) {
   uint32_t j, n, s, y=0, z=0;
   for( j=0; j < (OUTPUT_SIZE+7)>>3; ++j ) {
       s = 0;
       n = 32; do { // 32 pairs of rounds
           s += 0x9e3779b9;
           y += ((z<<4)+K0) ^ (z+s) ^ ((z>>5)+K1);
           z += ((y<<4)+K2) ^ (y+s) ^ ((y>>5)+K3);
       } while (--n);
       z ^= j; // CFB; makes short cycles virtually impossible
       // portably format in lowercase hexadecimal
       printf("%08"PRIx32"%08"PRIx32, y, z);
   }
   return 0;
}

// Generates one million octets expressed as two million characters
// in lower-case hexadecimal on standard output; when expressed in
// ASCII as two million octets, their hash per SHA-256 is
// d5b727ef6a9177c897b68085d60a7660f6f6b1dbf09cb7e91fe59da3a66d4e2d

引用自：https://crypto.stackexchange.com/questions/52405