從一個小組中生成隨機的非重複數字
我讀了這個問答，它給出了一個聰明的解決方案：將遞增索引輸入到塊密鑰密碼中，作為產生非重複隨機數的一種方式。問題是所有好的算法的塊大小通常都太大了。如果我只想遍歷所有 16 位數字或所有 N 位數字，其中 N 由手頭的問題決定，該怎麼辦？頭腦正常的人不會製作 16 位分組密碼，但這正是我所需要的。
我必須對所有 n 位數字進行偽隨機迭代的一個想法是使用二進製欄位。隨機化模多項式， $ Q $ ，確保它是不可約的。然後隨機取一個起點， $ a $ , 並反复乘以一個隨機的原始元素， $ r $ , 生成偽隨機序列。
$ n_i = a r^i \pmod Q $
有人告訴我這還不夠好。預測下一個元素可以解釋為離散對數問題，如果 $ i $ 是必須從中找到的明文 $ n_i $ . 離散對數是困難的，但是當 $ n_i $ 都是按順序給出的，能不能找到問題 $ r $ 和 $ Q $ 從序列仍然可以解釋為離散對數問題？問題有名稱嗎？有多難？
如果這種迭代方法不好，我有一個想法讓它變得更難：填充索引 $ i $ 在加密之前使用一些隨機位，因此如果索引是 16 位數字，則使用 4 個隨機位將其加密為 20 位。這足以確保不可預測的模式嗎？哪種迭代方法可以確保找到解決方案有足夠的難度？這種修改的一個缺點是，雖然生成的序列是非重複的，但它並沒有覆蓋整個輸出域。有沒有辦法覆蓋整個輸出域？
如果您要在輸出域中生成所有數字，一旦您通過中間點，攻擊者猜測下一個數字的工作就會變得越容易，您使用的數字越多。我會建議你選擇任何方法，永遠不要超過 $ N/2 $ 使用的值，其中 $ N $ 是可以使用該方法生成的元素總數， $ N=2^{16} $ 在你的例子中。
實際上，我認為使用有限域沒有問題，但您需要讓攻擊者難以猜測用於生成它的值，即使該方法是已知的。
我的解決方案是使用與生成 AES S-box 相同的有限域反演方法，但在 $ GF(2^{16}) $ 使用 APA 方法。這是一個高度非線性的序列，生成器值和歸約多項式的組合太多，無法像在 $ GF(2^{8}) $ .
本質上，您對輸入執行仿射變換，然後在場中找到逆，然後再次執行仿射變換，從可能的多項式列表中隨機選擇一個不可約多項式。每個有限域內都有仿射生成器和向量的特定組合，可以生成對 S-box 有用的高質量結果，但您不會受到相同條件的限制，從而為您提供更大的靈活性。該算法的數學描述將非常簡單。
格式保留選項允許您輕鬆地建構您想要的任何塊大小的 Feistel 密碼，因為您的域大小是 2 的偶數冪，在您的情況下為 16 位，通過使用另一個塊密碼或 PRF 作為 F 函式。您可以加入 AES，使用 8 位塊的一半加上一個圓形計數器作為輸入，並將輸出截斷為 8 位。這將非常容易編碼並且非常快速地生成數字，但代價是對最終算法的複雜描述。您還可以在 CTR 模式下生成 128 位子密鑰，然後將這些子密鑰用作每一輪的獨立 AES 密鑰，但需要額外的計算。
查看是否交換 (pdf)。與一些基於 Feistel 網路的解決方案不同，這將為您提供近乎理想的安全性（攻擊者必須查詢接近整個空間才能獲得不可忽略的優勢）。
或者，列舉和改組 2^16 個 16 位數字的列表只需要 ~128KB 的 RAM。如果您需要重現排序，請使用密鑰作為 PRNG 種子。