$d_p$ 泄露应该是每个密码手必会的基础攻击之一了，前段时间复习了一下这些基础攻击，发现了一种用Coppersmith的 $d_p$ 泄露解法，这种方法不再需要 $e$ 可枚举，所以是一种更广义的解法

后来我把这道题放在Sloth的选拔赛上，结果是全防出去了啊，~~如果今年招不到密码手的话锅估计是我来背了x~~

先给一下题目的代码：


from secret import flag
import libnum

bits = 1024
p, q = [random_prime(2^bits) for _ in range(2)]
n = p * q
e = 2*10^76-3
d = e.inverse_mod((p-1) * (q-1))
dp = d % (p-1)

m = libnum.s2n(flag)
c = pow(m, e, n)

print('e  = %d' % e)
print('n  = %d' % n)
print('dp = %d' % dp)

print('c  = %d' % c)

'''
e  = 19999999999999999999999999999999999999999999999999999999999999999999999999997
n  = 7195506839435218889565105541674965483194164483027741709706696451513641438345177472634371310250998546706062462270851552911697354605048972081656931006641878545036542923897114647393564522132057589249800431430995780074871171268958056358251827104531889348948541240686274977093185746573748206617663459128090693743840574459752890533065398493485714768878646999590143805843490432318539260302521682823958290340460403361801534822098048095280034600065200137857346827560676300256938953222718633375808719441534702981763523406056651752914141143665893462943582116716812913462656214604870428310720751101481210148746546806273965485289
dp = 34961801811050613471700883525108632060492526395401334090302835931304663757529660746363964830407055340550990256271716811099606849841913560556222756478612800702209651907866303152581107449312861896692310607989826809665245295483724533775337076019316812377921373194504440845718347150919782506437242366281376701299
c  = 3014636373048664939954772778404195986026862165799593915685719641505606570670923436003664110094703916031096486273947905494103538805486521321522443488182065845367347589071783679908494724693530639371358965655992560909299314626568439587755874253430614726720724608456333450258184012429367293386944954388615812902809362326474915645899324083994448117282677622943580354006160302366855350193039875335543211982510928721395526768129547143054319585071252781483346116972611571317425047748862917945459911485505200762492537496489429730213393936533514665994680707861503489288913062785427211743828345144957201996243444547648085230048
'''

复习·

先来简单地复习一下普通的 $d_p$ 泄露解法，总所周知， $d_p \equiv d \pmod {p-1}$ ，所以把这个关系代入 $ed \equiv 1 \pmod {\varphi(n)}$ 中可得：

$e d_p \equiv 1 \mod {(p-1)}$

展开即存在 $k < e$ 使得：

$e d_p - 1 = k (p-1)$

即：

$p = \frac{e d_p - 1}{k} + 1$

一般情况下， $d_p$ 泄露的题目都会给一个可以枚举的 $e$ ，通常是 $e=65537$ ，由于 $k<e$ ，所以可以通过枚举 $k$ 算得 $p$ ，然后对 $n$ 进行分解

但在这个题目中 $e = 2 \cdot 10^{76}-3$ ，显然不可枚举，于是不能用这种解法

思路·

稍微分析一下可知 $n$ 是2048 bits，所以 $e$ 相对于 $n$ 是“小”的，于是可以首先想到用格去解，或者用Coppersmith

下面构造一下Coppersmith的式子，上面已经计算得：

$e d_p - 1 = k (p-1)$

整理一下即：

$e d_p - 1 + k = k p$

模 $p$ ：

$e d_p - 1 + k \equiv 0 \pmod p$

令 $A = e d_p - 1$ ，令 $x = k$ ，就是解同余方程：

$A + x \equiv 0 \pmod p$

这个方程的解法和RSA的素数 $p$ 部分泄露解法相同，即使用Coppersmith解方程

$A + x \equiv 0 \pmod n$

中未知数 $x$ 的一个解，由于 $p$ 是 $n$ 的因子，所以 $x$ 也是 $A + x \equiv 0 \pmod p$ 的一个解

具体的界我就直接引用Steven书上的结论了（懒

大概就是在

$e < n^{1/4 - \epsilon}$

的时候可以解，其中 $\epsilon$ 是误差

实测的话如果 $n$ 是2048 bits，那么 $e$ 在490+ bits时可解，我测的时候把small_roots的epsilon设为0.02，如果不调epsilon的话只能440+ bits，使用更小的epsilon估计会有更好的效果，不过耗时太久就没继续往下测了

EXP·

#!/usr/bin/env sage

e  = 19999999999999999999999999999999999999999999999999999999999999999999999999997
n  = 7195506839435218889565105541674965483194164483027741709706696451513641438345177472634371310250998546706062462270851552911697354605048972081656931006641878545036542923897114647393564522132057589249800431430995780074871171268958056358251827104531889348948541240686274977093185746573748206617663459128090693743840574459752890533065398493485714768878646999590143805843490432318539260302521682823958290340460403361801534822098048095280034600065200137857346827560676300256938953222718633375808719441534702981763523406056651752914141143665893462943582116716812913462656214604870428310720751101481210148746546806273965485289
dp = 34961801811050613471700883525108632060492526395401334090302835931304663757529660746363964830407055340550990256271716811099606849841913560556222756478612800702209651907866303152581107449312861896692310607989826809665245295483724533775337076019316812377921373194504440845718347150919782506437242366281376701299
c  = 3014636373048664939954772778404195986026862165799593915685719641505606570670923436003664110094703916031096486273947905494103538805486521321522443488182065845367347589071783679908494724693530639371358965655992560909299314626568439587755874253430614726720724608456333450258184012429367293386944954388615812902809362326474915645899324083994448117282677622943580354006160302366855350193039875335543211982510928721395526768129547143054319585071252781483346116972611571317425047748862917945459911485505200762492537496489429730213393936533514665994680707861503489288913062785427211743828345144957201996243444547648085230048

PR.<x> = PolynomialRing(Zmod(n))
f = e * dp + x - 1
f = f.monic()
roots = f.small_roots(X=e, beta=0.47)
assert roots

k = Integer(roots[0])
assert (e * dp + k - 1) % k == 0

p = (e * dp + k - 1) // k
assert n % p == 0
q = n // p

phi = (p-1) * (q-1)
d = Integer(e).inverse_mod(phi)
m = Integer(pow(c, d, n))
flag = bytes.fromhex(m.hex())
print(flag.decode())

总结·

一点小小的改进（：