picoCTF Write-up ~ Pwning RSA (1/2)

ctf
encryption
rsa

#1

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


(exploit) #2

Awesome, keep it up dude :smiley:


(pico) #3

Instead of using the on-line services (that are perfectly fine), you can convert those numbers like this:

$ echo "obase=16;BIG_DECIMAL_NUMBER" | bc
$ echo "HEX_SEQUENCE" | xxd -r -p

Or in 1 shot

echo "obase=16;BIG_DECIMAL_NUMBER" | bc | xxd -r -p

Great post by the way!


#4

We might be looking at 0x00sec’s crypto wizard!


#5

awesome man!

so:

echo "obase=16;`python solve.py`" | bc | xxd -r -p

#6

This topic was automatically closed after 30 days. New replies are no longer allowed.