生成偽隨機排列的計算效率最高的方法是什麼？
我有一個應用程序，我需要在其中創建最多 J 個長度為 N 的數組的隨機混洗副本。然後我將進行數百萬甚至數十億次迭代，這樣，在每次迭代中，我都必須獲取 K 的值<< 原始數組的 J 個置換副本的 N 個條目。對於所有 J 個 shuffled-copies，需要訪問的 K 個條目都是相同的，但是這組 K 個條目會從一個迭代變為另一個迭代。
為了大致了解問題的維度，假設 J = 25000、N = 500000 和 K = 50，即使這些數字不是先驗固定的。
到目前為止，我一直在遵循的簡單方法是使用 Fisher-Yates 算法（也稱為 Knuth shuffle）來創建數組的置換版本，將它們作為 NxJ 矩陣儲存在記憶體中。然而，在許多情況下，該矩陣往往太大，這是有問題的。此外，在每次迭代中重新計算整個矩陣會非常緩慢。
作為替代方案，我已經開始考慮使用偽隨機排列。使用加密過程複雜度為 O(1) 的分組密碼，我可以理想地獲取所需的 K 個條目，每次迭代的複雜度為 O(KJ)。這在經驗上似乎是可以接受的。
我的問題，作為一個對密碼學有非常基本了解的人，你會推薦我使用哪種方案來執行這樣的任務。關鍵是我寧願有一個加密速度非常快的方案，即使加密標準的安全性很差。只要可以生成的一組不同的排列（並且看起來足夠隨機）在 2^32 的數量級上，就可以了。類似 AES 的安全級別顯然是矯枉過正。
作為參考，我目前正在使用具有 ceil(log2(N)) 位和非常簡單的輪函式（16 位輪密鑰，8 位與明文的一半異或）的“手工”4 輪 Feistel 網路，結果通過 S 盒傳遞，其他 8 位用作一組 256 個隨機位移的索引）。我還使用循環行走方案來處理 N 不是 2 的冪的（常見）情況。
我猜這個方案對於密碼標準來說是個坏笑話，但是對於我的應用程序（統計假設檢驗）來說，它似乎足夠隨機。如果我能稍微降低加密方案的複雜性，那就太好了。
如果你們中的任何人都可以提供一些建議，我將非常感激！
TL; DR 我正在尋找最快的方法來生成一組大小為 N 的偽隨機排列。我更關心速度而不是方案的安全性（大約 2^32 個“真正的”隨機排列就足夠了）。
使用格式保留加密。目前的 NIST 標準跟踪模式FFX應該足夠快以滿足您的目的。對於您的域大小，您可能還想嘗試swap-or-not shuffle，這是一種新的結構，它也非常快且易於實現。要從這些方案中獲得絕對最佳的速度，您應該使用單個 AES 呼叫作為您的 PRF，如果您有AES-NI指令，最好使用它們。
編輯：任何基於不經意洗牌的 PRP 生成器都應該適用於您的目的。這是另一個參考解釋那是什麼。
我解釋、批評並嘗試改進問題中的技術（通過在統計模擬中使用密碼技術來獲得可以說是令人滿意的功能來要求***速度）。***洗牌和成熟的格式保留加密旨在完美或可證明的加密安全性，這是一個不同的目標。
假設要計算的條目的（未說明的）分佈是相當隨意的，並且儲存 $ J\cdot N\cdot\lceil\log_2(N)\rceil $ bits 不是一個可行的選擇，問題中的一般技術似乎最好：建構一個有效的鍵控偽隨機排列 $ P $ 集合的 $ {0\dots N-1} $ , 用鑰匙（注 $ y $ 以防止符號衝突）隨機，或從排列索引中獲得 $ j\in{0\dots J-1} $ （例如作為 $ y=y_0\oplus j $ 和 $ y_0 $ 在多次迭代開始時固定的隨機常數）；然後評估 $ P_y(x) $ 如所須。
問題建立 $ P $ 從分組密碼 $ E $ 的 $ n=\lceil\log_2(N)\rceil $ -位塊大小，與 $ P_y(x) $ 通過循環行走技術計算：
重複
- $ x\gets E_y(x) $
直到 $ x<N $
輸出 $ x $
任何 $ P_y $ 顯然是集合的排列 $ {0\dots N-1} $ . $ P $ 顯然至少與 $ E $ 是（忽略邊通道問題，例如通過時序或功率分析）。計算 $ P_y(x) $ 平均使用 $ 2^n/N<2 $ 的評價 $ E $ , 最多 $ 2^n-N+1<N $ .
問題建立 $ E $ 作為Feistel 密碼, 對稱的 if $ n $ 是偶數，或者大部分是這樣，如果 $ n $ 不是。它有 4 輪 ad-hoc 輪函式，基於截斷的 AES S-box（請參閱目前問題的評論中的詳細資訊），沒有我可以發現的空白缺陷 $ n\approx13 $ .
即使按照給出的描述進行了良好的設計，也存在潛在的問題：Luby-Rackoff 結果（How to Construct Pseudo-random Permutations from Pseudo-random Functions，在 Crypto 1985 的程序中）確保了 Feistel 密碼在 3 輪後的安全性（ 4 如果我們考慮自適應選擇密文攻擊）僅對獨立和隨機輪函式有效；漸近地當 $ n $ 成長；並且當評估的不同輸入的數量遠少於 $ 2^{n/2} $ （這裡， $ \sqrt N $ )，這在應用程序中是不保證的。隨著更多空間的探索，需要更多輪次（參見 Jacques Patarin 的Luby-Rackoff：7 輪足夠 $ 2^{n(1−\epsilon)} $ 安全性，在 Crypto 2003 的程序中）。
擴展：我將展示為什麼寬度小 $ E $ ，我們需要超過 4 輪才能達到甚至接近加密穩健性的程度。在如上圖所示的 4 輪對稱 Feistel 密碼中，如果兩個密鑰使用相同的 $ F_2 $ 在輸入處的常數的異或內，並且相同 $ F_3 $ ，那麼對於任何 $ I_a $ ， 功能 $ I_b\to O_b $ 在一個常數的異或內是相同的（取決於 $ I_a $ ) 在輸入。對於兩個相當大的隨機排列（機率約為 $ 2^{n(2^{n/2-1}-2^{n-1})} $ ， 那是 $ 2^{-24192} $ 為了 $ n=12 $ )，並且如果它發生很容易檢測到並且可以想像可能會對實際應用產生影響。在考慮的結構中（在對此問題的評論中有詳細說明） $ n=12 $ ，每個輪函式是與一個 6 位常數後跟一個 in 的 XOR $ 2^8 $ 6x6 位的 S-box，因此任何兩個隨機鍵控都有 $ F_2 $ 和 $ F_3 $ 導致該特徵的可能性 $ 2^{-22} $ ，這預計會發生超過一百次 $ J=25000 $ 按建議構造的排列。對於實際攻擊，我們選擇任意固定 $ I_a $ , 和部分映射 $ I_b\to O_b $ 對於隨機 $ I_b $ （多一點 $ 2^{n/4} $ 對每一個的評價 $ J $ 排列會做）；當我們發現碰撞 $ E_b(I_a|I_b)=E_b’(I_a|I_b’) $ , 我們檢查是否 $ \forall x,E_b(I_a|(I_b\oplus x))=E_b’(I_a|(I_b’\oplus x)) $ （在肯定的情況下，我們可以確認類似的屬性適用於任何其他 $ I_a $ ，並且實際上可以肯定的是 $ E $ 和 $ E’ $ 共享相同的 S-box $ F_2 $ ，並且在 $ F_3 $ , 和相同的 XOR 常數 $ F_3 $ ）。我們極有可能找到一對 $ (E,E’) $ 在使用問題中提出的構造時具有這種屬性，並且對於隨機排列幾乎是不可能的。攻擊可以適應工作 $ P $ 使用自行車步行建造。
**更正：**此外，我們可以想像排列奇偶性的應用 $ P $ 可能會產生影響，例如排序中掉期數量的分佈。任何 Feistel 密碼都會產生一個偶排列，因此 $ E $ 甚至。儘管 $ N<2^n $ 允許 $ P $ 無論是偶數還是奇數，它的奇偶性將我們強烈偏向於 $ N $ （論據：當 $ 2^n-N $ 比較小 $ \sqrt N $ ， 對於大多數 $ E $ ，循環行走重複循環恰好執行兩次 $ 2^n-N $ 輸入，並且一次用於所有其他輸入，因此產生的奇偶校驗 $ P $ 是 $ N\bmod 2 $ ）。所以我們需要大量的騎自行車（this other question問多少），或者在一個關鍵位的控制下使排列成為偶數或奇數（一種簡單的技術使用除最右邊之外的任何全零密文的 XOR ，具有控制奇偶校驗的關鍵位），或偏離直接的 Feistel（例如，使用模加法而不是 XOR 將輪函式的結果與半狀態相結合）。
更一般地說：在小寬度的 Feistel 構造中註入熵的一種推薦方法是在整個狀態寬度上使用圓形密鑰的模組化添加（而不是像問題的 Feistel 構造中那樣對一半狀態進行異或）：注入近兩次盡可能多的熵，這是非常可取的；並平衡排列的奇偶性。
通過仔細規範 Feistel 密碼，使用更多輪次、注入更多密鑰材料並處理奇偶校驗問題（除非明顯無關緊要，包括從未使用至少 2 個輸入的任何情況），該方法具有優點。使用AES-NI指令建構輪函式的另一個答案中的想法會很快提供一些東西，但會犧牲可移植性，我不會冒險這樣做。
這是一個經過修訂的暫定，命名為
fastperm2，使用密碼技術在一個小域上建構有效的隨機排列。我強調我不提供密碼安全保險；儘管如此，我還是挑戰一個人在隨機密鑰設置中找到攻擊比 $ 2^{64-i} $ 賠率步驟 $ 2^{-i} $ 成功的，甚至僅限於特定的 $ N $ .理由：
易於用 C 編寫程式碼；
有限的自行車步行，因為額外的努力最好花在更多的回合上；
最簡單的圓形函式，沒有 S-box，使用：
- 通過與公共乘法器的模乘法進行擴散（向左，並在一定程度上向右）；
- 右移狀態異或的右擴散和非線性；
- 在完整狀態上使用加法與輪密鑰組合，以最大化密鑰材料並處理排列奇偶性；
至少 16 輪希望能彌補這種簡單性（我希望我能證明這個價值，而不是用嚴肅的密碼類比）。
足夠多的輪次，至少 64 位熵被注入密碼的每一半，丟棄一輪（希望 64 位安全性可以抵禦一般的中間相遇攻擊）；
限制域，以便 $ N! $ 舒適地高於 $ 2^{128} $ , 狀態適合 32 位字。
根據參數選擇 $ N $ :
- 確保 $ 40\le N\le 2^{32}-2^{20} $ （對於較低 $ N $ ，無論如何，沒有什麼能比得上費舍爾-耶茨）；
- 找到最低的 $ M $ 和 $ N\le M $ 這樣 $ M\equiv2^k\pmod{2^{k+1}} $ 和 $ k $ 最接近的整數 $ n(\sqrt5-1)/2) $ 在哪裡 $ n=\lceil\log_2(M)\rceil $ （因此： $ 6\le n\le32 $ , $ k=\lfloor(13n+10)/21\rfloor $ ， 和 $ M=(2\big\lfloor\lceil N/{2^k}\rceil/2\big\rfloor+1)2^k $ );
- $ r\gets2\max(\lceil64/(n-1)\rceil+1,8) $ ，輪數。
- $ C\gets\lfloor(28657M+23184)/46368/2^k\rfloor2^k+(\text{7D8B5}{16}\bmod 2^k) $ （以便 $ C\approx M(\sqrt5-1)/2 $ , 和低 $ k $ 位 $ C $ 是每個常數 $ F{29}\equiv5\bmod 8 $ );
- 儘管 $ \gcd(C,M)\ne1 $
- $ C\gets C-2^k $
- $ s\gets n-k $ ，班次計數；
注意：參數是這樣的 $ x\to C\cdot x\bmod M $ 和 $ x\to x\oplus\lfloor x/2^s\rfloor $ 是集合的排列 $ {0\dots M-1} $ . 第一個變換在狀態位中實現了良好的左擴散；兩種變換都給出了一些正確的擴散（儘管僅限於最左邊 $ s $ 第一次轉換的位）。
子鍵設置：
- 對於每個 $ j $ 和 $ 0\le j<r $
- 放 $ y_j $ 到一個均勻的隨機值 $ {0\dots M-1} $ （或使用未指定的偽隨機函式 $ y $ 和 $ j $ )
加密 $ x $ 和 $ 0\le x<N $ :
重複
對於每個 $ j $ 和 $ 0\le j<r $ 按升序排列
- $ x\gets(C(x\oplus\lfloor x/2^s\rfloor)+y_j)\bmod M $
儘管 $ x\ge N $
輸出 $ x $
精確地實現乘法和模約減是至關重要的。在 C99 中並假設所有變數都是 類型
uint32_t，一輪是：x = ((x ^ x>>s)*(uint64_t)C + y[j]) % M;計劃：給出一個參考C實現。
對於統計應用程序，輪數 $ r $ 可以降低；我猜想 $ r\gets2\max(\lceil40/(n-1)\rceil+1,5) $ 將通過任何不使用密碼結構知識建構的隨機性測試，包括任何預先存在的測試。
修訂：round 函式中的兩個可怕的拼寫錯誤已得到修復。我又開始考慮了 $ n-1 $ 每輪注入一些熵（而不是 $ k $ 在短暫的
fastperm3）。增加在簡化版本中註入的熵以供統計使用，以降低幾乎相同排列的機率。.
