dp与dq泄露

RSA中泄露dp/dq公式推导

学习出处：https://skysec.top/2018/08/25/RSA%E4%B9%8B%E6%8B%92%E7%BB%9D%E5%A5%97%E8%B7%AF-2/

https://skysec.top/2018/08/24/RSA%E4%B9%8B%E6%8B%92%E7%BB%9D%E5%A5%97%E8%B7%AF(1)/ /)

已知dp e n

推导

已知

dp ≡ d mod (p-1)

e d ≡ 1 mod (p-1) (q-1) ①

得

e dp ≡ e d mod (p-1)

=> e d = k1(p-1) + e * dp

代入①式

e dp + k1 (p-1) = k2 (p-1) (q-1) + 1

e dp = (p-1)(k2(q-1) - k1) + 1

由于 dp < p-1 => e > k2 * (q-1) - k1

设 x = k2 * (q-1) -k1

遍历(0,e) 若x 满足整除e * dp -1，且结果(p-1) + 1能整除n，则成功分解n

例题

[BUU]RSA2

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

解题

from Crypto.Util.number import *
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for x in range(1,e+1):
    if (e*dp-1)%x==0 and n%((e*dp-1)//x+1)==0:
        p=(e*dp-1)//x+1
        break
q=n//p 
d=inverse(e,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))

#b'flag{wow_leaking_dp_breaks_rsa?_98924743502}'

已知dp dq p q

推导

由中国剩余定理可知，我们可以通过①②式联立求出m

m1 ≡ mod p ①

m2 ≡ mod q ②

=> m ≡mod n

由①式 = k * p + m1

代入②式 m2 = (k * p + m1) mod q

(m2 - m1) ≡ k*p mod q

因为gcd(p,q)=1

k ≡ (m2 - m1) * mod q

再将结果代入 = k * p + m1

= ((m2 - m1) mod q) p + m1

=> m ≡ (((m2 - m1) mod q) p + m1) mod n

求出m1,m2即可

dp ≡ d mod (p-1)

=> d = k * (p-1) + dp

代入 ≡ m1 mod p

≡ m1 mod p

由费马小定理(p是大素数，显然和c互素)

≡ m1 mod p

同理≡ m2 mod q

代入 m ≡ (((m2 - m1) mod q) p + m1) mod n 中即可求得m

（当然m也可以直接通过crt求得）

题目

[BUU]rsa2

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

解题

from Crypto.Util.number import *
from libnum import solve_crt
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
m1=pow(c,dp,p)
m2=pow(c,dq,q)
m=(solve_crt([m1,m2],[p,q]))
print(long_to_bytes(m))

#noxCTF{W31c0m3_70_Ch1n470wn}

总结

dp泄露可以通过分解n，根据已知的e求解RSA

而dp,dq同时泄露时，即使不知道e,d，也可以通过p,q直接求出明文m