我的隨機數真的“壞”還是“必須”不時發生的統計效應？
我的軟體使用作為 MCU 一部分的 TRNG（熵源）。
測試機構對我的軟體生成的隨機數進行了檢查，發現了一個問題，我現在必須檢查：
他們針對 NIST 測試套件執行我的隨機數： https ://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf
非重疊模板匹配測試失敗。
它正在尋找隨機字元串中給定位序列的出現次數，並將這些數字與期望值進行比較。測試統計 $ \chi^2 $ 是一種度量，觀察到的數字與預期的出現次數的匹配程度。
大量的 N*M 位被分成 N 塊，每 M 位。該圖案的長度為 m。
命中的平均值是
$ \mu = \frac{M-m+1}{2^m} $
變異數
$ \sigma^2 = M (\frac{1}{2^m} - \frac{2 m - 1}{2^{2m}}) $
檢驗統計量為
$ \chi^2 (obs) = \sum_{i=1}^{N} \frac{(W_i-\mu)^2}{\sigma^2} $
i 遍歷所有 N 個塊並且 $ W_i $ 表示塊 i 中的匹配數。
p 值為
$ p = 1-\Gamma_{inc}(\frac{N}{2}, \frac{\chi^2 (obs)}{2}) $ 在哪裡 $ \Gamma_{inc} $ 是不完全伽馬函式。
如果計算的 P 值 < 0.01，則斷定該序列是非隨機的。
我自己實現了這個測試，並獲得了 80,000 個隨機字節的測試執行：
N=8, M=80000
一個好的模式是：
expected occurrences of 1110000 in random binary of length 80000:624 W[0]:657 W[1]:633 W[2]:620 W[3]:608 W[4]:659 W[5]:610 W[6]:607 W[7]:628 OK: P=0.697173010616大多數模式都很好，但有些模式非常糟糕，例如：
expected occurrences of 1110110 in random binary of length 80000:624 W[0]:554 W[1]:618 W[2]:715 W[3]:648 W[4]:602 W[5]:619 W[6]:683 W[7]:611 *****NOT OK: P=0.000101720454752或者
expected occurrences of 11000100 in random binary of length 80000:312 W[0]:310 W[1]:352 W[2]:297 W[3]:325 W[4]:332 W[5]:376 W[6]:327 W[7]:318 *****NOT OK: P=0.00404698900088現在的問題：
當我解釋 P 值時，它是在給定序列是隨機的情況下獲得觀察到的測試統計數據的機率。所以 P=0.000101720454752極不可能，所以測試失敗。
最有趣的是，當我將塊大小增加 10 倍時（800,000 個隨機字節）
N=8, M=800000
我在所有模式上都得到了很好的結果。
現在它的真正含義是什麼？我的隨機數真的“壞”還是“必須”不時發生的統計效應？無論如何，測試失敗…
為什麼十倍數據集可以？
我將不勝感激任何評論。謝謝。
問題中討論的失敗測試之一是為此目的而編碼的。使用已知良好的偽隨機源（SHA-256 的增量值輸出合格）驗證程式碼可能很有用。如果它經常失敗，則程式碼需要修復！測試的定義很複雜，例如在2.7.4 (2)中定義瞭如何計算所搜尋模式的出現次數，並且可能會出現錯誤。
但是我無法想像給出所觀察到的錯誤，並且（在解決了關於對參考測試案例沒有影響的不完整伽馬函式定義的問題，以及我的一個錯字之後）我確認問題的 P -values 匹配問題的計數。
對於這些結果（尤其是第二個測試案例，P 值 < 1/9830），必須至少滿足以下條件之一：
- 生成器的輸出與隨機（我的猜測）有很大區別；
- 這是一個嚴重的倒霉案例（糟糕的程度很大程度上取決於選擇了多少次測試，顯示的失敗案例，見下文）；
- 問題的計數以一種奇怪的、不規則的方式有些錯誤；
- 參考文獻中的數學非常糟糕（但我想這是眾所周知的）。
重要的是：測試似乎以多種模式執行。在這種情況下，應該降低被認為失敗的 P 值門檻值（例如，除以測試次數）；或者最好，應該聚合 P 值。對於聚合，我們可以使用Fisher 方法。從理論上講，這需要將測試視為獨立的，如果樣本 RNG 輸出從未使用多種模式進行測試，就會出現這種情況。從業者偶爾會不那麼小心，但這很少會改變遊戲規則。
注意：參考僅略過選擇 P 值門檻值的問題（注意 $ \alpha $ )，並且沒有說明如何確定多個測試的總體結果是通過還是失敗。它甚至對如何解釋 P 值做出了高度誤導性的陳述，例如第 1.1.5 節末尾的這三個句子中的第二個（強調我的）：
一個 $ \alpha $ 0.001 表示如果序列是隨機的，人們會期望 1000 個序列中的一個序列被測試拒絕。對於 P 值 ≥ 0.001，序列將被認為是隨機的，可信度為 99.9%。對於 P 值 < 0.001，序列將被認為是非隨機的，可信度為 99.9%。
這個問題正確地觀察到
最有趣的是，當我將塊大小增加 10 倍（800,000 個隨機字節：N=8，M=800000）時，我只能在所有模式上獲得良好的結果。
特別是如果測試的生成器是無條件的 TRNG（見下文），這將匹配生成器在本地具有重複模式的故障模式，但這些模式會隨著時間的推移而演變。
如果測試數據的來源是一個無條件的 TRNG，並且除非該東西的供應商在契約中以嚴厲的懲罰保證不需要任何條件來通過任何類型的測試（這將是一個愚蠢的舉動），那麼 RNG 失敗測試應視為正常。相應地，送出此輸出供實驗室驗證應被視為程序錯誤：這些測試旨在測試 RNG 是否可與隨機區分開來，而無條件的 TRNG 通常是！
另一方面，如果測試的是使用 TRNG 播種的 PRNG 的輸出（這對於黑盒測試來說是典型的），並且測試失敗，則表明（兩者）PRNG 極差/有缺陷和TRNG的失敗。
未經處理的 TRNG 通常具有缺陷，通常是細微的，取決於製造變化和環境條件。設計工程師必須考慮到這一點。應使用無條件 TRNG 的輸出（僅在操作模式下）：
- 監測無條件 TRNG 的故障；監控的目標是確保源提供一些熵，高於某個設計限制，而不會引發錯誤警報。
- 並提供一個 PRNG，該結果被使用（不是 TRNG 的無條件輸出）。
此外，如果該 PRNG 不是 CSPRNG（這是典型的硬體 PRNG，通常是 LFSR 的變體），對於某些關鍵用途，PRNG 的輸出應該是一個好的 CSPRNG 的輸入（通常認為可以直接使用用於更平凡事物的硬體 PRNG，例如大規模 DPA 對策）。
將一個合格的 TRNG 變成一個通過所有標準測試的好的 RNG 是很容易的。難的是使監控能夠在現場明顯地檢測到故障並採取相應的行動，但在正常使用情況下不會錯誤地檢測到故障。真正的失敗可能是因為攻擊者做了各種令人討厭的事情：欠壓/過壓、加熱或液化氣體蒸發以降低 RNG 源的熵率，或者在電源上疊加時鐘/毛刺（等等）控制 TRNG 源並使其接近確定性。有時，對手只是墨菲定律（可能表現為接觸不良、電線過長、電源不干淨、去耦不足、製造缺陷），但也同樣成功。
注意：我聽說過一個故事，當時缺乏經驗的硬體製造商提出了一種帶有模組的 IC，該模組最初被指定為始終有效的直接可用 TRNG；然後發現有時無法通過測試；並匆忙替換為有條件的 TRNG，無法訪問指定的無條件 TRNG。據報導，這使得正確監控 TRNG 變得困難：唯一合理的選擇是打破條件，但故事結束時並沒有明確表明已經實現並部署了這一點。
您正在測試多少種模式？如果您正在尋找許多不同的模式。預計其中至少有一個會更常見。通常我們希望 p 值很小以顯示影響並使用某種多假設校正。然而，這對我們有利，因此這不是一個好的解決方案。但是像你一樣增加數據量。如果頂部模式只出現在小樣本中，但在大樣本中，您看不到任何問題。我會相信大樣本。如果某種模式確實出現得稍微頻繁一些，那麼更大的樣本只會使 p 值更加極端。歸咎於多假設檢驗。