dq 低位泄露 + qinvp:用 qinvp·q²−q≡0 mod n 构造一元多项式,枚举 k 恢复 dq 并分解 n
crypto/rsa · verified
一句话结论
已知 n、e、dq 的低 120 位与 qinvp = q^{-1} mod p 时,由 e·dq ≡ 1 (mod q-1) 得 e·dq-1 = k(q-1)(0<k<e),再代入 qinvp·q² - q ≡ 0 (mod n),令 dq = 2^120·x + dq_low 并枚举 k,可构造关于 x 的一元模多项式,用 Coppersmith 小根求出 dq,进而 q=(e·dq-1)/k+1、p=n/q 完成分解。
原理
- dq 与 k 的关系:
dq = d mod (q-1),故e·dq ≡ e·d ≡ 1 (mod q-1),即e·dq - 1 = k·(q-1),且0 < k < e(因为dq < q-1)。于是q = (e·dq - 1)/k + 1。 - qinvp 给出模 n 的等式:
qinvp = q^{-1} mod p即qinvp·q ≡ 1 (mod p),写成整数qinvp·q = 1 + k2·p;两边乘q得qinvp·q² = q + k2·p·q = q + k2·n,因此t·q² - q ≡ 0 (mod n),其中t = qinvp。 - 消去 q 得到 x 的多项式:把
q = (e·dq-1)/k + 1代入并两边乘k²,整理得t·(e·dq-1)² + k·(2t-1)·(e·dq-1) + k²·(t-1) ≡ 0 (mod n)。 再把dq = 2^120·x + dq_low代入,得到只含未知x的二次模多项式(其余量已知)。 - 为什么 x 是小根:真实
dq使上述等式在模n下成立,而x = (dq - dq_low)/2^120是dq的高位部分,约512-120 = 392位;q整除n,因此多项式模n的小根即对应真实x。k未知但只有e-1 ≈ 65536个,逐个枚举即可。 - 恢复流程:命中
k后,dq = 2^120·root + dq_low,q = (e·dq-1)//k + 1,p = n//q,验证p*q == n;之后按普通 RSA 解密。
触发条件
- 泄露
dq的低若干位(原文 120 bit)与qinvp = q^{-1} mod p,同时给出n、e与密文; k的枚举空间0<k<e可接受(e=65537);- 未知
dq高位位数在 Coppersmith 界内(原文 392 bit,beta=0.5可解); - 能运行 Sage
small_roots。
利用步骤
- 计算
t = qinvp,确认dq_low的位数L(原文 120); - 对
k从e-1递减到1:构造dq = 2^L·x + dq_low,代入f(x) = t·(e·dq-1)² + k·(2t-1)·(e·dq-1) + k²·(t-1) mod n; f.monic()后调用small_roots(X=2^(pbits-L), beta=0.5)(原文kbit=512-120);- 若返回根,恢复
dq = 2^L·root[0] + dq_low、q = (e·dq-1)//k + 1、p = n//q,验证p*q == n; - 命中后计算
d = e^{-1} mod (p-1)(q-1)解密密文;若某k无根继续下一个。
PoC
# sage;原文蓝帽杯2022 corrupted_key 参数
t = qinvp
PR.<x> = PolynomialRing(Zmod(n))
dq = 2^120 * x + dq_low
kbit = 512 - 120
for k in range(e, 1, -1):
f = t * (e*dq - 1)^2 + k * (2*t - 1) * (e*dq - 1) + k^2 * (t - 1)
f = f.monic()
root = f.small_roots(X=2^kbit, beta=0.5)
if root:
dq = 2^120 * root[0] + dq_low
q = int((e*dq - 1)//k + 1)
p = n // q
if p*q == n:
print('dq =', dq, 'p =', p, 'q =', q)
break
变体与关联
- 对称情形:泄露
dp低位与pinvq = p^{-1} mod q时,可构造pinvq·p² - p ≡ 0 (mod n)的同型多项式; k范围:0 < k < e,e很小时可枚举;e很大时可结合k的近似值或其它泄露缩小范围;- 与库内
crypto-rsa-dp-high-bits-bivariate-coppersmith对比:后者用e·dp-1=k(p-1)构造二元小根(x 与 k 同时求),本卡用qinvp提供额外模 n 等式,把 k 枚举掉、只留一元 x; - 与
crypto-rsa-dp-dq-both-leak-crt-recombine-without-e对比:后者是 dp/dq 完整泄露后的 CRT 重组,不涉及 Coppersmith。
检测与防御
- 防御侧:不要在任何日志/报错/侧信道中泄露
dq的部分比特或q^{-1} mod p(CRT 中间值);CRT-RSA 实现应使用盲化(base blinding)与故障注入防护; - 使用足够大的素数并避免复用密钥;密钥生成后校验
dp/dq未被写入可访问的内存转储/配置; - 检测侧:看到
dq_low、qinvp、corrupted_key一类参数组合时,按本卡评估e·dq-1=k(q-1)与qinvp·q²-q≡0的可行性。