So as you might know, pysec, dtm, kowalski and me did the picoCTF some time back.
One of the challenges we did was an RSA one.
The challenge was as follows
e = 65537
n = 642313240848064014975043934308658242447312485152342673610756859535090103704610472004913349502648157091104463303511131278665176160214474038294042375555935567033107229886104534241324327133387923226576002115108963521725703773387678635509903034467838260875686083768549775481391190161412646384559222421917626615323
dp = 17765378008759755288183210466105878526943875374957170036175281330288884608317141953683920408636506981101765935449140323585600732241535721917282237462133813
c = 147903288008907053469880199469959588903705520519775597541160700501753344741954421604588338524905987922631822425828587114084662512860181022047137469441292833823381362238861070683420786510831001513730638949486694641768638258876688738949817816449109334961820861920165271653627904957302093274915248851406573361863
So as you might have seen in my previous article here we already know what e, n and c are.
e is the public key
n is the modulus
and c is the ciphertext.
But what’s this dp doing there?
Luckily there is this site that has some valuable info.
It seems that dp is defined as:
dP = (1/e) mod (p-1)
but wait.
Let’s pause here for a minute.
Notice two things here:
1/e ( inv(e) ) and (p-1).
What would happen if we’d multiply this by e?
You’d get a 1 mod, mod what?
It’s gotta be a 1 mod a multiple of (p-1).
So that means if you substract 1 from it, you’d get a multiple of (p-1).
But how does this help us and why would we even care about p?
Well from the other article I wrote that we know than n = p*q.
And that to calculate d we need phi(n).
If we manage to get p, we get q for free, since n / p = q.
And with p and q we can calculate phi(n).
With phi(n) we can calculate e^-1 which is d.
Then with d we can calculate c^d mod n = m!!!
So it turns out that finding p is crucial for solving this challenge and having a multiple of (p-1) sounds like a great start!.
But how would be get p from this multiple of p-1?
Use the computer!
There are two ways to solve this.
The one I used in the challenge was as following.
mp = (dp * e) - 1 #mp is multiple of p-1
for i in range(2,1000000):
p = (mp / i) + 1
if n % p == 0:
break
print p
Another way would be as following
mp = (dp * e) - 1
#notice that mp is a multiple of p-1
#mp = k*(p-1) = kp - k
for i in range (2,1000000):
kp = mp+i
if gcd(n,kp) > 0:
p = gcd(n,kp)
break
print p
This final solution works, because the gcd of kp and n would p, since p would divide both kp and n.
Having now found p. we can simple define q as
import gmpy2
q = n / p
phin = (p-1)*(q-1)
d = gmpy2.divm(1,e,phin)
m = gmpy2.powmod(c,d,n)
print m
Now m would still be very unreadable
m = 3670434958110785066911905751469631231338751225710158680692616521935747246580687863838005016679513421330301
So let’s first convert it to hex using this nice site:
http://www.mobilefish.com/services/big_number/big_number.php
We now have 666C61677B776F775F6C65616B696E675F64705F627265616B735F7273613F5F37373436373139303435377D
So let’s move to this other cool site
http://string-functions.com/hex-string.aspx
and so we get our flag:
flag{wow_leaking_dp_breaks_rsa?_77467190457}
That’s it!
Next article we will cover another RSA challenge from the picoCTF
