♧ Godown 安全知识树

已知 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)且没有额外填充/编码层。

利用步骤

  1. 计算 D = H*H - 4*N,用 math.isqrt(D) 开方;校验 root*root == D,否则检查 H 是否有误或需要小范围搜索。
  2. 计算 p = (H + root)//2、q = (H - root)//2;校验 p*q == N。
  3. 取较小因子 r = min(p, q);计算 d = pow(e, -1, r-1)(要求 gcd(e, r-1)==1)。
  4. m = pow(c, d, r);用 long_to_bytes(m) 解码,检查是否以 flag{ 开头或符合明文格式。
  5. 若结果不对,改用完整分解:phi = (p-1)*(q-1)(或 λ = lcm(p-1,q-1)),d = pow(e, -1, phi),m = pow(c, d, N)。
  6. 若 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 完全失效,换更长密钥也不能弥补参数泄漏;应重新生成密钥对。