從線性同餘生成器預測值

我了解到線性同餘隨機數生成器在密碼學上並不安全 - 我的理解是，給定以下形式的 LCG：

X_n = (aX_(n-1) + c) mod m

給定過去 X_n 的數量（即使不知道 a、c、m），可以預測未來的 X_n。

然而，在大多數實現中，有幾個複雜的因素：

1. 返回的值通常隱藏一定數量的 X_n 的最低有效位
2. 在大多數情況下，這些值以一個小整數p為模返回。

因此，除了內部狀態本身，我們通常只有每個狀態的模 p 的高階位。

我的問題是：在給定一些具有這些限制的過去值的情況下預測未來值是否容易處理 - 有證據嗎？

我找到了 J. Boyar 的這篇論文，但據我所知，它只考慮了第 (1) 點。

編輯

@fgrieu 已經表明，如果我們知道a、c和m並且m是 2 的冪，那確實是微不足道的。如果有更通用的解決方案，我仍然感興趣。

該答案與該問題的早期變體有關，該變體曾經給出了一個範例問題a, c, m known , 如下所示：

考慮在 Java 中從0to列印 100 個隨機數的以下內容5：

Random r = new Random(); // seeded by system time for (int i=0; i<100; i++) System.out.println(r.nextInt(6));

其中r.nextInt(6)基本上是以下內容：

seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); // i.e. seed = (seed * multiplier + addend) $ \bmod 2 ^ {48} $

int bits = (int)(seed >>> (48 - 31)); return bits % 6;

是的，可以從其第一個輸出預測該線性同餘生成器變體的輸出。首先，唯一未知的是 的原始值seed，即 48 位。這可能是蠻力的，給定適度的資源（一些 CPU.days），並且我們有足夠的輸出（如果輸出真的是隨機的，我們會有大約 $ 100\cdot {log}_2(6) \approx 258 $ 資訊位）。然而，有更好的攻擊可能，在幾秒鐘內成功。

這個問題本身是多種多樣的。最初它使用 8 的小整數（最終模數）而不是 6。我們首先研究它，因為事實證明它更容易，並且是 6 版本的一個很好的介紹。

原始問題，以return bits % 8

這裡seed有 48 位，bits是它最左邊的 31 位，結果bits % 8是它的低 3 位。的前 28 位seed永遠不會影響生成器的輸出（在模數為 2 的 LCGm中，位的變化seed永遠不會傳播到 的低位seed）。因此，為了預測輸出，seed表現為 20 位（不是 48 位）狀態。此外，減少的 20 位狀態的 3 個高位直接從第一個輸出中得知。

現在，由於除了 RNG 的初始狀態之外的所有內容都是已知的，因此暴力破解剩餘的 17 位幾乎是即時的。有更聰明的方法可以避免猜測。

這說明，當使用 2 的冪作為其模數的 LCG 的輸出m取模數為 2n時，輸出的周期比原始 LCG 的周期要小得多（以及即使出於模擬目的也可能是災難的其他弱點） .

更新：事實證明，Java 的nextInt(int n)方法特殊情況下發生的情況n是 2 的冪，然後做了一些與原始問題中顯示的非常不同的事情。這是為了避免上述影響。

其他問題，以return bits % 6

在這裡，所有的 48 位seed對輸出序列都有影響。但是有一種簡單的方法可以將這 48 位分成兩個單獨的受攻擊段。

因為最後的模6是偶數，所以低位bits也是輸出的低位，直接洩漏。它是主 LCG 的高位，減少到 .的低 18 位seed。seed這允許從第一個輸出的低位恢復低 18 位（我猜稍微多於 18 位）。一個簡單的方法是列舉 $ 2^{18} $ 的低 18 位的值，seed並且對於每個，檢查哪個給出了第一個輸出值的正確奇偶校驗。這將在一秒鐘內恢復低 18 位seed，並且足以預測進一步輸出的奇偶性。同樣，有更聰明的方法可以避免猜測。

現在我們剩下 30 個高位seed未知數；這可以在幾秒鐘內被暴力破解。可能有更聰明的方法。

更新：事實證明，Java 的nextInt(int n)方法與原始問題中顯示的不完全一樣，即使n不是 2 的冪；這是為了消除輸出中的偏差。然而，給出的簡化描述已經足夠好，所描述的密碼分析有公平的機會按原樣工作，並且可以適應可靠地工作。

---

更新 2：上面的工作是因為m是 2 的冪，並且最終的模數n可以被整除 $ 2^k $ 和 $ k>1 $ . 這允許單獨的攻擊 $ k+r $ 低位，其中 $ r $ seed是未用於產生輸出的正確位數（ $ k=1 $ , $ r=17 $ 在上面的例子中）。如果a和/或c和/或 $ r $ 是未知的，仍然可以進行這種分離，並找到 $ k+r $ , 和中的每一個的低位seed,a和c的值 $ r $ ，從考慮的多個連續輸出 $ \bmod 2^k $ ，與其他未知數無關。

---

一種更通用的方法，也適用於奇數n，也許也適用於未知a和/或c，將是在​​布爾可滿足性的形式下對問題進行編碼，並使用許多可用的 自動 求解器之一。不過，我無法預測執行時間。這種靈活的方法已經破解了一些稍微嚴重的密碼，例如參見 this cryptanalysis of A5/1或 this one。

---

LCG 對加密目的非常不利。它們適用於連續模擬目的（將輸出轉換為浮點數的尾數並按原樣使用），但對於離散模擬目的來說很脆弱。特別是，如果 LCG 使用 2 的冪作為其模數m，不要將其輸出模數取為偶數並期望結果表現為具有該數量面的骰子：該假設是不正確的，許多簡單的測試將表明那。

例如，連續（模擬）擲骰子的奇數和偶數之間的不平衡在之後正好為零 $ 2^{1+r} $ 拋出。這可以用更少的樣本通過雙向卡方檢驗nextInt(6)%2或什至僅檢測到nextInt(6)。難以置信的可以執行這個測試程式碼；它幾乎總是輸出 0（特別是另一個個位數的值），而真正的隨機通常會給出一個 3 位數的值。

import java.util.Random;
public class diceparity {
   public static void main(String[] args) {
       final int m = 262144; // number of dice throws
       Random rand = new Random();
       int s = -m/2; for (int i = m; i != 0; --i)
           s += rand.nextInt(6)%2;
       System.out.println("Deviation from expected: "+s);
   }
}

此外，在 262144 次投擲（或略少）之後，投擲的奇偶性會重複。

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