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
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 \(d_p < p-1\) and then \(d_p \cdot e=65537 \cdot d_p < 65537 (p-1)\); so \(k < 65537\), a reasonable value to bruteforce such \(k\) keeping in mind that \(p\) should be an integer that divides \(n\).
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}
crypto rsa