我正在努力申請Freize 等人。紙打破截斷的 LCG。

截斷 LCG 是一個偽隨機生成器，它輸出 $ n $ 前導位 $ y_i $ 的 $ x_i $ ， 在哪裡 $ (x_i) $ 是這樣的 $ x_{i+1} = \alpha \cdot x_i + \beta\mod M $ ， 和 $ \alpha $ 是一個整數，與 $ M $ . 第一個狀態 $ x_1 $ 是未知的。

目標是打破 LCG，即從一個或多個連續輸出中，找到目前狀態 $ x_i $ . 我們假設 $ \alpha $ 和 $ M $ 是已知的，並且 $ \beta = 0 $ （並且也是眾所周知的）。

---

理論

該論文指出（第 5 頁和第 6 頁），他們的方法解決了以下形式的模方程組 $ \displaystyle\sum_{j=1}^k a_{ij}x_j \equiv c_i \mod M $ ， 對所有人 $ i \in {1, \dots, k} $ .

從向量中推導出一個格子 $ a_i $ ，作者應用 LLL 來找到一個小的向量基 $ w_1, \dots, w_k $ .

通過乘以矩陣 $ \begin{pmatrix} w_1\ \vdots\ w_k \end{pmatrix} $ 在右邊 $ x $ ，他們推導出一組新的方程： $ \displaystyle\sum_{j=1}^k w_{ij}x_j \equiv c_i’ \mod M $ ， 對所有人 $ i \in {1, \dots, k} $ .

在這裡，我猜想 $ c_i’ $ 剛剛從 $ c_i $ 通過（在左側）乘以允許我們從原始基礎到簡化基礎的相同矩陣。

現在，如果 $ c_i’ $ 足夠小，等式實際上成立 $ \mathbb{Z} $ 我們可以解決它們：我們已經有效地解決了這個系統。

---

在實踐中

現在，作者更多地談論他們的 LCG 方法，第 3 部分（第 11 和 12 頁）。

我們有關係 $ \alpha^{k-1} x_{1} - x_k = 0 $ （編輯：修正錯字），所以我想這意味著我所有的 $ c_i $ 是 $ 0 $ .

現在，如果我想獲得我的 $ c_i’ $ , 我應該乘 $ c $ 左邊的矩陣與用於改變晶格基礎的矩陣相同。但是，鑑於我有 $ c = 0 $ ， 我應該 $ c’ = 0 $ 同樣，所以我們不需要計算這個矩陣。

此外，正如論文所述，我的格子是，

$$ L = \begin{pmatrix} M & 0 && \dots & 0\ \alpha & -1 &0& \dots & 0\ \alpha^2 & 0 & -1 & \dots & 0\ \vdots &&&\ddots & \vdots\ \alpha^{k-1} & 0 & 0 & \dots & -1\ \end{pmatrix} $$ 這是平凡的非奇異的，因此，唯一的解決方案 $ Lx = 0 $ 是 $ x = 0 $ ，這顯然是錯誤的。 更糟糕的是，這種方法不使用 $ y_i $ ，但它顯然應該在某個時候，所以我想我錯過了一些東西。

---

我的問題

（很可能相關）

1. 就我而言，什麼是 $ c_i $ ，我真的得到 $ c_i’ $ 從他們的基礎上改變？
2. 怎麼樣 $ y_i $ 應該參加這個方法嗎？

格子基礎 $ L $ 生成作為同餘解的每個點 $ a^{i-1} x_1 - x_i \equiv 0 \pmod{m} $ . 根據定義，簡化基 $ B = \mathsf{LLL}(L) $ 也產生相同的解決方案；它只是有更短的向量。

現在假設我們有一組輸出 $ \mathbf{y} = y_i $ 生成器，對應於 LCG 的最高有效位乘以 $ 2^s $ ，我們想找到 $ \mathbf{z} = z_i $ 這樣 $ \mathbf{y} + \mathbf{z} = \mathbf{x} $ ， 在哪裡 $ \mathbf{x} = x_i $ 是重構狀態。這裡的關鍵見解是

$$ \begin{align} & L \cdot \mathbf{x} \equiv 0 \pmod{m} \ & B \cdot \mathbf{x} \equiv 0 \pmod{m} \ & B \cdot \mathbf{x} = m \cdot \mathbf{k} \quad \mbox{(for some unknown $\mathbf{k}$)} \ & B \cdot (\mathbf{y} + \mathbf{z}) = m \cdot \mathbf{k} \ & B \cdot \mathbf{z} = m \cdot \mathbf{k} - B \cdot \mathbf{y} \end{align} $$ 現在，因為簡化基中的係數 $ B $ 很小，我們知道所有的元素 $ \mathbf{k} = k_i $ 很小，我們可以進一步推論 $ k_i = \lfloor (B \cdot \mathbf{y})_i / m \rceil $ ，或者換句話說， $ m \cdot k_i $ 是最接近的倍數 $ m $ 關於每個元素 $ B \cdot \mathbf{y} $ . 一旦我們知道 $ k_i $ ，這是一個簡單的線性代數問題。以下是 Sage 的範例：

p = previous_prime(2^32)
a = randint(2, p)
s = randint(0, p)
X = [ a^(i+1) * s % p for i in range(4) ]
Y = [ x - x % 2^16 for x in X ] # high 16 bits
Z = [ x % 2^16 for x in X ] # low 16 bits (secret)

L = matrix([
   [  p,  0,  0,  0 ],
   [a^1, -1,  0,  0 ],
   [a^2,  0, -1,  0 ],
   [a^3,  0,  0, -1 ]
])

B = L.LLL()

W1 = B * vector(Y)
W2 = vector([ round(RR(w) / p) * p - w for w in W1 ])

Z_ = list(B.solve_right(W2))
print Z_
print Z

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