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