改進的 RC4 密鑰調度算法的狀態恢復
考慮這個算法：
def ksa(k): L = length(k) j = 0 for i from 0 to L: #[0..L-1] (non inclusive "to") j = (j + k[k[i] % L])%L swap(k[i], k[j])
k是一個整數數組 $ 0 \leq x < 256 $ . 問題是如何列舉所有可能的數組k，從而生成具有給定前綴的數組 $ P $ . 換句話說，如果k'=ksa(k)，如果 $ P=[1,2,3] $ , 那麼如何生成所有k, 這樣 $ prefix(k’,length(P))=P $ ? 列舉是最好的，但只建構一個這樣k的也很好。for i from 0 to Cwhere變體的解決方案 $ C \leq L $ 也會很有趣。這是加密算法 RC4 的密鑰調度的變體。
您描述的算法似乎有一類特殊狀態（類似於 RC4 的 Finney 狀態），由以下狀態組成 $ i = j $ 和 $ k_x \bmod L = 1 $ ， 在哪裡 $ x := k_i \bmod L $ .
如果我們在循環開始時處於屬於此類的狀態，則循環的效果將只是交換 $ k_i $ 和 $ k_{i+1} $ 並增加兩者 $ i $ 和 $ j $ 一個。因此，只要我們也有 $ x \notin {k, k+1} $ ，下一次循環迭代的狀態也將屬於這一類特殊狀態。
特別是，考慮如果在算法之前，我們有 $ k_0 = L-1 $ 和 $ k_{L-1} = 1 $ . 那麼初始狀態 $ i = j = 0 $ 屬於上面描述的特殊類，這將持續到算法結束。倒數第二次迭代，其中 $ i = L-2 $ , 確實把我們帶出了課堂，留下了我們 $ i = j = x = k_x = L-1 $ ，但這只會導致數組的最後兩個元素 $ k $ 在最後一次迭代中第二次交換，留給我們 $ k_{L-2} = L-1 $ 和 $ k_{L-1} = 1 $ .
同時，數組的所有其他元素，在 $ L-1 $ 在開始和 $ 1 $ 最後，只需向下移動一個位置 $ L-1 $ 元素從他們身邊冒出。因此，從一個初始數組
$$ (L-1, a, b, c, \dotsc, y, z, 1) \tag{1} $$我們最終得到最終狀態$$ (a, b, c, \dotsc, y, z, L-1, 1) \tag{2} $$無論未知元素的值如何 $ a, b, c, \dotsc, y, z $ . 相反，以任何形式的最終狀態結束 $ (2) $ 上面，從相應的初始狀態開始就足夠了 $ (1) $ . （同樣的技巧也適用於終止於某處的循環 $ i = C < L-1 $ , 除了最初的 $ L-1 $ 元素然後結束於 $ k_{C+1} $ 而不是在 $ k_{L-2} $ .)
事實上，我只是寫了一個小程序來測試這個。這是一個執行範例 $ L = 10 $ ，每次迭代一行，從括號中的八個隨機值開始 $ L-1 = 9 $ 和 $ 1 $ :
k = (9, 144, 165, 42, 43, 56, 231, 72, 53, 1), i = 0, j = 0 k = (144, 9, 165, 42, 43, 56, 231, 72, 53, 1), i = 1, j = 1 k = (144, 165, 9, 42, 43, 56, 231, 72, 53, 1), i = 2, j = 2 k = (144, 165, 42, 9, 43, 56, 231, 72, 53, 1), i = 3, j = 3 k = (144, 165, 42, 43, 9, 56, 231, 72, 53, 1), i = 4, j = 4 k = (144, 165, 42, 43, 56, 9, 231, 72, 53, 1), i = 5, j = 5 k = (144, 165, 42, 43, 56, 231, 9, 72, 53, 1), i = 6, j = 6 k = (144, 165, 42, 43, 56, 231, 72, 9, 53, 1), i = 7, j = 7 k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), i = 8, j = 8 k = (144, 165, 42, 43, 56, 231, 72, 53, 1, 9), i = 9, j = 9 k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), j = 8, end of loop