隨機置換中第n項的高效計算

想象一下，我可以使用類似Knuth shuffle和帶有種子鍵的種子隨機數生成器來洗牌0到2^32之間的所有數字。隨機置換中第n項的高效計算

在概念上，我會（使用Ž 代替ž爲了簡潔）需要兩個數組：

[2, 0, 1, 4, 3] // perm 
[1, 2, 0, 4, 3] // inv === p^-1

如果我有這些陣列，我可以有效地查找排列中的第n個元素以及查找purmutation值v中的元素;

v = perm[n]; 
n == inv[v]; // true

我不想存儲UINT表示此洗好的一組，因爲我在任何時候整個打亂順序從不感興趣兩個16 GB陣列。我只對第n個元素的價值感興趣。

我非常想要寫兩個是這樣工作的純函數：

uint nthShuffled = permutate<uint>(key, n); // O(log n) 
uint n == invert<uint>(key, nthShuffled); // O(log n)

要求：

每32名值映射到唯一不同的32位值。
排列中前100個元素的知識不能提供關於排列中第101個元素的信息。

據我所知，理論上必須至少有2 ！唯一的鍵來表示任何可能的排列，但我相信我可以在實踐中隱藏這個問題後面的一個好的散列函數。

那裏有什麼東西可以接近這個嗎？

來源

2011-11-09 Doug Coburn

歡迎來到Stack Overflow！如果您想從加密的角度（而不是在C++部分）更多地考慮這個問題，那麼對於姊妹站點[Cryptography Stack Exchange]（http://crypto.stackexchange.com/）來說這將是一個很好的問題。（我是主持人）。如果你也這麼認爲，你可以將它標記出來讓SO版主遷移它（使用「需要管理員注意力」並輸入自定義標誌原因）。 –

任何分組密碼實際上是一個僞隨機排列。 32位塊密碼置換0和2^32 - 1之間的整數。

給定一個密鑰，用這個密鑰加密N給出N-th僞隨機數。

唯一的問題是找到一個好的32位塊密碼。我知道的唯一一個是SKIP32，但我對它的實力一無所知。

SKIP32的密鑰大小是80位。如果這是一個好的密碼，那就足夠了。

但是，我不知道密碼。

如果增加至2^64 - 1整數是一個選擇，你可以使用simpply知名的64位塊加密像三重DES或河豚。

來源

2011-11-09 01:31:08 Dennis

有許多標準的方法，例如Luby-Rackoff構造，用於在現有加密基元（例如分組密碼或散列函數）之外構建具有任意塊大小的安全分組密碼。見例如[這個問題在crypto.SE]（http：// crypto。stackexchange.com/questions/504/can-you-create-a-strong-blockcipher-with-small-blocksize-given-a-strong-blockci）瞭解更多信息。 –

聽起來像SKIP32可能符合所有要求，謝謝。 –

您對crypto.SE的這個問題的鏈接正是我一直在尋找的。謝謝！ –

「的排列的前100種元素的 Knowldedge提供什麼可能是在排列第101個元素的任何信息。」

您需要存儲在內存中的整個陣列。我建議使用stxxl，它通過將大容量的容器存儲在磁盤上來爲大數據類型設計。由於隨機置換的本質，你不能外推給定[n]的[n-1]或[n + 1]的值。所以它看起來並不像空間可以被優化。

來源

2011-11-09 01:14:17 moshbear

從技術上講，你是對的。但我認爲OP正在尋找一種僞隨機排列。 – Dennis

要對所有可能的2^32進行純粹的無偏差覆蓋！可能的排列，我必須（最好）將密鑰存儲爲介於0和2^32！-1之間的數字。但在實踐中，我應該把可能的排列數限制在2^128左右，以便所有可能排列的空間具有良好的僞隨機分佈。 –

哈希不會解決隨機數字序列。

存儲2^32位。這是0.5 GB。

在你走的時候運行Fischer-Yates隨機播放和「交叉」位。如果你想知道第五個元素的內容，那麼你會劃掉4，第五個隨機值將是你的數字。

要獲得第n個排列，則需要回溯。運行算法n次，得到號碼，如：

Find 5th index after 4 permutations: 

First iteration: 
1st : skip (run through the RNG) 
2nd : skip 
3rd : skip 
4th : 7th index to 5th index 
Second iteration: (run using same seed as 1st iteration) 
1st : skip 
2nd : skip 
3rd : 3rd index to 7th index 
4th : 7th index to 5th index 
Third iteration: 
1st : skip 
2nd : 4th index to 7th index 
3rd : 3rd index to 7th index 
4th : 7th index to 5th index 
Fourth iteration: 
1st : 8th index to 4th index 
2nd : 4th index to 7th index 
3rd : 3rd index to 7th index 
4th : 7th index to 5th index

通過最後一次迭代，你知道第八指數導致成爲第5個指標。

編輯：我寫了一個快速程序來測試速度。每個排列需要幾分鐘。它很慢，但仍然可用。

來源

2011-11-09 01:31:49 Pubby

從加密的角度來看，你需要一個帶有32位塊的分組密碼。

關於任意（通常是小）域的加密問題（又稱「密鑰置換」）就是Format-Preserving Encryption。

對於那個特定的問題，有一個generic "perfect" solution - 但計算涉及通過超幾何分佈進行採樣，這意味着大量的浮點數和任意精度數的分散，這很昂貴。

也有「近似」解決方案，其中置換不嚴格地說是在所有可能的置換中均勻地選擇，但是可以使得任意小的差別，以至於不可能區分實施排列和一個真正隨機選擇的排列。具體參見Thorp shuffle。

沒有標準和安全的32比特塊密碼，因爲32位爲不夠，以確保安全性的情況，其中塊密碼通常使用（數據的長流的加密，例如，如SSL的一部分）; 64位塊已經皺起了眉頭。所以你在這裏有點自己。

來源

2011-11-09 13:51:22

任何密碼系統，其中每個32位消息M alwasy加密到相同的32位消息E不適用於其中M可能被多次加密的流密碼。我打算按序列順序加密數字，並且不要多次加密相同的M。我（加密者）想知道E是否是第n個元素，但我不想讓你知道這一點。 –

隨機置換中第n項的高效計算

回答

相關問題