dp或dq泄露

1.dp和dq的泄露（已知dp，dq，p，q，c）

公式推导转载至https://blog.csdn.net/qq_32350719/article/details/102719279

原本dp和dq的作用是用来加快加解密速度的,但是由于dp和p,dq和q的关系密切,一旦泄漏,将造成很大的安全隐患

这里就不再次赘述了,只写出对解题相关的

  • dp = d mod(p-1)
  • dq = d mod(q-1)
  • InvQ * q = 1 mod p

数学推导最后得出：

  • m1 = c^{dq }mod q
  • m2 = c^{dp} mod p
  • m = (((m2−m1)∗p−1 mod q)p+m1) mod n

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2  
from Crypto.Util.number import long_to_bytes  

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

InvQ=gmpy2.invert(q,p)  
mp=pow(c,dp,p)  
mq=pow(c,dq,q)  
m=(((mp-mq)*InvQ)%p)*q+mq  

print(long_to_bytes(m))

2.只有dp的泄露（已知dp，e，n，c）

公式推导如下： 转载至 （https://blog.csdn.net/weixin_45859850/article/details/109559190）

550Nz6.png

攻击思路：通过公式推导可以确定p-1在（0，e）区间，因此对程序遍历（e+1种可能），求出(p-1)得到p且能被n整除；接下来就是常规RSA的解法得到d。

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 as gp

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751


for i in range(1,e):                   
    if(dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1) == 0:   
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi=(q-1)*(p-1)            
            d=gp.invert(e,phi)         
            m=pow(c,d,n)               
           
print(m)                              

print(bytes.fromhex(hex(m)[2:]))      
# b'flag{wow_leaking_dp_breaks_rsa?_98924743502}'