可重現的偽隨機排列
我有辦法通過交換某種初始值和生成多項式來計算兩個相似的偽隨機週期序列嗎？
就像一個線性回饋移位寄存器，但有一個有限的數字域，每個數字在序列中只出現一次？
我正在閱讀這個問題，要求一個由密鑰播種的公共偽隨機數生成器 $ K $ ，這將輸出整數值 $ r_j $ 在指定範圍內 $ [a,b] $ （這裡，
$$ 1 to 75 $$) 偽隨機地根據密鑰，然後在到達它們中的每一個恰好一次後循環。添加下一個輸出是一個函式 $ F_K $ 以前的（而不是一些內部狀態）。 我們需要的只是一個偽隨機排列 $ P_K $ 集合的 $ [0,n-1] $ 和 $ n=b+1-a $ , 它是逆的 $ {P_K}^{-1} $ , 我們從中定義
$$ r_{j+1}=F_K(r_j)=P_K({P_K}^{-1}(r_j-a)+1\bmod n)+a $$ 換句話說，要移動到下一個數字，我們
- 減去 $ a $
- 應用逆排列 $ {P_K}^{-1} $
- 加一，如果結果是 $ n $ 將其替換為零
- 應用排列 $ P_K $
- 添加 $ a $
這基本上是適用的 $ P_K $ 到一個循環計數器和一個偏移量。如果我們可以記住計數器的狀態，前兩個步驟是不必要的。
構造偽隨機排列 $ P_K $ 是Format Preserving Encryption的經典問題。一種選擇是使用Fisher-Yates shuffle建構的表格。另一種是使用分組密碼和循環：
計算 $ w=\lceil\log_2(n)\rceil $ ，也就是在 $ n-1 $
建個 $ w $ 位塊密碼 $ C $ 帶鑰匙 $ K $ （同化至 $ w $ -位整數到 $ w $ -bit 位串，例如big-endian 約定）。
計算 $ y=P_K(x) $ 作為
- $ y\gets x $
- $ y\gets C_K(y) $ ，即加密 $ y $ 帶鑰匙 $ K $ 每個分組密碼 $ C $
- 如果 $ y\ge n $ , 轉到上一步
計算 $ x={P_K}^{-1}(y) $ 作為
- $ x\gets y $
- $ x\gets{C_K}^{-1}(x) $ ，即解密 $ x $
- 如果 $ x\ge n $ , 轉到上一步
加密和解密循環總是終止，並且平均執行幾次。
構造排列 $ C_K $ , 我們可以使用對稱Feistel 密碼，除了我們想使用 $ \displaystyle w=\min\left(2\left\lceil\frac{\log_2(n+1)}2\right\rceil,4\right) $ 這將確保 $ w $ 甚至，Feistel 密碼不會小到退化，並且在 $ n $ 是四的冪，我們使用稍微大一點的分組密碼來補償它是一個偶數排列。
另一種選擇是近對稱的 Feistel 密碼，當 $ w $ 是奇數，並且循環循環的加法而不是 XOR（修復偶排列的東西），這讓我們使用 $ w=\min(\lceil\log_2(n)\rceil,4) $ .
如果我們不著急的話，Feistel 圓形函式 $ i $ 可 $ F_{i,K}(L)=\operatorname{PRF}_K(i\mathbin|L) $ 截斷為 $ \lceil w/2\rceil $ -bit，對於某些PRF，例如 HMAC-SHA-256。
在任何情況下（特別是如果我們使用更簡單/更弱的輪函式），我們應該使用很多輪小 $ w $ ， 也許 $ \lceil 6+60/w\rceil $ .