可逆地洗牌一組百萬個號碼

Question

我需要來發行一系列{1,2,3,4}票據（至少看似）是隨機數{10,934,3,453,867,122,4,386,564 ...} 。當呈現後，我必須能夠計算它們的原始索引（例如122 → 3.）

換句話說，我需要的時間間隔似乎是隨機排列p [1 ... N]具有一個逆置換p-1。 N約爲10 。

的原因的是：

• 這是一個密碼：當收到一張票，它不應該很容易 猜測車票哪裏之前發出。
• 票據應該是短的可以記下的字母數字字符串。
• 我想避免記錄每張票發出。

Answer 1

您可以使用Linear congruential generator生成此類序列。 X0是種子（或者如果你願意的話，排列的索引）。 m應該等於N + 1。選擇c和a以確保完整的週期長度（如上面鏈接中「週期長度」部分所述）。這將爲您提供一個大小爲N的一對一映射。

要恢復索引，您可以使用系列中的少量連續僞隨機數破解LCG，即not too hard。當然，你可以保留m，a和c並節省麻煩。

想要更安全的方法請看David Eisenstat的評論。您只需要密鑰即可恢復索引。不利的一面是，如果你使用標準的FPE，N必須是2^x-1（例如2^128-1）。

Answer 2

1產生僞隨機洗牌，你可以使用費雪耶茨算法中：

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

What distribution do you get from this broken random shuffle?

for (int i = tickets.Length - 1; i > 0; i--) 
{ 
int n = random(i + 1); 
Swap(tickets[i], tickets[n]); 
} 

提防不使用 「錯誤」 的算法（他有偏見）。

你會得到排列，然後是逆排列。

2問題隨機隨機洗牌。

因爲有10000000！排列，你應該有一個非常大的種子

然後問題是在隨機發生器。標準的大約是32位，也許多一點，但遠不及1000萬！

你應該看到的東西像財神：

https://en.wikipedia.org/wiki/Fortuna_%28PRNG%29

Answer 3

我會在計數器模式下使用一些知名的密碼（例如，DES）。

對於正常的目的，DES通常被認爲是相當破碎的，但它似乎能夠很好地滿足您的需求，並且比大多數較新的算法具有更小的塊大小。對於你來說，這意味着它會產生一個較小的結果（如果有內存服務，則爲64位）。一旦你將它轉換成可讀的字符（例如base64），你最終會得到10個左右的字符。

要檢索原始數字，只需使用您的密鑰進行解密。

結果看起來相當隨機 - 實質上，將它們排序重新排序的唯一已知方法是破壞DES，這可以完成（已完成），但是執行此操作的資源非常重要。

如果你確實需要比這更好的安全性，你可以使用類似AES而不是DES的方式（以產生更長的「關鍵」值爲代價）。