pwnthem0le

Home Blog About GitHub

pwnthem0le is a Turin-based, hacking students group born out of CyberChallenge 2018. Read more about us!

21 September 2018

picoCTF 2017 - weirderRSA Writeup

by matpro98

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

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:

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}

tags: crypto  rsa