Markdown
# LCG-RSA的强强联手 — Writeup
## 题目信息
- **题目名称**：LCG-RSA的强强联手
- **题目类型**：Crypto / LCG 参数恢复 + RSA
- **Flag 格式**：`LHFLAG{...}`
## 题目描述
一次调试日志意外泄露了 LCG 的连续 10 个输出。服务端用同一 LCG 的后续状态生成 RSA 的两个素数 `p` 和 `q`，对 flag 进行了加密。已知 `task.py` 和 `output.txt`，恢复 flag。
## 附件要点
### task.py（核心逻辑）
```python
class LCG:
def __init__(self, m, a, b, seed):
self.m, self.a, self.b, self.x = m, a, b, seed
def next(self):
self.x = (self.a * self.x + self.b) % self.m
return self.x
rng = LCG(M, A, B, SEED)
leak = [rng.next() for _ in range(10)] # 10 个连续输出泄露
p = next_prime(rng.next()) # 第 11 个输出 → p
q = next_prime(rng.next()) # 第 12 个输出 → q
n = p * q; e = 65537
c = pow(int.from_bytes(FLAG, "big"), e, n)
```
### output.txt
```
leak = [10 个 ~512-bit 整数]
n, e, c 已知
```
## 解题思路
### 1. 恢复 LCG 模数 m
LCG 迭代公式：
$$x_{n+1} = a \cdot x_n + b \pmod{m}$$
定义差分序列：
$$t_n = x_{n+1} - x_n$$
则：
$$t_{n+1} = x_{n+2} - x_{n+1} = a(x_{n+1} - x_n) = a \cdot t_n \pmod{m}$$
因此：
$$t_{n+1} \cdot t_{n-1} - t_n^2 \equiv a^2 \cdot t_{n-1}^2 - a^2 \cdot t_{n-1}^2 \equiv 0 \pmod{m}$$
即 $|t_{n+1}t_{n-1} - t_n^2|$ 是 $m$ 的整数倍。
对多个 $n$ 计算该值并取 GCD，即可恢复 $m$：
```python
t = [leak[i+1] - leak[i] for i in range(len(leak) - 1)]
multiples = [abs(t[i+1] * t[i-1] - t[i]**2) for i in range(1, len(t) - 1)]
m = multiples[0]
for u in multiples[1:]:
m = gcd(m, u)
```
### 2. 恢复 a 和 b
由 $t_1 \equiv a \cdot t_0 \pmod{m}$：
$$a = t_1 \cdot t_0^{-1} \pmod{m}$$
由 $x_1 = a \cdot x_0 + b \pmod{m}$：
$$b = x_1 - a \cdot x_0 \pmod{m}$$
### 3. 恢复 seed 并复现 PRNG
由 $\text{leak}[0] = a \cdot \text{seed} + b \pmod{m}$：
$$\text{seed} = (\text{leak}[0] - b) \cdot a^{-1} \pmod{m}$$
用恢复的 `(m, a, b, seed)` 重建 LCG 并验证 leak 完全一致。
### 4. 生成 p、q 的 LCG 基础值
```python
rng = LCG(m, a, b, seed)
_ = [rng.next() for _ in range(10)] # 跳过已泄露的
lcg_p = rng.next() # 第 11 个输出
lcg_q = rng.next() # 第 12 个输出
```
### 5. 爆破 next_prime 偏移
$p = \text{next\_prime}(lcg\_p)$ 即 lcg_p 之后的下一个素数。对于 ~512-bit 的大数，素数间隙极小，可直接从 lcg_p 开始递增搜索：
```python
p = lcg_p | 1 # 确保是奇数
while n % p != 0:
p += 2
q = n // p
```
实际偏移仅 **124**（即 lcg_p 之后第 62 个奇数）。
### 6. RSA 解密
```python
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
flag = pow(c, d, n)
```
## 完整攻击代码
```python
from math import gcd
leak = [...] # 10 known outputs
n, e, c = ... # from output.txt
# Step 1: Recover m
t = [leak[i+1] - leak[i] for i in range(9)]
multiples = [abs(t[i+1] * t[i-1] - t[i]**2) for i in range(1, 8)]
m = multiples[0]
for u in multiples[1:]: m = gcd(m, u)
# Step 2: Recover a, b
a = t[1] * pow(t[0], -1, m) % m
b = (leak[1] - a * leak[0]) % m
# Step 3: Recover seed
seed = (leak[0] - b) * pow(a, -1, m) % m
# Step 4: Replay LCG
class LCG:
def __init__(self, m, a, b, x): self.m, self.a, self.b, self.x = m, a, b, x
def next(self):
self.x = (self.a * self.x + self.b) % self.m
return self.x
rng = LCG(m, a, b, seed)
_ = [rng.next() for _ in range(10)]
# Step 5: Find p
lcg_p = rng.next()
p = lcg_p | 1
while n % p != 0: p += 2
q = n // p
# Step 6: Decrypt
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
flag = pow(c, d, n).to_bytes(200, 'big').lstrip(b'\x00')
```
## 结果
| 参数 | 值 |
|------|-----|
| LCG 模数 m | 512-bit |
| p 偏移 | offset = 124（从 LCG 输出到素数） |
| seed | 成功恢复，leak 验证通过 |
## Flag
```
LHFLAG{lcg_rsa_predictor_9f3a1c7e5b2d}
```
## 总结
| 要点 | 说明 |
|------|------|
| **漏洞 1** | LCG 线性结构导致模数可从连续输出中恢复 |
| **漏洞 2** | `next_prime` 偏移极小，可直接爆破 |
| **攻击链** | leak → LCG 参数恢复 → 预测 p,q → RSA 解密 |
| **防御建议** | 使用密码学安全的 CSPRNG（如 `secrets` 模块），不要用 LCG 生成密钥材料 |