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!