RSA 小明文多项式泄露:c=m³+a2m²+a1m+a0 的高精度求根与低 16 位爆破
crypto/rsa · verified
一句话结论
当 RSA 输出不是 c=m^e mod N 而是 c=m^3+a2m^2+a1m+a0 mod N,且 m 很短、多项式总量小于 N 时模约减不发生,c 就是精确整数多项式;利用已知的 a2 高位构造近似三次方程,高精度牛顿法逼近根后在 ±2^16 内爆破 m,即可恢复作为 AES 密钥的 m 并解出 flag。
原理
- 无模约减条件:m 为 16 字节(约 128 bit)时
m^3约 384 bit;a2*m^2约 40+256=296 bit;a1*m、a0更小;各项之和约 385 bit,远小于 N(约 1024 bit)。因此c = (m^3 + a2m^2 + a1m + a0) mod N中的mod N不改变值,c 就是精确整数。 - 部分系数已知:题目只给出 a2 的高位
a2_high(a2 = a2_high << 16 + low),a1、a0 已知。先忽略低位,把A = a2_high << 16代入Q(x) = x^3 + A x^2 + a1 x + a0 - c。 - 高精度求根:用 Decimal 提高精度(
prec=200),从x = c^(1/3)出发做牛顿迭代x ← x - Q(x)/Q'(x),得到与真实 m 接近的整数根;由于 a2 的低 16 位未知,根有误差。 - 局部爆破:在
m_approx ± 2^16内枚举 delta,令num = c - m^3 - a1*m - a0,若num % m^2 == 0,则a2_candidate = num // m^2;检查a2_candidate >> 16 == a2_high,命中即真实 m。 - 后续利用:m 被直接当作 16 字节 AES-128-CBC 密钥,用已知 iv 解密密文并去填充即可。
触发条件
- RSA 或类 RSA 加密使用小指数 e=3,且明文 m 很短(示例 16 字节)。
- 密文计算包含多项式附加项(
a2 m^2 + a1 m + a0),且总量小于 N,未发生模约减。 - 攻击者知道 a1、a0 与 a2 的高位(或可通过枚举/侧信道获得)。
- m 可直接作为对称密钥或包含可验证格式(flag/填充),便于确认命中。
利用步骤
- 确认
c < N且各多项式项的量级之和小于 N,排除模回绕。 - 用已知的 a2 高位构造
A = a2_high << 16,写出Q(x)=x^3+A x^2+a1 x+a0-c。 - 用高精度 Decimal/整数牛顿法求近似根
m_approx。 - 在
±2^16范围内枚举 delta,利用num % m^2 == 0与a2 >> 16两个条件筛选真实 m。 - 把 m 转 16 字节作为 AES 密钥解密密文,去 PKCS#7 填充得到 flag。
PoC
from decimal import Decimal, getcontext
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
getcontext().prec = 200
c_dec = Decimal(c)
A = Decimal(a2_high << 16)
a1_dec, a0_dec = Decimal(a1), Decimal(a0)
x = Decimal(c) ** (Decimal(1) / Decimal(3))
for _ in range(50):
Q = x**3 + A*x**2 + a1_dec*x + a0_dec - c_dec
Qp = 3*x**2 + 2*A*x + a1_dec
x_new = x - Q / Qp
if abs(x_new - x) < Decimal(1):
x = x_new
break
x = x_new
m_approx = int(x)
for delta in range(-2**16, 2**16 + 1):
m = m_approx + delta
if m <= 0:
continue
num = c - m**3 - a1*m - a0
if num % (m*m) != 0:
continue
a2 = num // (m*m)
if a2 >> 16 == a2_high:
key = m.to_bytes(16, 'big')
cipher = AES.new(key, AES.MODE_CBC, iv=bytes.fromhex(iv))
print(unpad(cipher.decrypt(bytes.fromhex(ct)), 16).decode())
break
原文数据命中 m=155455820692697783953491152103673430935(delta=-3406,a2=590661429227),解出:
ISCTF{i7_533M5_Lik3_You_R34lLy_UNd3R574nd_Polinomials_4nD_RSA}
变体与关联
- 若附加项完全已知(a2 无未知低位),可直接对 c 开三次方或解精确三次方程,无需爆破;见 [[crypto-rsa-e3-small-plaintext-integer-cube-root]]。
- 若 m 更大导致
m^3 > N,需改用 Coppersmith 小根;见 [[crypto-rsa-e3-known-prefix-suffix-coppersmith]]。 - 多项式次数/项数可变:核心是“总量小于 N → 精确多项式 → 求根 + 局部枚举未知系数/低位”。
- 关联:[[crypto-rsa-polynomial-derivative-hidden-exponent-enum]](同为多项式系数泄漏类攻击)。
检测与防御
- 检测:CTF 中检查密文是否小于 N、是否存在未约减的多项式结构;AES 密钥短、由 RSA 小明文直接派生是典型信号。
- 防御:使用 OAEP 等随机化填充,使 m 接近模长且随机;不要用短明文/短密钥直接派生对称密钥;避免泄露多项式系数的高位。
- 加固:RSA 密钥至少 2048 bit,密文输出前统一做模约减并校验范围。