同模数多把 RSA 私钥:Coppersmith 补全缺失 e + HGS 小私钥分解 N
crypto/rsa · verified
一句话结论
三把损坏的 RSA 私钥共用同一个 1024-bit n,其中两把只缺 e 的低 256 bit;用 (e_hi·2^256+x)^3 ≡ fingerprint (mod n) 的 Coppersmith 小根恢复完整 e,再利用三把私钥的 d 只有 384 bit(≈n^0.375)且共享 n,用 Howgrave-Graham–Seifert 多密钥小私钥攻击分解 n,最后以 E=e0·e1·e2 解密。
原理
- 部分 e 恢复:已知
e = e_hi·2^256 + x,0 ≤ x < 2^256,且e^3 ≡ fingerprint (mod n)。构造f(x)=(e_hi·2^256+x)^3-fingerprint,在模n下求小根;x只有 256 bit,远小于 Coppersmith 界(n为 1024 bit,三次多项式界约n^(1/3)≈341 bit),small_roots(X=2^256, beta=1.0)可恢复。 - HGS 多密钥小私钥:多把密钥共享
n,私钥d_i满足e_i d_i ≡ 1 (mod φ(n)),即e_i d_i - 1 = k_i φ(n)。若d_i较小,可用 Howgrave-Graham–Seifert 的格方法同时利用多组(e_i, n)求φ(n)的倍数,进而分解n。论文给出的界:两个密钥且d < n^0.357时可高效恢复;样本增多时界可到n^0.5。本题d≈n^0.375,略高于 0.357,但有三把密钥,仍可解。 - 与 Wiener/Boneh-Durfee 的区别:Wiener 针对单密钥
d < n^0.25;Boneh-Durfee 针对单密钥d < n^0.292;HGS 利用“同一模数、多把密钥”的额外信息,把界推到n^0.357以上。本题d约 384 bit,n约 1024 bit,d≈n^0.375,单密钥方法不够,必须用多密钥 HGS。 - 分解后:
φ=(p-1)(q-1),d=inverse(E,φ),m=pow(c,d,n);E=e0·e1·e2是题目组合后的指数。 - 为什么成立:部分
e的未知量小,Coppersmith 可在多项式时间求小根;多密钥共享模数时,e_i d_i - 1与φ(n)的关系在格中形成短向量,LLL 可恢复φ(n)的倍数,从而解出p/q。
触发条件
- 多个 RSA 密钥共享同一
n(common modulus),且至少一个私钥指数d较小(d < n^0.357左右,密钥越多界越宽)。 - 部分公钥指数
e有已知高位、未知低位足够小(可 Coppersmith)。 - 有
fingerprint = e^3 mod n之类的校验值;有密文c和组合指数E。 - 能运行 Sage 的
small_roots与格基约减(LLL/BKZ)。 - 损坏的 PEM 仍能解析出共同的
n与残缺e;否则需要先修复/提取。
利用步骤
- 从损坏 PEM 提取共同的
n和残片e0/e1_hi/e2_hi;确认e1/e2各缺 256 bit。 - 对每个残片构造
f(x)=((hi<<256)+x)^3 - fingerprint,small_roots(X=2^256, beta=1.0)求x;用pow(e,3,n)==fingerprint校验。 - 得到
e0/e1/e2后,构造 HGS 多密钥格(多变量多项式、monomials、construct_relation),对alpha从 0.30 到 0.45 逐档尝试 LLL,解出φ(n)的倍数,进而求p/q(判别式s^2-4n为完全平方)。 - 计算
φ=(p-1)(q-1),d=inverse(e0*e1*e2, φ),m=pow(c,d,n),转字节得到 flag0xGame{Welcome home}。
PoC
R.<x> = PolynomialRing(Zmod(n))
B = 2^256
def recover(hi, fp):
f = ((hi * B + x)^3 - fp).monic()
roots = f.small_roots(X=B, beta=1.0, epsilon=0.05)
assert roots, "small_roots failed"
e = hi * B + int(roots[0])
assert pow(e, 3, n) == fp
return e
e1 = recover(e1_hi, fp1)
e2 = recover(e2_hi, fp2)
HGS 部分的核心是构造 L = [[pI_n,0,0],[M_A^T,I_n,0],[-B^T,0,c]] 之外的多密钥关系格:对每个 e_i 建立 e_i d_i - 1 = k_i φ(n) 的多项式,按 construct_relation() 生成 monomial 行,LLL 后从短向量反推 φ(n) 的倍数;原文用 alpha 从 0.30~0.45 逐档尝试,判别式开方得到 p/q。完整 hgs_factor() 较长,建议按论文/原文实现并用 p*q==n 校验。
变体与关联
- 变体(单密钥小 d):Wiener(
d<n^0.25)、Boneh-Durfee(d<n^0.292);本题d≈n^0.375,单密钥方法不够。 - 变体(部分私钥泄露):若已知
d的高位/低位,用部分密钥暴露攻击(Coppersmith)恢复d或分解n。 - 变体(共模):若同一明文用同一
n、不同互素e加密,直接用共模攻击(扩展欧几里得)恢复明文,不需要私钥。 - 关联卡片:[[crypto-rsa-common-modulus]](共模攻击)、[[crypto-rsa-multiprime-partial-key-coppersmith]](Coppersmith 小根与 beta 下调)、[[crypto-rsa-fermat-close-prime-factorization]](分解)、[[crypto-rsa-pollard-pminus1-smooth-prime]](分解)。
- 边界:
d超过 HGS 界、密钥样本不足、e缺失位数超过 Coppersmith 界时不可行;PEM 损坏严重/缺失n时需先恢复;LLL 参数/alpha选错会失败。
检测与防御
- 密钥生成:每个密钥使用独立
n,不要复用模数;n至少 2048 bit;d必须足够大(≥n^0.5更安全),避免小私钥。 - 密钥保护:私钥文件不要部分泄露/损坏后继续使用;发现
e指纹可被验证时,尽快轮换密钥。 - 检测:审计中搜索共享
n的多把公钥/私钥、异常小的d、损坏 PEM 中的残缺e;CTF 中看到fingerprint=e^3 mod n与多把同n私钥时,按本卡先补e再 HGS。 - 响应:一旦确认模数复用或私钥部分泄露,视为密钥已失陷,立即吊销/轮换并排查历史密文。