♧ Godown 安全知识树

dp 高位泄露(hint = dp>>180):二元 Coppersmith 求低位与 k 后分解 n

crypto/rsa · verified

一句话结论

当题目泄露 dp = e^{-1} mod (p-1) 的高位(hint = dp >> 180)时,利用 e·dp - 1 = k·(p-1) 可把「dp 的低 180 位未知、k 未知」写成模 p 的二元小根问题,用二元 Coppersmith 在 Zmod(n) 上求出两个小根,进而反解 p = (e·dp - 1)/k + 1 分解 n。

原理

  • dp ≡ e^{-1} (mod p-1) 等价于 e·dp ≡ 1 (mod p-1),即 e·dp - 1 = k·(p-1),其中 k < e。
  • 写成 e(dp_h·2^180 + x) - 1 ≡ 0 (mod p)(因为 p-1 ≡ -1 项被吸收进同余):e·dp - 1 = k(p-1) = kp - k,故 e·dp + (k - 1) ≡ 0 (mod p)。设 y = k - 1,就有 f(x, y) = e·(hint·2^180 + x) + y ≡ 0 (mod p)。
  • 未知模数 p 是 n 的因子;p ≥ n^{1/2},因此 f 在 Zmod(n) 上的小根若满足 |x| < 2^180、|y| < e ≈ 2^101,且 X·Y < p^{?} 的 Howgrave-Graham 界成立,就能用二元 Coppersmith 求出 (x, y)。本卡参数下 X·Y ≈ 2^281,小于 p^{1/2} ≈ 2^512,余量充足。
  • 求出 x 得 dp,求 y 得 k,于是 p = (e·dp - 1) // k + 1,q = n // p,常规解密。
  • 为什么用 Zmod(n) 而不是 Zmod(p):p 未知,但 f ≡ 0 (mod p) 且 p | n,在 Zmod(n) 上求小根同样能得到解(根的模数只是被放大),这是 partial key exposure 的标准做法。

触发条件

  • 已知 n, e, c,且 e 是较小的素数(k = (e·dp-1)/(p-1) < e,e 越大 y 的界越松,但 e 太大会使 y 的搜索空间变大);
  • 泄露 dp 的高位、缺失位数 t 满足 X·Y ≲ n^{1/2}(本例 t=180,e 101 bit);
  • p, q 为常规 1024 bit 素数,e 与 φ 互素。

利用步骤

  1. 由 hint 还原 dp 的高位:leak = hint << 180,dp = leak + x,x < 2^180。
  2. 在 PolynomialRing(Zmod(n)) 上构造 f = e*(leak + x) + (y - 1)。
  3. 用二元 Coppersmith(small_roots(f, (2^180, 2^180), m=1, d=4))求小根 (x0, y0)。
  4. dp = leak + x0,k = y0,p = (e*dp - 1)//k + 1;校验 n % p == 0。
  5. φ=(p-1)(q-1),d=e^{-1} mod φ,解出明文。

PoC

from Crypto.Util.number import long_to_bytes, inverse
from sage.all import PolynomialRing, Zmod

# small_roots 为 Howgrave-Graham 二元 Coppersmith 的通用实现(省略,见 Sage 常用模板)
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930

leak = hint << 180
R = PolynomialRing(Zmod(n), names=('x', 'y'))
x, y = R.gens()
f = e * (leak + x) + (y - 1)
res = small_roots(f, (2**180, 2**180), m=1, d=4)

dq_l, k = int(res[0][0]), int(res[0][1])
dp = leak + dq_l
p = (e * dp - 1) // k + 1
assert n % p == 0
q = n // p
d = inverse(e, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)))

变体与关联

  • 变体:泄露 dq 高位同理,换成 e·dq - 1 = k(q-1)。
  • 变体:缺失位数较大(X·Y > n^{1/2})时,可加 m/d 参数提高界,或先用 k 枚举(k < e 只有 10 万级)降为一元 Coppersmith。
  • 关联:[[crypto-rsa-dp-leak-enumerate-k-factorization]](枚举 k 的一元做法)、[[crypto-rsa-bivariate-coppersmith-two-small-roots]](二元 Coppersmith 模板)、[[crypto-rsa-partial-plaintext-high-bits-coppersmith]](明文高位泄露)。
  • 边界:e 很大(y 界接近 p)或缺失位数过多时格不够短,需更多泄露位或额外信息。

检测与防御

  • 检测(CTF 视角):看到 hint = (e^{-1} mod (p-1)) >> t 这类「把私钥参数右移」的提示,先试「构造 e·dp-1 = k(p-1) + Coppersmith」。
  • 防御(实现视角):任何 CRT 私钥参数(dp/dq/qinv)都不应部分外泄;硬件侧信道场景需做盲化(blinding)与恒定时间实现,避免高位泄露。