解题思路（要求解题思路清晰，每个题需截图flag值并且包含时间） 这题的核心不是分解 RSA，而是把 三个带线性扰动的 RSA 方程 合并成一个多项式，再用 Coppersmith 一元小根攻击 找明文。

1. 观察加密过程

题目：

m = bytes_to_long(flag)

c = pow(a*m+b, 3, n)

即：

c_i=(a_i m+b_i)^3 \pmod{n_i}

共有三组：

\begin{cases} (a_1m+b_1)^3 \equiv c_1 \pmod{n_1}\ (a_2m+b_2)^3 \equiv c_2 \pmod{n_2}\ (a_3m+b_3)^3 \equiv c_3 \pmod{n_3} \end{cases}

其中：

明文相同

模数互素

2. 构造多项式

把未知数记成

对于第一组：

(a_1x+b_1)^3-c_1 \equiv 0 \pmod{n_1}

展开：

a_1^3x^3 +3a_1^2b_1x^2 +3a_1b_1^2x +(b_1^3-c_1) \equiv0\pmod{n_1}

记为：

f_1(x)

同理得到：

f_2(x)

f_3(x)

真正的明文 同时满足：

f_i(m)\equiv0\pmod{n_i}

3. CRT 合并

因为：

\gcd(n_i,n_j)=1

所以可以对每个系数做 CRT。

例如三次项：

A \equiv a_1^3 \pmod{n_1}

A \equiv a_2^3 \pmod{n_2}

A \equiv a_3^3 \pmod{n_3}

得到唯一：

A \pmod N

其中

N=n_1n_2n_3

其它系数同理。

于是得到：

F(x)

Ax^3+Bx^2+Cx+D

满足：

F(x)\equiv f_i(x)\pmod{n_i}

因此：

F(m)\equiv0\pmod N

4. 化成首一多项式

把最高次项变成 1。

求：

A^{-1}\pmod N

然后：

G(x)=A^{-1}F(x)

得到：

G(x)=x^3+\cdots

且：

G(m)\equiv0\pmod N

5. 为什么能用 Coppersmith

题目里：

每个 是 1024 bit。

所以：

N

约为：

3072 \text{ bit}

于是：

N^{1/3}

约为：

2^{1024}

而 flag：

flag{e3bed61d917f86053a6ec4a2adb9d34c} 长度大约：

38 字节左右

即：

m < 2^{320}

显然：

m \ll N^{1/3}

满足 Coppersmith 条件。

6. Coppersmith 的作用

我们已经得到：

G(m)\equiv0\pmod N

并且知道：

|m|<2^{320}

这是标准形式：

f(x)\equiv0\pmod N

寻找小根：

|x|<X

Coppersmith 通过：

1. 构造格

2. LLL 约化

3. 得到新的整数多项式

最终恢复：

x=m

7. 恢复 flag

得到：

m

后：

long_to_bytes(m)

即可得到：

flag{e3bed61d917f86053a6ec4a2adb9d34c}

一句话总结

这题本质上是：

(a_i m+b_i)^3 \pmod{n_i}

的 Håstad Broadcast Attack（线性填充版）。

解题链路：

构造 fi(x) ↓ CRT 合并系数 ↓ 得到 F(x) mod N ↓ 化成 monic polynomial ↓ Coppersmith 一元小根攻击 ↓ 恢复 m ↓ long_to_bytes(m) ↓ flag

这是 CTF 中非常经典的一类题，关键词通常是：

Hastad Broadcast Attack with Linear Padding Coppersmith Univariate Small Root Low Exponent RSA