picoCTF 2017 - weirderRSA Writeup

crypto
,

We have the public key, which consist of and , and the encrypted flag .

1
2
3
4
5
e = 65537
n = 352758655756163603130656475864162239004344663459120398951306959672239055329877644796995008368282924624780849432051543118959312685532106237568240835778731486989439626252834661294225426875963944816709371554839452465119058016363040631618359944564550348310851045841670935254841385590882490443247265126417117450357
dp = 13530055667815347122266109008252377134325151556131892235929064596659462917644020624855537451062167377041847601387880412738836767351591511886432133011921729

c = 23428056833770750219439218340180501853506449797628734848807388355447212714387039203998085387476974936419607861041793755542930286287098871510394661091846780839592290953853536571372997807697657464569729651718518301857979495046280018444198435962234642736892075369840282923945267377104440625478468507147243879631

Understanding the hint

The hint given is to find a multiple of . Since in RSA , we have , , , . Thus there exist such that .
From we have and then ; so , a reasonable value to bruteforce such keeping in mind that should be an integer that divides .

Attack

Using Python, the gmpy2 library is useful to compute the modular multiplicative inverse. The code is very simple:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import gmpy2
e=65537
n=352758655756163603130656475864162239004344663459120398951306959672239055329877644796995008368282924624780849432051543118959312685532106237568240835778731486989439626252834661294225426875963944816709371554839452465119058016363040631618359944564550348310851045841670935254841385590882490443247265126417117450357
dp=13530055667815347122266109008252377134325151556131892235929064596659462917644020624855537451062167377041847601387880412738836767351591511886432133011921729
c=23428056833770750219439218340180501853506449797628734848807388355447212714387039203998085387476974936419607861041793755542930286287098871510394661091846780839592290953853536571372997807697657464569729651718518301857979495046280018444198435962234642736892075369840282923945267377104440625478468507147243879631

stuff=dp*e-1
for k in range(1,e):
    if stuff%k==0:  #p should be an integer
        p1=stuff//k+1
        if n%p1==0: #p should divide n
            p=p1
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(bytes.fromhex(hex(pow(c,d,n))[2:]))

and returns the flag flag{wow_leaking_dp_breaks_rsa?_47413771836}