PicoCTF 2017: Weirder RSA (175)

An RSA problem! This writeup assumes basic knowledge of RSA.

Given:

"Another messaged encrypted with RSA. It looks like some parameters are missing. Can you still decrypt it?"

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

Hint: Is there some way to create a multiple of p given the values you have? Fermat's Little Theorem may be helpful.

Solution

The first thing I will try to do is solve for p. Because we are given n, computing q after getting p will be simple. With both p and q, the rest of the problem is relatively trivial.

From previous questions, we knew that dp was d%(p-1), where % is the modulus function. (NOTE: dp is NOT d*p. For multiplication, I will explicitly write "*".)

It then follows that d < p - 1.

We also know that d * e = 1 % (p - 1). This is simply writing down the modular multiplicative inverse part of RSA.

d * e = 1 % (p-1) is the same as ((d % (p-1)) * (e % (p-1))) % (p-1) = 1 % (p-1).

Then by the definition of modulus, we get dp * e = k * (p-1) + 1, where k is some unknown integer.

Because dp < p-1, it follows the k ≤ e.

Because e is a relatively small number, it is easy to simply try all the values of k from 1 to e until we can find a corresponding integer value of p that will satisfy dp * e = k * (p-1) + 1.

So I wrote a python script that went something like this (mod inverse function and some obvious variables not included for sake of legibility):

l = dp * e - 1
p = 0
for k in range(1, e):
    if l%k == 0:
        p = (l//k + 1)
        if n%p == 0:
            q = n//p
            t = (p-1)*(q-1)
            print(pow(c,modinv(e,t),n))

3670434958110785066911905751469631231338751225710158680692616521935747246580688484040488309932916523151997

flag{wow_leaking_dp_breaks_rsa?_98924743502}