生成應該取決於密鑰的隨機數

我想生成隨機數，例如從

$$ 1..100 $$. 生成隨機數的算法應該像*“線性同餘生成器”*一樣工作，如下所示： $ X_{n+1}≡(aX_n + c)\ (mod\ m) $

在哪裡：

$ c $ - 增量應該類似於 98979817

$ a $ - 應該用於安全並且應該是很大的數字

$ X_n $ - 初始編號

但是，我不能使用這個公式，因為我的 $ m\ (mod m) $ 是 100 所以它是 $ m < c $ 和 $ m < a $ . 雖然它應該是 $ m > c $ 和 $ m > a $ .

也許有類似的東西比這更安全？

根據我們常見問題解答中的標準，任何使用線性同餘生成器且沒有密碼學的偽隨機數生成器都是不安全的，或者至少是不令人滿意的。很可能，一個熟練的對手將能夠通過適度的工作從過去的一定數量的輸出中預測未來的輸出；充其量，這不會發生，但不會有合理的論據表明這是不可能的。有許多或多或少難以閱讀的論文說明了這一點。最近的一個問題，另一個那裡，進一步說明了這一點。如果更安全 要求被認真對待，最好完全忘記 LCG，並使用密碼學。

安全的“取決於密鑰的隨機數生成器”中應該有三個步驟，生成一個均勻分佈在整數上的輸出序列 $ [1…100] $ :

1. 初始鍵的拉伸。目的是使暴力搜尋密鑰不可行，或者至少代價高昂。如果密鑰已經足夠寬（比如 120 位或更多；256 很多）並且隨機均勻選擇，*那是多餘的；*在幾乎任何其他情況下，包括當人們需要記住（或更糟的是選擇）鍵時，強烈建議對該輸入進行故意緩慢的轉換。在許多情況下（特別是：多個使用者的組合和密碼的使用），初始密鑰應該在拉伸時加鹽。這些函式的標準建構塊是基於密碼的密鑰派生函式。一個常見的是PBKDF2；加密貨幣更安全；目前最先進的技術是Scrypt。
2. 加密安全偽隨機數生成器，或等效的安全流密碼的密鑰流生成器。我們將向它提供（可能是拉伸的）密鑰（在名為種子或密鑰的輸入中），然後它將根據需要輸出我們可能想要的幾乎任意數量的隨機位。該密碼原語的設計力求使該輸出在計算上與不知道種子的對手無法區分。有大量的 CSPRNG 和流密碼可供選擇，最佳選擇取決於上下文。如果它必須在任何現代 CPU 上執行得很快，就會想到Salsa20 。
3. 後處理以獲得均勻分佈在所需輸出間隔上的輸出 $ [u…v] $ ， 這裡 $ [1…100] $ . 一種簡單的合適技術（有點浪費，但沒關係，因為 CSPRNG 可能很快）是：

• 找到最小的整數 $ w $ 這樣 $ 2^w\ge v-u+1 $ ; 這就是 $ w=7 $ ， 自從 $ 128\ge100 $ .
• 獲得 $ w $ 位使用 CSPRNG，形成一個整數 $ r $ 在範圍內 $ [0…2^w-1] $ ， 直到 $ r<v-u+1 $ （否則，丟棄 $ r $ 並重複此步驟）。
• 輸出 $ u+r $ ，並根據需要繼續上一步以獲得更多輸出。

---

如果簡單且基於 LCG 很重要，並且只要輸出足夠好以通過一些簡單的統計測試，那麼安全毫無意義，則以下過程建構 LCG 並對其輸出進行後置處理（我假設範圍 $ [u…v] $ 寬度不超過約 $ 2^{16} $ ).

1. 選擇 $ m=2^{64} $ （或方便的更高功率 $ 2 $ ), $ a=3141592621 $ , $ c=1 $ （這符合TAOCP第 2 卷第 3.6 節中更詳細的建議；除了我保留 $ a $ 不變，而不是冒險擴大規模 $ m $ ); C 或 C++ 類型unsigned long long（如果可用）適用於隱式約簡模一些適當的實現相關 $ m $ .
2. 尋找 $ w $ 從區間 $ [u…v] $ 如上（這裡 $ w=7 $ 為了 $ [1…100] $ ).
3. 放 $ X $ 將密鑰截斷為位寬 $ m $ （重複一遍：安全性超出了範圍！但是，將其他關鍵位輸入其中並沒有什麼壞處 $ c $ ，只要它被強制為奇數）。
4. 放 $ X $ 到 $ a⋅X+c\bmod m $ ; 在 C 中是X = a*X+c;.
5. 形式 $ r $ 在範圍內 $ [0…2^w-1] $ 來自 $ w $ 高位_ $ X $ ; 在 C 中，這r = X>>(W-w);是W為 選擇的無符號整數類型的位寬X，並且 $ m=2^{\mathtt W} $ .
6. 如果 $ r\ge v-u+1 $ , 繼續第 4 步。
7. 輸出 $ u+r $ , 並根據需要進行步驟 4 以獲得更多輸出。

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