密文 C ≡ p³q mod N:C·n⁻¹ mod N 退化为 p²,整数开方直接分解 n
crypto/rsa · verified
一句话结论
题目除了普通 RSA 的 c = m³ mod n 之外,还额外输出 C ≡ p³·q (mod N)(N 是另一对 2048 bit 素数 P·Q 的模数);因为 p³q = p²·(pq) = p²·n,所以 C·n⁻¹ ≡ p² (mod N),而此时 p² 只有约 2002 bit 小于 2048 bit 的 N、没有发生模约减,对 C·n⁻¹ mod N 直接开平方就得到 p,接下来 q = n//p、求 d 解出明文。
原理
- 代数化简:
C = p³q mod N = (p²)·(p·q) mod N = p²·n mod N。因此C·n⁻¹ ≡ p² (mod N),攻击者第一步只做一次模逆。 - 为什么能开方而不需要 Coppersmith:
p是 1001 bit,p²约 2002 bit,而N = P·Q是 2048 bit(P、Q各 1024 bit)。于是p² < N,p² mod N不产生回绕,C·n⁻¹ mod N的取值恰好等于整数p²,gmpy2.iroot(·, 2)一次得到p。 - 边界条件:只要
p² < N就成立;若p与N的因子量级接近(例如P、Q与p同位数),p² > N会产生回绕,就需要枚举k使得p² = C·n⁻¹ + k·N且为完全平方(或改用 Coppersmith 求p的小根)。 - 另一条并行线索:
c = m³ mod n用e=3正常解密即可(d = inverse(3, (p-1)(q-1))在p,q ≢ 1 mod 3时存在,题目正是用while p%3==1生成素数保证可逆)。 - 为什么这个“多输出”是致命的:
n本来只该在m³ mod n里作为模数出现,把n的因子乘进一个模另一个模数的表达式里,等于把n的因子以“平方”形式泄露给攻击者;两个互不相干的 RSA 实例被同一个乘积式绑在一起。
触发条件
- 同时给出
n(被分解目标)、N(另一个模数)、c、C。 C的表达式含p的幂次与q的乘积,使得C ≡ p^k·n mod N且p^k < N。e与p-1、q-1互素(本题e=3,素数生成时避开了≡1 mod 3)。
利用步骤
- 读输出得到
n, c, N, C。 - 算
D = C * inverse(n, N) % N,验证D的 bit 长度约等于2 * bitlen(p)。 p = gmpy2.iroot(D, 2)[0],检查n % p == 0;不整除则说明发生了回绕,改用k枚举或 Coppersmith。q = n // p,d = inverse(3, (p-1)*(q-1)),m = pow(c, d, n),long_to_bytes取 flag。- 校验:
pow(m, 3, n) == c且p*q == n。
PoC
from Crypto.Util.number import inverse, long_to_bytes
import gmpy2
n, c, N, C = ...
D = C * inverse(n, N) % N
p = gmpy2.iroot(D, 2)[0]
assert n % p == 0
q = n // p
d = inverse(3, (p - 1) * (q - 1))
m = pow(c, d, n)
assert pow(m, 3, n) == c
print(long_to_bytes(int(m)))
变体与关联
- 变体:
C ≡ p²·q² mod N时C·n⁻² ≡ 1,无信息;要挑“指数差 2 且能约掉n”的形式才有用。 - 变体:
C ≡ p³·q mod N且p² > N时,枚举k ∈ [0, ⌈p²/N⌉]使D + kN为完全平方,通常k很小。 - 变体:若给的是
C ≡ p^e·q mod N、e稍大,而p^e已超N,则需 Coppersmith 求p小根;可复用 [[crypto-rsa-prime-bit-chunks-multivariate-coppersmith-tiered]] 的框架。 - 关联:[[crypto-rsa-multiprime-cube-hint-linear-prime]](开立方型提示)、[[crypto-rsa-perfect-square-modulus-p-squared]](模数本身是完全平方)、[[crypto-rsa-e3-small-plaintext-integer-cube-root]](同样是“密文未模约减”的开方思路)。
检测与防御
- 防御:绝不把模数因子以乘积/幂的形式放进任何对外输出;本题的
C属于纯粹的“出题式泄露”,真实系统里对应的是把私钥材料拼进签名中间值。 - 防御:
e=3且无随机填充本身已不安全;再加上因子泄露,等同于直接公布私钥。 - 检测:输出中出现两个不同模数的组合式(一个模数作模、另一个模数的因子作乘数)时应立即拒绝生成。
- 响应:该密钥对作废;同时检查是否有任何日志/接口把
p的幂次运算中间值外泄。