RC4 密鑰流是隨機的嗎？
我有理由使用 RC4 的 PRNG 一半，但對其輸出的隨機性感到非常困惑。（只有 PRNG 的一半。）
一方面，大量文獻發現 RC4 的密鑰流存在更大的偏差。似乎弱區分器和強區分器都可以從真正的隨機序列中辨識 RC4。這些分析是由聰明的人進行的。
另一方面，RC4 密鑰流通過了大多數公認的隨機性測試套件。我親自針對 100 GB 的輸出文件執行了 Dieharder 測試，它通過了。這些測試套件旨在辨識所謂的隨機位序列中的偏差，並且由聰明的人編寫。
任何人都可以將這個圓圈平方嗎？
編輯：
在查看了答案/評論後，我認為 RC4 算法的 PRNG 部分比粗略檢查最初看起來要好。這麼說，我排除了所謂的密鑰調度算法，它顯然已經很糟糕了。我會提出以下意見：
- 事實仍然是單個密鑰流通過了隨機性的最佳統計測試。這是不容忽視的。如果任何類型的隨機性存在顯著偏差，標準測試都會發現它。與證據相匹配的唯一假設是長期偏差在通常可接受的範圍內。
- 下面引用的論文承認主要的統計偏差僅發生在密鑰流的前 512 個字節內，並且完全歸因於密鑰調度算法/密鑰長度。
- 長期偏差比初始偏差低 500 倍，作者強調了確定長期偏差的不確定性，其中 $ 2^{-16} $ 難以完全評估或分類的偏差。
- pi 的十進制擴展顯示出相似的幅度偏差 (10e-6)，甚至達到 2 萬億位——這就是隨機性的本質。
- 如果對其他 PRNG 進行同樣程度的廣泛審查，它們是否也會表現出類似的偏見？
總之，在我看來，使用完全隨機化和手動注入的狀態數組（從而繞過固有的密鑰調度組件），RC4 是一個很好的 PRNG。
就像fkraiem 的回答指出的那樣，通過統計測試並不能證明 PRNG 在密碼學上是隨機的，甚至在其他測試中是隨機的。
在 RC4 的情況下，偏差在密鑰流的開頭最為突出。借用Vanhoef 和 Piessens 的“你所有的偏見都屬於我們：打破 WPA-TKIP 和 TLS 中的 RC4”（pdf，第 6 頁）的有用說明，被稱為 RC4 NOMORE 攻擊：
偏差將需要越來越多的樣本來檢測，沿著密鑰流越遠。解釋你的發現：
另一方面，RC4 密鑰流通過了大多數公認的隨機性測試套件。我親自針對 100 GB 的輸出文件執行了 Dieharder 測試，它通過了。
如果您通過使用該大小的單個 RC4 密鑰流來做到這一點，那麼只有開始可能會有可檢測的偏差。通過生成數十億個短密鑰流，您甚至可以使用一些通用的統計測試來檢測偏差（或者您可能不會，這取決於測試的具體內容）。
（此外，通常的做法是刪除初始密鑰流以消除在早期密碼分析中發現的最大偏差。如果您的 RC4 已經這樣做，這可能有助於隱藏統計測試中的偏差。不是因為它們不存在在修剪後的輸出中，但因為它們需要更多數據才能看到。）
這些偏差可能難以普遍檢測的原因是它們是密鑰流的特定字節之間的特定關係（請參閱連結論文中的第 2.3.3 節），並且對所有此類等式進行測試將非常耗時。另一方面，為套件添加針對這些偏差的特定測試只會幫助您證明輸入是 RC4（已知損壞）——其他輸入不太可能具有這些確切的偏差。
