創建單週期排列

有一次我想出了一個塊大小為 16 位的小排列。這小到足以計算每個映射。然後我從零開始迭代映射，看看需要多少次迭代才能返回到零。這個數字不到一半 $ 2^{16} $ .

無論出於何種原因，假設一個人需要一個只有一個循環的偽隨機排列。也許他們需要製作一個單週期 S 盒，或者他們想使用排列來對分組密碼的明文輸入進行非線性調整（每個塊的調整是連續迭代的結果，而不是一個增量） . 我首先想到的是全週期 LCG，但是當我嘗試用它來製作 S-box 時（ $ f(x) = (37 \cdot x + 11) \mbox{ mod } 256 $ )，結果看起來相當有序。這對於明文塊的調整無關緊要，但似乎完全不具有有序性的特性似乎是可取的。那麼，有什麼方法可以生成/構造單週期排列？

構造這種偽隨機單週期排列的明顯方法是採用偽隨機排列 $ P $ （不必是單週期），一個簡單的固定單週期排列 $ Inc $ （例如，只需將值增加 1），並構造：

$$ S = P^{-1} \ \circ Inc \ \circ P $$ 也就是說，要評估 $ S(x) $ , 你首先應用排列 $ P $ 至 $ x $ ，那麼排列 $ Inc $ ，然後是排列 $ P^{-1} $ ，這是排列的倒數 $ P $ .

應該很明顯的事情：

• $ S $ 是單循環置換
• 每個單循環排列都可以通過適當的選擇以這種方式表示 $ P $
• （不太明顯）如果 $ P $ 在所有排列上均勻選擇，然後 $ S $ 在所有單週期排列上統一選擇。

如果你想建構一個單循環 s 盒子，並想通過繪製一個均勻隨機的單循環排列來構造它，可以直接這樣做：

1. 創建一組 P 的數字 2..N
2. 設置 IDx=1
3. 從 P 中抽取一個隨機成員 M 將其分配給索引 Idx
4. 從 P 中刪除成員
5. 設置 Idx=M
6. 如果 P 非空，則從步驟 3 開始重複。
7. 將 1 分配給 Idx 的最後一個點。

你可以用一個數組和一個大小計數器來表示 P，為了刪除一個元素，你將最後一個元素複製到它的位置並減小大小。這允許所有步驟 $ O(1) $ 和總執行時間 $ O(n) $

如果你想要一個大的單循環排列（太大而無法完全實現），雨披給出了一個公平的解決方案，它依賴於偽隨機排列。

引用自：https://crypto.stackexchange.com/questions/51787