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,e101 bit); p, q为常规 1024 bit 素数,e与φ互素。
利用步骤
- 由
hint还原dp的高位:leak = hint << 180,dp = leak + x,x < 2^180。 - 在
PolynomialRing(Zmod(n))上构造f = e*(leak + x) + (y - 1)。 - 用二元 Coppersmith(
small_roots(f, (2^180, 2^180), m=1, d=4))求小根(x0, y0)。 dp = leak + x0,k = y0,p = (e*dp - 1)//k + 1;校验n % p == 0。φ=(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)与恒定时间实现,避免高位泄露。