A bit different from the other challenge, we are given an image with a PEM-encoded private key. This was a bit cumbersome to deal with at first. I used an OCR software to obtain the partial data (whilst manually checking it for computer made mistakes). This was the image:

In text form, we have

I then generated a key without any password using

openssl genrsa -out privkey.pem 1024

and noted that the keys were of the same size. So with some cut and paste into the generated key, I could get an ASN.1 viewer to extract the information I needed. This was the information that was possible to extract:

we define

Moreover, we have

and

So, what can one do with this information? Well, the first thing we can notice is that we look for a prime such that (I made the assumption that ) and it has the form . I counted to be 198 bits, so that becomes .

Rewriting the above, we get for some integer . I computed as follows:

for j in range(198, 201):
    for i in range(1,100000):
        y = gmpy.gcd(e*d_q - 1 - (q_p-1)*i, 2**j)
        if log2(y) > (j-2): break
    X = (e*d_q-1-(q_p-1)*i) / 2**j / i
    q = 2**j*X + (q_p)
    
    if e*d_q % (q-1) == 1:
        print 'Hacked the shit out of q:',q

…and we obtain , which is

or in hex

We see that it matches with the partial . Ok, so far so good!

Now, we want to determine . We have the relations and . Again, rewriting we get and for integers . With a little further manipulation, we get the final .

We run

z = qinv*q
u = e*d_p
for j in range(0,10000000):
    if gmpy.gcd(u-1+j,z-1) > 10000:
        print j, gmpy.gcd(u-1+j,z-1)

and obtain

Good, now we are basically done.

N = p*q
ciph = s2n(open('flag.enc').read().rstrip())
d = invmod(e, (p-1)*(q-1))
print n2s(pow(ciph,d,N))

gives 0ctf{Keep_ca1m_and_s01ve_the_RSA_Eeeequati0n!!!}. Nice!