RC4 或 Salsa20 等流密碼的 PRG 週期是多少？
在更改密鑰之前，我對流密碼可以使用多長時間感到困惑。具體來說，我以基於 RC4 的流密碼為例。
假設我想加密一條很長的消息。我選擇了一個 128 位的密鑰並開始使用 RC4 流密碼進行加密。RC4 在其 PRG 重新開始之前必須執行多少輪？Salsa20 怎麼樣：在冒著洩露資訊的風險之前，使用相同的密鑰可以執行多長時間？
我意識到，作為一個實際問題，這個時間段可能比任何現實世界的資訊都要長得多，但我仍然有興趣知道這個界限。
RC4 的內部狀態由一個 256 元素的混洗數組和指向該數組的兩個指針組成。因此，共有
$$ 256! \times 256^2 \approx 2^{1700.00} $$可能的狀態。由於 RC4 的狀態更新函式是可逆的，它充當了對這組可能狀態的一個排列，因此每個起始狀態最終都會在經過足夠多次迭代後重新出現。 多少才足夠多？好吧，如果我們假設更新函式表現得像一個隨機排列（當然，它不是，但它是一個很好的第一個近似值），那麼預期的循環長度大約是 $ 2^{1700}/2 = 2^{1699} $ 迭代（！）。實際上，從隨機狀態開始的循環長度至少為 $ k $ 迭代次數約為 $ 1 - k/2^{1700} $ ; 這意味著達到一個小於的周期，比如說， $ 2^{200} $ 迭代應該少於一次 $ 2^{1700-200} = 2^{1500} $ 初始化，即基本上從不在宇宙的生命週期內。
當然，如前所述，RC4 狀態更新函式不是隨機排列。例如，有一個已知的類 $ 254! $ 短週期 $ 256^2-256 = 65280 $ 各州；幸運的是，標準的 RC4 鍵設置保證永遠不會擊中它們。有關 RC4 的實際循環結構的更多資訊，請參見例如S. Mister 和 SE Tavares的“類 RC4 密碼的密碼分析”。