• 在RSA中有一种题型是就是已知dp或者dq这一类题型。简单说一下dp、dq这两个

dp≡d mod(p−1)dq≡d mod(q−1)\begin{array}{l} dp \equiv d ~mod(p-1)\\ dq \equiv d ~mod(q-1) \end{array}

  • 接下来就归纳一下dp、dq泄露的一些RSA加密相关的题型。

题型1_已知dp,dq,p,q,c

RSA侧信道攻击-CSDN博客

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

方法一

  • 接下来对这个过程进行推导

dp≡d mod(p−1)dq≡d mod(q−1)由于m≡cd mod(n)可以得到m≡cd mod(p)在RSA加密中有ed≡1 mod(phi(n))所以就有ed≡1 mod(p−1)即edp≡1 mod(p−1)所以得到e≡dp−1 mod(p−1)当e比较小的时候,就可以得到e,之后就可以正常求d\begin{array}{l} dp\equiv d ~mod(p-1)\\ dq\equiv d ~mod(q-1)\\ 由于\\ m \equiv c^d~mod(n)\\ 可以得到\\ m \equiv c^d~mod(p)\\ 在RSA加密中有\\ ed \equiv 1~mod(phi(n))\\ 所以就有\\ ed \equiv 1~mod(p-1)\\ 即\\ ed_p \equiv 1~mod(p-1)\\ 所以得到\\ e \equiv d_p^{-1}~mod(p-1) \\当e比较小的时候,就可以得到e,之后就可以正常求d \end{array}

  • exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
n = p*q
import libnum
import gmpy2
e = gmpy2.invert(dp,p-1)
print(e)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

方法二

题型2_只有dp泄露(已知dp,e,n,c)

情况1_e比较小

  • 题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import libnum
import gmpy2
from uuid import uuid4
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
flag = b'flag' + str(uuid4()).encode()+b'}'
m = bytes_to_long(flag)
phi = (p-1)*(p-1)
d = gmpy2.invert(e,phi)
dp = d % (p-1)
c = pow(m,e,n)
print("c=",c)
print("e=",e)
print("dp=",dp)
print("n=",n)
"""
c= 17903389155084064476875300798787458860010822336124225302980898809939416920158705605508390250286333720412625513671092206933830330067684522812065436129123169919211735111409445535760670653407924847182019142248053919509570903175607375444321539955863283723120719170835395137919048480834500584336359758092548345248650430753339247056308099257555565253447883586567521614543802862716630103936439012364987028888084096624906906990190288289753086859110805733141610256395995740284888339524480178884455471294756076813633953333574445052248597288115260150589705184819295527059473349287469935490699076844586633853019433800215877933316
e= 65537
dp= 6352603443898977504044367404284930204125487330296105180662267171681990257785156719451182492889438759968557086170848827570432423414661280505213694591577890648872743220537032737681104568264790196220609588283922012236552133550886857604976447928240525230876094924797571342492618459275450500806170407398608206337
n= 18343811749613740461646915968660871242958488199004349375615446954827735334075789879738722071607088485034345483797350182700482481895340028322879676926760966419198036214451133351800666947971371587811455384771477795749439728557504308026363013059257164093818726469835190593773723129633256774657014484683876444779919787810418368382065516662429793354393864139244683570045431165503606363089814592016829853173864673072444439941464410347865938603684792353624037325988949250878391014866374277601164971927135520978969875859746400899763458844493200219341053388021284783262276052610903392188107384453085514529459634538552260336453
"""

  • 接下来推导一下：

  • exp如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum
import gmpy2
c= 17903389155084064476875300798787458860010822336124225302980898809939416920158705605508390250286333720412625513671092206933830330067684522812065436129123169919211735111409445535760670653407924847182019142248053919509570903175607375444321539955863283723120719170835395137919048480834500584336359758092548345248650430753339247056308099257555565253447883586567521614543802862716630103936439012364987028888084096624906906990190288289753086859110805733141610256395995740284888339524480178884455471294756076813633953333574445052248597288115260150589705184819295527059473349287469935490699076844586633853019433800215877933316
e= 65537
dp= 6352603443898977504044367404284930204125487330296105180662267171681990257785156719451182492889438759968557086170848827570432423414661280505213694591577890648872743220537032737681104568264790196220609588283922012236552133550886857604976447928240525230876094924797571342492618459275450500806170407398608206337
n= 18343811749613740461646915968660871242958488199004349375615446954827735334075789879738722071607088485034345483797350182700482481895340028322879676926760966419198036214451133351800666947971371587811455384771477795749439728557504308026363013059257164093818726469835190593773723129633256774657014484683876444779919787810418368382065516662429793354393864139244683570045431165503606363089814592016829853173864673072444439941464410347865938603684792353624037325988949250878391014866374277601164971927135520978969875859746400899763458844493200219341053388021284783262276052610903392188107384453085514529459634538552260336453
for i in range(1,e+1):
    p = (e*dp-1)//i +1
    q = n//p
    phi = (p-1)*(q-1)
    d = gmpy2.invert(e,phi)
    m = pow(c,d,n)
    flag = libnum.n2s(int(m))
    if b'flag' in flag:
        print(flag)
# b'flag99070f7e-ae58-486d-92ab-90a459733431}'

情况2_e比较大-方式1

  • 参考博客：RSA中dp泄露的广义解法 | Tover’s Blog
  • 当e比较大的时候爆破的这种方式就失效了，需要使用Coppersmith攻击去打，其实还有另一种方法，在方式2中有介绍。
  • 题目附件如下：
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
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
'''

情况2_e比较大-方式2

  • 参考：哔哩哔哩up主，风二西
  • 题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
import libnum
from Crypto.Util.number import *
from uuid import uuid4
flag = b'flag{' + str(uuid4()).encode() + b'}'
m = libnum.s2n(flag)
p = getPrime(1024)
q = getPrime(1024)
e = getPrime(128)
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
dp = d % (p-1)
c = pow(m,e,n)
print("n=",n)
print("e=",e)
print("c=",c)
print("dp",dp)
"""
n= 20321619613599238327562742433784398114829270105049108058460237334459070259926555778823052291765799404251085130724314686188208820777643216315393790411957239711736324610882563747582351553148706221674531708365618046565831731176618232774641296792030699817748347153021835519691955437816148513470603323199091035218364568767719728360525210658253097647287639202220624724272464419588750833971771515207204364559454815656166322072549920086679791985702206781553219053953280237509411034619938334953962401099376320738437024373521643865078331922997308506082760932456320948587430133513571885015104153268936985341100091008238720621633
e= 205434228073239326738506746716772526219
c= 11548642221770841541811392635821507507312161150718724228944896682361048856460170100776821457863788622415757532070924873036643692894408425910069424138157684828462542394521344510597108637993240742147039842815166789931700881117140041621679859298392564565882103258018604979328969687943701895143578495578994092850798505869593698145717740105772683349750333656214296648580914491240862802638015485788316085774808715506750628847177519517863808091337783912653531947811391127282655881624482986557917081859143955319928610919824077418622800384052044379790585048270639841508079751079225952756599907751904776970181110738831204448836
dp 45211659884540488379100671132417131379082091573785518811912180572463131709514767206976474092474859759936034844026596940793684057801067767662543343505890455248162156452399368758882227723665226243761701887223395899770504343019400329508540740945264220072804901134107828177254649467221779098783534884348776312499
"""

题型3_已知dp部分位

题目1_已知dp高位

其他dp、dq相关题型