# pwnthem0le

## 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 $n$ and $e$, $d_p=d \pmod{p-1}$ and the encrypted flag $c$.

e = 65537
n = 352758655756163603130656475864162239004344663459120398951306959672239055329877644796995008368282924624780849432051543118959312685532106237568240835778731486989439626252834661294225426875963944816709371554839452465119058016363040631618359944564550348310851045841670935254841385590882490443247265126417117450357
dp = 13530055667815347122266109008252377134325151556131892235929064596659462917644020624855537451062167377041847601387880412738836767351591511886432133011921729

c = 23428056833770750219439218340180501853506449797628734848807388355447212714387039203998085387476974936419607861041793755542930286287098871510394661091846780839592290953853536571372997807697657464569729651718518301857979495046280018444198435962234642736892075369840282923945267377104440625478468507147243879631


## Understanding the hint

The hint given is to find a multiple of $p$. Since in RSA $d \cdot e \equiv 1 \pmod{\varphi(n)}$, we have $d \cdot e \equiv 1 \pmod{(p-1)(q-1)}$, $d \cdot e \equiv 1 \pmod{p-1}$, $d \pmod{p-1} \cdot e \equiv 1 \pmod{p-1}$, $d_p \cdot e=1 \pmod{p-1}$. Thus there exist $k \in \mathbb{Z}$ such that $d_p \cdot e=1+k(p-1);\ p=\dfrac{d_p \cdot e -1}{k}+1$. From $d_p=d \pmod{p-1}$ we have $% $ and then $% $; so $% $, a reasonable value to bruteforce such $k$ keeping in mind that $p$ should be an integer that divides $n$.

## 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