RSA 广播攻击变种:仿射变换 (a·m+b)^3 与 CRT 合并多项式求小根
crypto/rsa · verified
一句话结论
当同一明文 m 在多个互素模数下被仿射变换后做低指数加密(c_i ≡ (a_i*m + b_i)^3 mod n_i)时,可以先把每个三次多项式 f_i(x)=(a_i*x+b_i)^3-c_i 的系数用 CRT 合并成模 N=∏n_i 的多项式 F(x),则 F(m) ≡ 0 mod N;再用 Coppersmith small_roots 求小根即可恢复 m,无需同余式完全相同。
原理
- 标准 Hastad 广播攻击要求
c_i ≡ m^e mod n_i,CRT 合并后开 e 次方;若加密前做了仿射变换,直接开方失效。 - 但
m仍是每个同余式f_i(m) ≡ 0 mod n_i的根,其中f_i(x)=(a_i*x+b_i)^3-c_i。 - 因为
n_i两两互素,可对f_i的每个系数(常数项到三次项)分别做 CRT,得到模N=∏n_i的多项式F(x);于是F(m) ≡ 0 mod N。 F的首项系数lead若与N互素,可在Z_N上归一化为首一多项式,再用 Coppersmith 求|m| < X的小根;X取2^384到2^1000逐档尝试。- 找到根后必须回代每个
n_i验证(a_i*m+b_i)^3 ≡ c_i mod n_i,避免 CRT/多项式构造错误或伪根。 - 本质是把“同明文广播”推广为“同明文的多项式同余”,只要
m足够小且e小(3 次),Coppersmith 就能解。
触发条件
- 使用小公钥指数
e=3(或较小e),同一明文m在至少e个互素模数下加密。 - 每个模数对应已知仿射变换
(a_i,b_i)与密文c_i。 m的比特长度小于N的某个比例(Coppersmith 小根界),案例可到 900–1000 位。- 首项系数
lead与N互素(否则 gcd 可能直接给出因子)。
利用步骤
- 收集
(n_i,a_i,b_i,c_i),确认gcd(n_i,n_j)=1。 - 在
ZZ上展开f_i(x)=(a_i*x+b_i)^3-c_i,得到 4 个系数。 - 对每个系数用 CRT 合并到模
N,得到F(x);检查gcd(lead,N),若不为 1 可直接尝试分解。 - 在
Z_N上把F归一化为首一多项式(每项乘lead^{-1})。 - 对
X=2^384,2^448,...,2^1000调用small_roots(X=X, beta=1.0)。 - 对每个根
m回代所有n_i验证;通过后转字节/文本得到 flag。 - 若失败,检查
m是否比界大、e是否真是 3、多项式展开/CRT 是否有误。
PoC
# Sage
mods = [Integer(n1), Integer(n2), Integer(n3)]
params = [(Integer(a1), Integer(b1), Integer(c1)),
(Integer(a2), Integer(b2), Integer(c2)),
(Integer(a3), Integer(b3), Integer(c3))]
N = prod(mods)
PR.<x> = PolynomialRing(ZZ)
polys = [(a*x + b)^3 - c for a, b, c in params]
coeffs = []
for k in range(4):
residues = [Integer(polys[i][k]) % mods[i] for i in range(3)]
coeffs.append(Integer(crt(residues, mods)))
lead = Integer(coeffs[3])
print("gcd(lead,N) =", gcd(lead, N))
ZN = Zmod(N)
R.<y> = PolynomialRing(ZN)
f = y^3 + sum((ZN(coeffs[k]) / ZN(lead)) * y^k for k in range(3))
for xb in [384, 448, 512, 640, 768, 900, 1000]:
roots = f.small_roots(X=2^xb, beta=1.0)
for r in roots:
m = Integer(r)
if all(power_mod(a*m + b, 3, n) == c % n
for n, (a, b, c) in zip(mods, params)):
print(int(m).to_bytes((int(m).bit_length() + 7)//8, "big"))
raise SystemExit
变体与关联
- 变体:仿射变换可能是
a_i*m + b_i、m*a_i mod n_i、分段/线性组合;只要能写成多项式同余即可。 - 变体:
e不是 3 而是 5/7 时,多项式次数升高,需要更多模数/更大N或更强 Coppersmith。 - 变体:若
gcd(lead,N) != 1,可能直接得到N的因子,转为分解攻击。 - 关联:[[ctf-crypto-rsa-hastad-broadcast-e3-crt]](标准广播)、[[crypto-rsa-e3-small-plaintext-integer-cube-root]](小明文开方)、[[crypto-rsa-crt-multi-modulus-high-bits-coppersmith-low-bits]](CRT+Coppersmith)。
检测与防御
- 防御:使用 OAEP 等随机化填充,确保同一明文每次加密结果不同;避免小
e与固定线性变换组合。 - 防御:不要用同一明文在多个密钥/模数下加密;对 RSA 使用 2048 位以上模数与标准库。
- 检测:代码中出现
(a*m+b)^e mod n、多个模数、CRT 合并多项式;同一明文重复加密。 - 响应:发现广播/仿射泄露后轮换密钥,审计历史密文是否可恢复,改用随机化填充。