继续介绍RSA加密中关于私钥d的攻击，在本篇博客中，只会说明dp泄露与dq泄露的各种题型，而不会详细介绍dp、dq部分位泄露的题型，部分泄露的题型我将其分类为部分私钥泄露攻击这一类别中。
下面一张图片就是本篇博客要介绍的攻击类型：

首先来介绍一下dp和dq指的是什么，首先d通常指的就是私钥d，而p、q通常指的就是模数n的两个素数p、q。
- dp指的就是 $d_p\equiv d~mod(~p-1)$
- dq指的就是 $d_q\equiv d~mod(~q-1)$
对于dp或dq泄露的核心推导公式，也是与之前的小私钥攻击的核心公式一样，都使用的是密钥等式这一核心式子。

ed=1+k\lambda(N)\\ ed=1+k\phi(N)

接下来就直接进入正题，这类题型还是比较简单的，大部分都只用到数论，没有什么高深的数学知识。

dp泄露

方法一

这里的dp泄露并不是单指dp泄露，而是dp或dq其中之一泄露。
- 当加密指数比较小的时候，在小私钥攻击的时候就有讲过一个式子。
$0<k=\frac{ed-1}{\lambda(N)}<\frac{ed}{\lambda(N)}<min\{e,d\}$
- 此时 $k$ 就比较小，这样就可以在有限的时间遍历求出 $k$ 。从而泄露出密钥等式的一些信息。
接下来我们回到密钥等式来看看 $dp$ 泄露的推导过程：
- 首先由于 $dp$ 泄露，所以我们知道了这个同余关系 $d_p\equiv d~mod(~p-1)$
- 接下来我们先考虑 $dp$ $d p$ 泄露的这个同余式，并且密钥等式是关于 $\phi(N)$ $ϕ (N)$ 的
  - 对于 $dp$ 泄露我们有： $d_p\equiv d~mod(~p-1)$
  - 两边同时乘个 $e$ 就有： $d_p*e\equiv ed~mod(~p-1)$ 记为①式
  - 接下来我们就考虑密钥等式： $ed\equiv 1~mod(~\phi(N))$
  - 根据同余的性质就可以变成这样： $ed\equiv 1~mod(~p-1)$
  - 这样①式就可以将 $ed$ 转换为 $1$ ： $d_p*e\equiv 1~mod(~p-1)$
  - 将同余式转换成等式： $d_p*e= 1 + k(p-1)$
  - 此时就有 $0<k=\frac{ed_p-1}{p-1}<\frac{ed_p}{p-1}<min\{e,d_p\}$
- 当 $e$ $e$ 是小指数加密的情况就可以直接遍历求解了。
  - 遍历 $k\in (0,e)$ ，计算 $p=\frac{d_p*e-1}{k}-1$
  - 判断 $p$ 是否能整除 $n$ ，如果能整除 $n$ 就可以将 $n$ 分解出来了。
上面的推导过程就是方法一的 $d_p$ 泄露的处理方法。做几道例题就行了。

方法二

参考博客：RSA中dp泄露的广义解法 | Tover’s Blog
对于方法一中的遍历的方法还是比较特殊情况的，但是当 $d_p$ 和 $e$ 都很大的时候就会导致方法一失效。
这样我们就要来介绍一个方法二，方法二需要用上Coppersmith攻击。但是这个方法本质上还是求 $k$
对于方法一中的 $d_p$ $d_{p}$ 泄露推导，这里就不多介绍了：
- 方法一的 $d_p$ 泄露的推导，我们就需要使用这样的一个式子： $d_p*e= 1 + k(p-1)$
- 我们对这个式子变形一下就会得到： $ed_p-1+k=kp$
- 我们再对这个变形的式子模上 $p$ ： $ed_p-1+k\equiv 0~mod(~p)$
- 由于 $ed_p-1$ 的值我们是知道的， $k$ 的值我们不知道，不妨可以设 $x=k,b=ed_p-1$
- 那么我们的同余式就可以列出方程： $x+b\equiv 0~mod(~p)$
- 这个时候我们就可以转到模 $N$ 下求小根（构造思路与 $p$ 部分位泄露一样）： $x+b\equiv 0~mod(~N)$
- 当这个式子的未知数（小根） $x$ 满足Coppersmith攻击的界限的时候，就可以求解成功。
对于该情况的Coppersmith攻击的界限，就直接照抄Tover的图片了，界限 $e<n^{\frac{1}{4}-\epsilon}$ ，其中 $\epsilon$ 是误差。

方法三

参考博客：RSA中dp泄露的广义解法 | Tover’s Blog
方法一的条件比较特殊，方法二需要用上Coppersmith，需要sage，并且当界限不满足的时候也没办法求出，而方法三是针对一般情况，一般的 $d_p$ 泄露最好都使用这种方法来做会更好一点。
在这个博客中发现只要 $d_p$ $d_{p}$ 泄露出来，用gcd()就可以直接分解 $n$ $n$ 了，接下来我们推到一下：
- 首先我们有这个式子 $d_p\equiv d~mod(~p-1)$ ，这种情况 $d_p$ 我们其实可以看成是公钥对为 $(e,p)$ ，私钥对为 $(d_p,p)$ 的RSA加密，这个公私钥对记为RSA2
- 这个时候我们任意取一个 $m<p$ （这种引入一个新的数在leak类型的题目也很常见），将该 $m$ 使用公钥对 $(e,n)$ 进行加密，就会出现这样的式子： $c \equiv m^{e}~mod(~n)$
- 对于刚刚加密过的 $m$ ，根据同余的性质我们其实有： $c\equiv m^{e}~mod(~p)$
- 此时我们使用 $d_p$ 进行解密操作，由于 $m<p$ 所以可以保证还原出 $m$ ： $m\equiv c^{d_p}~mod(~p)$
- 但是此时我们并不能知道 $p$ ，但是可以使用这个式子得到一个p的倍数： $m-c^{d_p}\equiv 0~mod(~p)$ ，即 $m-c^{d_p}=kp$
- 这个时候我们计算 $gcd(c^{d_p}~mod(~n)-m,n)$ ，就可以自然分解得到 $p$ 了（这个地方可能有点不明白模 $n$ 不会改变其整除 $p$ ，这个在很多leak类题目都是这样搞的。）
这个算是 $d_p$ 泄露的通解了。

题型一方法一

题型1 题目1

题目来源：LitCTF 2023P_Leak | NSSCTF
题目附件如下：

from Crypto.Util.number import *
e=65537
m=bytes_to_long(b'xxxx')
p=getPrime(512)
q=getPrime(512)
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
dp=d%(p-1)
c=pow(m,e,n)
print("dp=",dp)
print("n=",n)
print("c=",c)
#dp= 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
#n= 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
#c= 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619

这个就是一个常规的 $d_p$ $d_{p}$ 泄露的题型：
- 其中有公钥对 $(e,n)$ ，并且 $n=pq$
- 并且还泄露了 $d_p\equiv d~mod(~p-1)$
- 那我们就可以根据 $d_p*e=1+k(p-1)$ 这个式子爆破出这个 $k$
- 最终达到分解 $n$ 的目的
exp如下：

import gmpy2
from Crypto.Util.number import *
dp= 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
n= 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
c= 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619
e = 65537
x = (dp*e-1)
for k in range(1,65537):
    p1 = x//k
    p = p1+1
    if n % p == 0:
        print("p=",p)
        print("q=",n//p)
p = 6806799523138018080299902882276558488747716843553684211592596116521280697310815421606971932213296208463550463809415551367299447277297860237756145281101709
q = 7435529578648849854035363871331880952240009932326862680743902402621727268266241566852168314449841733241705179681279879240181196857939144128592553250929153
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(int(m))
print(flag)
"""
p= 6806799523138018080299902882276558488747716843553684211592596116521280697310815421606971932213296208463550463809415551367299447277297860237756145281101709
q= 7435529578648849854035363871331880952240009932326862680743902402621727268266241566852168314449841733241705179681279879240181196857939144128592553250929153
b'LitCTF{Prim3_1s_Le@k!!!!!}'
"""

题型二方法二

题型2 题目1

题目来源：Sloth的选拔赛
题目附件如下：


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
'''

这题没啥好说的了，就直接Coppersmith攻击即可，只需要理由下面这个式子确定未知数 $k$ 的界限就行：

0<k=\frac{ed-1}{\lambda(N)}<\frac{ed}{\lambda(N)}<min\{e,d\}

直接贴上exp：

import gmpy2
from Crypto.Util.number import *
e  = 19999999999999999999999999999999999999999999999999999999999999999999999999997
n  = 7195506839435218889565105541674965483194164483027741709706696451513641438345177472634371310250998546706062462270851552911697354605048972081656931006641878545036542923897114647393564522132057589249800431430995780074871171268958056358251827104531889348948541240686274977093185746573748206617663459128090693743840574459752890533065398493485714768878646999590143805843490432318539260302521682823958290340460403361801534822098048095280034600065200137857346827560676300256938953222718633375808719441534702981763523406056651752914141143665893462943582116716812913462656214604870428310720751101481210148746546806273965485289
dp = 34961801811050613471700883525108632060492526395401334090302835931304663757529660746363964830407055340550990256271716811099606849841913560556222756478612800702209651907866303152581107449312861896692310607989826809665245295483724533775337076019316812377921373194504440845718347150919782506437242366281376701299
c  = 3014636373048664939954772778404195986026862165799593915685719641505606570670923436003664110094703916031096486273947905494103538805486521321522443488182065845367347589071783679908494724693530639371358965655992560909299314626568439587755874253430614726720724608456333450258184012429367293386944954388615812902809362326474915645899324083994448117282677622943580354006160302366855350193039875335543211982510928721395526768129547143054319585071252781483346116972611571317425047748862917945459911485505200762492537496489429730213393936533514665994680707861503489288913062785427211743828345144957201996243444547648085230048
b = dp*e-1
P.<x> = PolynomialRing(Zmod(n))
f = x + b
result = f.small_roots(X=e,beta=0.4)
print(result)
a = result[0] + b
p = gmpy2.gcd(int(a),n)
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
"""
[8285854266086836372223825792633215255480037326765944136613664818968699699497]
b'HSCTF{47cfc8fd-e4e0-46a3-a610-47860d29f479}'
"""

题型三方法三

题型3 题目1

题目来源：Sloth的选拔赛（同题型2题目1的题目）
题目附件如下：


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}$ 泄露，除了使用爆破求解 $k$ $k$ ，从而分解 $n$ $n$ ，接下来便使用 $gcd$ $g c d$ 的方式分解 $n$ $n$
- 首先选取 $m=111$ ，并计算 $c_1\equiv m^{e}~mod(~n)$
- 其次计算 $m'=c^{d_p}~mod(~n)$
- 接下来分解 $p=gcd(m'-m,n)$
exp如下：

import gmpy2
from Crypto.Util.number import *
e  = 19999999999999999999999999999999999999999999999999999999999999999999999999997
n  = 7195506839435218889565105541674965483194164483027741709706696451513641438345177472634371310250998546706062462270851552911697354605048972081656931006641878545036542923897114647393564522132057589249800431430995780074871171268958056358251827104531889348948541240686274977093185746573748206617663459128090693743840574459752890533065398493485714768878646999590143805843490432318539260302521682823958290340460403361801534822098048095280034600065200137857346827560676300256938953222718633375808719441534702981763523406056651752914141143665893462943582116716812913462656214604870428310720751101481210148746546806273965485289
dp = 34961801811050613471700883525108632060492526395401334090302835931304663757529660746363964830407055340550990256271716811099606849841913560556222756478612800702209651907866303152581107449312861896692310607989826809665245295483724533775337076019316812377921373194504440845718347150919782506437242366281376701299
c  = 3014636373048664939954772778404195986026862165799593915685719641505606570670923436003664110094703916031096486273947905494103538805486521321522443488182065845367347589071783679908494724693530639371358965655992560909299314626568439587755874253430614726720724608456333450258184012429367293386944954388615812902809362326474915645899324083994448117282677622943580354006160302366855350193039875335543211982510928721395526768129547143054319585071252781483346116972611571317425047748862917945459911485505200762492537496489429730213393936533514665994680707861503489288913062785427211743828345144957201996243444547648085230048
m1 = 111
c1 = pow(m1,e,n)
m11 = pow(c1,dp,n)
p = gmpy2.gcd(m11-m1,n)
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(int(m))
print(flag)
"""
b'HSCTF{47cfc8fd-e4e0-46a3-a610-47860d29f479}'
"""

题型3 题目2

题目来源：LitCTF 2023P_Leak | NSSCTF
题目附件如下：

from Crypto.Util.number import *
e=65537
m=bytes_to_long(b'xxxx')
p=getPrime(512)
q=getPrime(512)
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
dp=d%(p-1)
c=pow(m,e,n)
print("dp=",dp)
print("n=",n)
print("c=",c)
#dp= 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
#n= 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
#c= 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619

常规的 $d_p$ $d_{p}$ 泄露，除了使用爆破求解 $k$ $k$ ，从而分解 $n$ $n$ ，接下来便使用 $gcd$ $g c d$ 的方式分解 $n$ $n$
- 首先选取 $m=111$ ，并计算 $c_1\equiv m^{e}~mod(~n)$
- 其次计算 $m'=c^{d_p}~mod(~n)$
- 接下来分解 $p=gcd(m'-m,n)$
exp如下：

import gmpy2
from Crypto.Util.number import *
dp = 5892502924236878675675338970704766304539618343869489297045857272605067962848952532606770917225218534430490745895652561015493032055636004130931491316020329
n = 50612159190225619689404794427464916374543237300894011803225784470008992781409447214236779975896311093686413491163221778479739252804271270231391599602217675895446538524670610623369953168412236472302812808639218392319634397138871387898452935081756580084070333246950840091192420542761507705395568904875746222477
c = 39257649468514605476432946851710016346016992413796229928386230062780829495844059368939749930876895443279723032641876662714088329296631207594999580050131450251288839714711436117326769029649419789323982613380617840218087161435260837263996287628129307328857086987521821533565738409794866606381789730458247531619
e = 65537
m1 = 111
c1 = pow(m1,e,n)
m11 = pow(c1,dp,n)
p = gmpy2.gcd(m11-m1,n)
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(int(m))
print(flag)
"""
b'LitCTF{Prim3_1s_Le@k!!!!!}'
"""

dp和dq泄露

推导

当 $d_p$ 和 $d_q$ 都已经泄露出来后，其实没有必要像上面 $d_p$ 泄露那样做，直接进行解密然后用 $CRT$ 求解正确的flag就行了。对于 $d_p$ 与 $d_q$ 都泄露的理由 $CRT$ 求解，这其实是RSA变种之一CRT-RSA核心解密原理。

RSA加密之dp与dq泄露

dp泄露

方法一

方法二

方法三

题型一方法一

题型1 题目1

题型二方法二

题型2 题目1

题型三方法三

题型3 题目1

题型3 题目2

dp和dq泄露

推导

例题1

dp泄露

方法一

方法二

方法三

题型一 方法一

题型1 题目1

题型二 方法二

题型2 题目1

题型三 方法三

题型3 题目1

题型3 题目2

dp和dq泄露

推导

例题1

题型一方法一

题型二方法二

题型三方法三