隨機性測試
假設我有三個序列：
S1 = {1,2,3,4,5,6,7,8,9,10}
S2 = {3,7,1,9,4,10,5,8,6,2}
S3 = {8,3,10,2,6,7,1,5,9,4}
即 S2 和 S3 只是 S1 的排列。有什麼方法可以檢查這些序列彼此隨機的程度？我需要使用任何隨機性測試來檢查它們的隨機性。我找到了用於比特流的 NIST 測試套件，但無法找到任何針對置換序列的測試。
請記住，序列很大 {1,2.3,…,n} 並且具有“m”序列。
編輯：這裡；m < n
排列是基於鍵的排列。
不存在序列（或排列，或字元串等）的隨機性。選擇序列（排列、字元串等）的**過程只有隨機性，這本質上不是您可以通過查看其輸出來測試的。
您可以做的是編寫一個決策程序，該程序將根據兩個不同的隨機過程中的哪一個生成輸出，以一定的機率返回不同的答案。 當然，其決策的機率分佈取決於其輸入的機率分佈！這裡有幾個例子：
- 輸入數據：字元串 $ n $ 位 $ b_i \in {0,1} $ .
程序：
- 計算$$ \chi^2 = \frac{(#{b_i = 0} - n/2)^2}{n/2} + \frac{(#{b_i = 1} - n/2)^2}{n/2}, $$在哪裡 $ #{b_i = 0} $ 是零位數和 $ #{b_i = 1} $ 是一位的數量。
- 如果 $ \chi^2 \leq 3.841 $ , 返回 0; 否則返回 1。
機率分佈：
- A1：獨立均勻伯努利試驗， $ \theta = 1/2 $
- B1：獨立的伯努利試驗偏向於 $ \theta = 1/3 $如果輸入按 A1 分佈，則返回 0 的機率為 95%，返回 1 的機率為 5%。用統計學術語來說，如果我們取 A 為原假設，取 1 表示拒絕或報警，則統計顯著性或誤報率為5%。
如果輸入按 B1 分佈，則返回 0 的機率要低得多，而返回 1 的機率要高得多。（練習：計算這些數量。用統計學術語來說，如果我們將 B 作為原假設 A 的備擇假設，則在給定 B 的情況下返回 1 的機率稱為檢驗的統計功效。） 2. + A2：獨立均勻伯努利試驗， $ \theta = 1/2 $ + B2：交替 0 和 1 位，01010101…或 10101010…等機率 $ 1/2 $如果輸入按 A2 分佈，那麼如上返回 1 的機率為 5%——顯然，這是與上面相同的測試和相同的分佈 A1，因此誤報率為 5%。
如果輸入按 B2 分佈，則返回 0 的機率為 100%，返回 1 的機率為 0%。也就是說，該測試沒有任何統計功效來檢測 B2！這說明了任何區分測試的效用完全取決於您試圖區分的分佈。你不能簡單地問：“這個序列是隨機的嗎？” 或“這個序列是獨立的均勻伯努利試驗嗎？”
- 輸入數據：八組獨特顏色的聰明人。
程序：
- 如果淡紫色糖果出現在黃色糖果之前，則返回 0；否則返回 1。
機率分佈：
我們假設一家工廠按字母順序生產顏色
$$ blue brown green mauve orange pink red yellow $$, 並沒有用所有可能的排列隨機排列它們——具體來說，它一直將前四個作為一個組，將後四個作為一個組排列，但從未將第一組中的任何內容與最後一組中的任何內容互換。所以我們有： + A3：具有均勻排列的聰明人 + B3：Smarties 藍色/棕色/綠色/淡紫色均勻排列，其次是橙色/粉色/紅色/黃色均勻排列。在分佈 A3 下，有 50% 的機會在黃色之前出現淡紫色，有 50% 的機會在淡紫色之前出現黃色。因此，該過程以相等的機率返回 0 和 1，即 50%。
在分佈 B3 下，有 100% 的機會在黃色之前出現淡紫色，在淡紫色之前出現黃色的可能性為 0%。因此，該過程以 100% 的機率返回 0，並以 0% 的機率返回 1。
在密碼學中，我們通常使用非常相似的分佈，以致於任何區分它們的過程對於兩種分佈返回 1 的機率幾乎相同——因此，即使是由非常聰明的密碼分析家設計的程序也可以t 以超過可忽略的機率區分分佈。 換句話說，如果 NIST 測試可以破壞您的系統，那麼它可能會被愚蠢到甚至不知道自己在嘗試的人破壞破壞你的系統——我的意思是從字面上看：NIST 的一個程序員，在一般意義上並不愚蠢，但特別缺乏對你的系統的了解，他能夠在幾年前設計一個測試，甚至在你設計你的系統之前就可以破壞它系統。
因此，我們無法幫助您找到置換序列隨機性的測試——從表面上看，這是一個荒謬的問題。嘗試對您進行精神分析以猜測哪些過程可能產生了您的排列，然後基於這些得出測試，這也不是很有趣。但是，如果您可以描述候選過程，或者描述一個過程並將其與排列上的均勻分佈進行比較，那麼也許會有一個測試可以區分它們。
例如，也許您正在嘗試置換 $ {0,1,2,\dots,2^{128} - 1} $ ，並且您的排列是通過（a）選擇一個 256 位密鑰來選擇的 $ k $ 均勻隨機，然後 (b) 選擇 $ \operatorname{AES}_k $ 作為排列。在這種情況下，您沒有希望將其與均勻隨機排列區分開來 $ {0,1,2,\dots,2^{128} - 1} $ （除非側通道攻擊）。
一個序列只有10個樣本，無法描述任何關於隨機性的事情。實際上，測試隨機性需要很長的序列。NIST 工具是推斷哪個序列是否為偽隨機的最佳方法之一，但是它們至少需要 10^6 個序列，並且輸入應該是位形式。