已知 N 与 p+q:解二次方程分解 RSA 并模小因子解密
crypto/rsa · verified
一句话结论
RSA 的 N = p*q 如果同时泄露了 H = p + q,则 p、q 是二次方程 x^2 - Hx + N = 0 的两个根:计算判别式 D = H^2 - 4N、开方后即可恢复 p、q;若只关心小于较小因子的明文,还可以直接用 d = e^{-1} mod (r-1) 在模 r 下解密,无需计算完整私钥。
原理
- 由韦达定理:
p + q = H、p*q = N,所以 p、q 满足x^2 - Hx + N = 0。 - 判别式
D = H^2 - 4N = (p-q)^2,在 p、q 为整数时 D 必为完全平方数;sqrt(D) = |p-q|。 - 两个根为
(H ± sqrt(D)) / 2,即 p、q;用isqrt配合整除校验可确认是否恢复成功。 - 恢复 p、q 后即可按标准 RSA 计算
d = e^{-1} mod λ(N)或mod φ(N),解出完整明文;如果密文对应的明文m小于较小因子r,还可以简化: c = m^e mod N,两边模 r 得c mod r = m^e mod r;- 取
d_r = e^{-1} mod (r-1),则m = c^{d_r} mod r; - 因为
m < r,模 r 的结果就是原始 m。 - 该简化在 CTF 中常见:flag 的整数值远小于 1024/2048 位素数,直接用较小因子即可恢复;若
m >= r或gcd(e, r-1) != 1,应改用完整分解 + CRT。 - 泄露
p+q的等价形式还有φ(N) = N - (p+q) + 1(已知 φ 可反推 H),以及直接给出p-q(同样可解二次方程)。
触发条件
- 已知 RSA 模数
N、公钥指数e、密文c,以及H = p + q(或φ(N)、p - q等等价信息)。 H^2 - 4N为完全平方数(或可通过小范围修正/爆破处理)。- 若使用“模小因子解密”简化,需要
m < min(p,q)且gcd(e, min(p,q)-1) == 1;否则用完整分解。 - 明文是整数编码(如
long_to_bytes)且没有额外填充/编码层。
利用步骤
- 计算
D = H*H - 4*N,用math.isqrt(D)开方;校验root*root == D,否则检查 H 是否有误或需要小范围搜索。 - 计算
p = (H + root)//2、q = (H - root)//2;校验p*q == N。 - 取较小因子
r = min(p, q);计算d = pow(e, -1, r-1)(要求gcd(e, r-1)==1)。 m = pow(c, d, r);用long_to_bytes(m)解码,检查是否以flag{开头或符合明文格式。- 若结果不对,改用完整分解:
phi = (p-1)*(q-1)(或λ = lcm(p-1,q-1)),d = pow(e, -1, phi),m = pow(c, d, N)。 - 若
D不是完全平方,检查H是否为p+q的变体(如H = φ(N)时先算p+q = N - φ + 1),或对H做小范围爆破。
PoC
import math
from Crypto.Util.number import long_to_bytes
N = 1537884748858979344984622139011454953992115329679883538491908319138246091921498274358637436680512448439241262100285587807046443707172315933205249812858957682696042298989956461141902881429183636594753628743135064356466871926449025491719949584685980386415637381452831067763700174664366530386022318758880797851318865513819805575423751595935217787550727785581762050732320170865377545913819811601201991319740687562135220127389305902997114165560387384328336374652137501
H = 154799801776497555282869366204806859844554108290605484435085699069735229246209982042412551306148392905795054001685747858005041581620099512057462685418143747850311674756527443115064006232842660896907554307593506337902624987149443577136386630017192173439435248825361929777775075769874601799347813448127064460190
c = 947079095966373870949948511676670005359970636239892465556074855337021056334311243547507661589113359556998869576683081430822255548298082177641714203835530584472414433579564835750747803851221307816282765598694257243696737121627530261465454856101563276432560787831589321694832269222924392026577152715032013664572842206965295515644853873159857332014576943766047643165079830637886595253709410444509058582700944577562003221162643750113854082004831600652610612876288848
e = 65537
D = H * H - 4 * N
root = math.isqrt(D)
assert root * root == D, "H^2-4N 不是完全平方"
p = (H + root) // 2
q = (H - root) // 2
assert p * q == N
r = min(p, q)
d = pow(e, -1, r - 1)
m = pow(c, d, r)
print(long_to_bytes(m).decode())
变体与关联
- 变体:已知
φ(N)时,p+q = N - φ(N) + 1,代回同一方程;已知p-q时,p = (H + (p-q))/2等。 - 变体:
N为多素数且已知各因子之和/部分和,可逐个解二次方程或构造高次方程。 - 变体:
m >= min(p,q)时,模小因子只能得到m mod r;应完整分解后用 CRT 或mod N解。 - 关联卡片:[[crypto-rsa-fermat-close-prime-factorization]](p、q 接近时用 Fermat 分解)、[[crypto-rsa-continued-fraction-lambda-factorization]](连分数/λ 分解)、[[crypto-rsa-wiener-small-private-exponent-large-e]](小私钥指数)。
- 边界:
D非完全平方通常说明 H 不是精确的 p+q,或 p、q 不是整数/存在额外因子;不要直接对浮点数开方,使用isqrt并校验。
检测与防御
- 检测:审计 RSA 参数生成/发布逻辑,确认
p+q、φ(N)、p-q、d等敏感值未被写入日志、调试接口、配置文件或错误消息。 - 修复:RSA 私钥参数(p、q、d、φ)必须保密;使用标准库生成密钥,避免自实现参数泄漏;对导出/调试信息做脱敏。
- 加固:使用 OAEP 填充、足够长的密钥(2048+),并定期轮换;对密钥生成环境做访问控制与审计。
- 边界:已知 p+q 后 RSA 完全失效,换更长密钥也不能弥补参数泄漏;应重新生成密钥对。