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

image-20260204150625294

  • 首先来介绍一下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泄露的核心推导公式，也是与之前的小私钥攻击的核心公式一样，都使用的是密钥等式这一核心式子。

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

dp泄露

方法一

  • 这里的dp泄露并不是单指dp泄露，而是dp或dq其中之一泄露。

    • 当加密指数比较小的时候，在小私钥攻击的时候就有讲过一个式子。
    • 此时$k$就比较小，这样就可以在有限的时间遍历求出$k$。从而泄露出密钥等式的一些信息。

  • 接下来我们回到密钥等式来看看$dp$泄露的推导过程：

    • 首先由于$dp$泄露，所以我们知道了这个同余关系$d_p\equiv d~mod(~p-1)$
    • 接下来我们先考虑$dp$泄露的这个同余式，并且密钥等式是关于$\phi(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$是小指数加密的情况就可以直接遍历求解了。
      • 遍历$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*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$是误差。

1

  • 对于$k$的界限，我们可以由如下这个式子确定：

方法三

  • 参考博客：RSA中dp泄露的广义解法 | Tover’s Blog
  • 方法一的条件比较特殊，方法二需要用上Coppersmith，需要sage，并且当界限不满足的时候也没办法求出，而方法三是针对一般情况，一般的$d_p$泄露最好都使用这种方法来做会更好一点。
  • 在这个博客中发现只要$d_p$泄露出来，用gcd()就可以直接分解$n$了，接下来我们推到一下：
    • 这个方法其实是运用费马定理分解（一开始的时候没想到，看了风二西的视频后才想起来的，这个分解方法在KPCTF2024的密码题有一题）
    • 首先我们要用上这个式子：$ed_p\equiv 1~mod(~p-1)$与$ed_p=1+k(p-1)$
    • 这个是我们要引入一个数$a$，这个$a$其实需要满足$(a,p)=1$，也就是满足使用费马定理的条件。
    • 接下来就有这个式子：$a^{ed_p}\equiv a^{1+k(p-1)}~mod(~p)$
    • 通过费马小定理就可以得到：$a^{1+k(p-1)}\equiv a*a^{(p-1)^k}~mod(~p)\equiv a~mod(~p)$
    • 所以我们就可以得到：$a^{ed_p}\equiv a~mod(~p)$，这样就得到：$a^{ed_p}=a+kp$这个记为①式，但是此时我们$p$是未知的。
    • 这个时候就要用上$n$，我们假设：$a^{ed_p}\equiv x~mod(~n)$，其中这个$x$是我们是可以算出来的。
    • 根据同余的性质，其实就有：$a^{ed_p}\equiv x~mod(~p)$，一般来说$x>p$，这样也可以得到：$a^{ed_p}=x+k’p$这个记为②式。
    • 此时我们用①式-②式，就可以得到这样的式子：$0=a-x+(k-k’)p$
    • 所以我们就得到了这个整除关系：$x-a=(k-k’)p\Rightarrow p|(x-a)$
    • 这样我们就可以直接用$gcd(x-a,n)=p$
  • 这个算是$d_p$泄露的通解了，本质上是费马分解。

题型一 方法一

题型1 题目1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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$泄露的题型：
    • 其中有公钥对$(e,n)$，并且$n=pq$
    • 并且还泄露了$d_p\equiv d~mod(~p-1)$
    • 那我们就可以根据$d_p*e=1+k(p-1)$这个式子爆破出这个$k$
    • 最终达到分解$n$的目的
  • exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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的选拔赛

  • 题目附件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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$的界限就行：
  • 直接贴上exp：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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的题目）

  • 题目附件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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$泄露，除了使用爆破求解$k$，从而分解$n$，接下来便使用$gcd$的方式分解$n$
    • 首先选取$m=111$，并计算$c_1\equiv m^{e}~mod(~n)$
    • 其次计算$m’=c^{d_p}~mod(~n)$
    • 接下来分解$p=gcd(m’-m,n)$
  • exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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$泄露，除了使用爆破求解$k$，从而分解$n$，接下来便使用$gcd$的方式分解$n$
    • 首先选取$m=111$，并计算$c_1\equiv m^{e}~mod(~n)$
    • 其次计算$m’=c^{d_p}~mod(~n)$
    • 接下来分解$p=gcd(m’-m,n)$
  • exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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泄露

推导

  • 参考博客：RSA侧信道攻击-CSDN博客

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

    • 设$(e,N)$是有效的RSA加密实例，其对应的私钥为$(d,p,q)$，已知$d_p$、$d_q$以及$p、q$和对应的密文$c$，目标是求出$m$。
    • 首先我们考虑密钥等式：
    • 已知$d_p,d_q$就可以将密钥等式转换为如下形式：
    • 所以就有如下的式子，这个式子其实就是CRT等式：
    • 由$d_p$和$d_q$定义，我们可以得到两个同余方程，也就式子$①、②$，回顾一下中国剩余定理如果$p-1$与$q-1$互素的话，那可以很容易恢复$d$，但是非常遗憾$p-1$和$q-1$至少都有一个公因数$2$，所以CRT的方法恢复$d$就失效了。
    • 此时我们就需要使用$p、q$来进行求解，我们考虑如下式子：
    • 那么由费马小定理就可以得到如下同余式子：
    • 由于$p,q$是互素的那么我们就可以直接使用$m_p$和$m_q$通过CRT恢复出明文$m$，这个就是不直接恢复私钥$d$，而是通过恢复$m_p$和$m_q$利用CRT恢复明文$m$

  • 上面是使用CRT恢复明文m，但是这个效率还是稍微低了点，为了更高的解密效率，还可以优化一下这个计算过程，优化如下：

    • 首先我们考虑这个式子：
    • 将这个同余式子转换为等式：
    • 将这两个式子相减：
    • 将相减的式子同时模上$q$：
    • 那么我们就可以求得$k_1$：
    • 那么就可以得到：
    • 注意：此时的$m_1$和$m_2$由于私钥$d$是没办法求出的，但是我们可以使用如下式子代替：

  • 通过对比，我们可以得到，使用加速后的方法求解明文可以少进行一次逆元计算，这样就可以提高计算效率。

例题1

  • 题目附件如下：
1
2
3
4
5
6
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

  • 根据上面的公式，我们可以使用CRT求解m，exp如下：
1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
p = 
q = 
dp = 
dq = 
c = 
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
m = CRT([m1,m2],[p,q])
print(long_to_bytes(m))
# b'noxCTF{W31c0m3_70_Ch1n470wn}'
  • 或者是根据加速运算的计算方法求得m，exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
p = 
q = 
dp = 
dq = 
c = 
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
q_inv = inverse(q,p)
m = m1 + (m1-m2)*q_inv*p
print(long_to_bytes(m))
# b'noxCTF{W31c0m3_70_Ch1n470wn}'