RSA 私钥 d 低 530 位泄露:枚举 k 与 d 高位,用 s²−4n 完全平方直接分解 n
crypto/rsa · verified
一句话结论
已知 RSA 私钥 d 的低 m 位 dl、公钥 (n,e) 与密文 c 时,不需要 Coppersmith/Sage:对每个 k∈[1,e−1],用 d ≈ (k·n+1)/e 估计 d 的高位、在 d = dl + d_high·2^m 中枚举少量 d_high,再用 φ=(e·d−1)/k、s=n+1−φ 与判别式 s²−4n 是否为完全平方直接分解 n,最后求 d_real 解密。
原理
- RSA 关系:
e·d ≡ 1 (mod φ(n)),所以存在整数k使e·d − 1 = k·φ(n),且1 ≤ k < e(e=65537时只需枚举 65536 个k)。 - 已知低位:把
d写成d = dl + d_high · 2^m,其中dl = d mod 2^m是已知的低m位(原文m=530,dl的位数为 530,符合dl < 2^530)。 - 高位估计:
φ(n) = n − (p+q) + 1 ≈ n,因此d = (1 + k·φ)/e ≈ (k·n + 1)/e。令d_approx = (k·n+1)//e,则d_approx − dl ≈ d_high·2^m + (d_approx − d)。误差项约k·(p+q−1)/e ≈ k·2√n/e,在 1024 位n、e=65537时约 500 多位,小于2^530,所以d_high落在(d_approx−dl)//2^m附近一个很小的窗口(原文取 ±10)。 - 过滤:对每个候选
d先检查(e·d − 1) % k == 0;通过后令φ=(e·d−1)/k、s=n+1−φ。因为s=p+q,p,q是二次方程x² − s·x + n = 0的两根,判别式Δ = s² − 4n必须是完全平方;math.isqrt(Δ)平方回代即可得到p,q,再验证p·q == n。 - 为什么成立:低位泄露把
d的自由度压到“高位猜测”,k的枚举把φ的未知乘数消掉,判别式完全平方是极强的正确性过滤器;一旦分解成功,φ与d_real都可直接算出,无需恢复原始d。 - 与 Coppersmith 方法的区别:另一类“d 低位泄露”卡把
p的低位作为未知量,用solve_mod+small_roots恢复p;本方法直接枚举d的高位并用二次方程判别式分解,纯 Python 即可,不依赖 Sage/格。原文文字写“d 的高位泄露”,但其代码d = dl + d_high·2^530与dl < 2^530表明dl是低 530 位,应以代码/数学为准。
触发条件
- 已知
n、e、c,以及d的连续低m位dl(d mod 2^m)。 e较小(如 65537),可以枚举k=1..e−1;若e很大,枚举不可行,需要改用格/Coppersmith。m足够大,使高位估计误差落在可接受的窗口内;m太小或误差超过窗口时需要扩大搜索或换方法。d的低位必须是真正的二进制低位(d mod 2^m),不是十六进制前缀/高位片段。- 目标使用标准 RSA(
p,q为大素数,φ=(p−1)(q−1)),无特殊多素数/CRT 变体。
利用步骤
- 确认
dl是d mod 2^m:检查dl < 2^m,并向题目/代码确认m。 - 对
k = 1..e−1: -d_approx = (k*n + 1) // e; - 若d_approx < dl,跳过; -candidate = (d_approx - dl) // 2^m; - 在candidate ± 10范围内枚举d_high,令d = dl + d_high*2^m; - 检查(e*d - 1) % k == 0,不满足则继续。 - 令
phi = (e*d - 1) // k,s = n + 1 - phi;计算delta = s*s - 4*n。 - 若
delta >= 0且math.isqrt(delta)**2 == delta,得到p=(s+root)//2、q=(s-root)//2;验证p*q == n。 - 分解成功后
d_real = inverse(e, phi),m = pow(c, d_real, n),long_to_bytes(m)得到明文/flag。 - 若所有
k/窗口都失败,检查m是否足够、dl是否确为低位、e是否过大,必要时扩大d_high窗口或改用 Coppersmith。
PoC
import math
from Crypto.Util.number import long_to_bytes, inverse
n = 143504495074135116523479572513193257538457891976052298438652079929596651523432364937341930982173023552175436173885654930971376970322922498317976493562072926136659852344920009858340197366796444840464302446464493305526983923226244799894266646253468068881999233902997176323684443197642773123213917372573050601477
c = 141699518880360825234198786612952695897842876092920232629929387949988050288276438446103693342179727296549008517932766734449401585097483656759727472217476111942285691988125304733806468920104615795505322633807031565453083413471250166739315942515829249512300243607424590170257225854237018813544527796454663165076
dl = 1761714636451980705225596515441824697034096304822566643697981898035887055658807020442662924585355268098963915429014997296853529408546333631721472245329506038801
e = 65537
m_bits = 530
shift = 1 << m_bits
for k in range(1, e):
d_approx = (k * n + 1) // e
diff = d_approx - dl
if diff < 0:
continue
candidate_high = diff // shift
for d_high in range(max(0, candidate_high - 10), candidate_high + 11):
d = dl + d_high * shift
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
s = n + 1 - phi
delta = s * s - 4 * n
if delta < 0:
continue
root = math.isqrt(delta)
if root * root != delta:
continue
p = (s + root) // 2
q = (s - root) // 2
if p * q != n:
continue
d_real = inverse(e, phi)
print(long_to_bytes(pow(c, d_real, n)).decode())
raise SystemExit
print("not found")
说明:原文脚本对每个 k 只枚举 candidate_high ± 10,在 1024 位 n/e=65537 下成功恢复;如果目标参数不同,窗口大小需按误差上界调整。PoC 未在本机执行。
变体与关联
- 变体:已知
d的高位时,不能用本方法(d = high·2^k + low的低位未知),应使用 Coppersmith/格方法或枚举k后解p的低位,见关联卡。 - 变体:
e较大时,k的范围可能不是1..e−1的可枚举规模;可先用d ≈ k·n/e约束k的范围或改用部分密钥暴露的格攻击。 - 变体:若同时知道
d的低位和部分p/q信息,可把多个同余条件合并,缩小k/d_high搜索。 - 变体:多素数 RSA 的
φ形式不同,需按φ(n)=∏(p_i−1)重写s/判别式。 - 关联:[[crypto-rsa-private-exponent-low-bits-partial-p]](同为 d 低位泄露,但用 solve_mod + Coppersmith 恢复 p)、[[crypto-rsa-d-leak-factor-n-reuse-modulus-new-e]](完整 d 泄露 + 同模数新 e)、[[crypto-rsa-boneh-durfee-small-private-exponent]](小 d 的格攻击)。
- 边界:
m太小/误差超过窗口、e太大无法枚举、dl并非真正的低位、d不是标准 RSA 私钥指数时,本方法失败或需要换算法。
检测与防御
- 防御:私钥
d的任何连续位(尤其是低位)都不得出现在日志、错误信息、调试输出、侧信道或序列化结构中;不要在密钥生成/加载代码里截断打印d。 - 防御:使用 HSM/TPM 保存私钥,启用 RSA blinding 与常量时间实现,降低侧信道泄露;密钥损坏后不要继续使用或部分恢复。
- 检测:审计日志/接口中是否出现
d & ((1<<m)−1)、dl、d_low等字段;CTF 中看到“已知 d 的低 530 位”即可按本卡尝试。 - 响应:确认私钥部分泄露后视为密钥失陷,立即吊销并轮换模数与密钥,评估历史密文是否已被解密。