0CTF – Equation

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

\begin{array}{l} \texttt{Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNt} \\ \texttt{V4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4} \\ \texttt{xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF} \\ \texttt{7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU} \\ \texttt{8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx} \end{array}

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:

q = \texttt{0x}\underbrace{\texttt{***********}}_{\text{unknown data}} \texttt{3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b}

we define

q' = \texttt{0x3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b}.

Moreover, we have

\begin{array}{rl} d_p = d \bmod (p-1) = & \texttt{0xd5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d3} \\ & \texttt{86da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59},\end{array}
\begin{array}{rl} d_q = d \bmod (q-1) = & \texttt{0x1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b95301} \\ & \texttt{5e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3},\end{array}


\begin{array}{rl} q^{-1} \bmod p = & \texttt{0xd5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f} \\ &\texttt{0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431}.\end{array}

So, what can one do with this information? Well, the first thing we can notice is that we look for a prime q such that e \cdot d_q \equiv 1 \bmod q (I made the assumption that e = 65537) and it has the form q = X*2^j + q'. I counted j to be 198 bits, so that becomes q = X*2^{198} + q'.

Rewriting the above, we get e \cdot d_q - 1 - (q'-1)i = X*2^{198} for some integer i. I computed q 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 q, which is

\begin{array}{rl}q = & 125028936349231615998244651464070698822285137769477072954768059973117768558790 \\ & 24002289593598657949783937041929668443115224477369136089557911464046118127387\end{array}

or in hex

\begin{array}{l}\texttt{0xeeb8defdf9f0aec0036116ac9d84ab925e7606e9ba4618bfc50d7fa42d3ecf7} \\  \texttt{901aa5867c782ea}\underbrace{\texttt{3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b}}_{=q'}.\end{array}

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

Now, we want to determine p. We have the relations e \cdot d_p - 1 \equiv 0 \bmod (p-1) and q^{-1}\cdot q \bmod p. Again, rewriting we get e \cdot d_p - 1 = k \cdot (p-1) = k \cdot p - k and q^{-1}\cdot q = m \cdot p for integers m,k. With a little further manipulation, we get the final e \cdot d_p - 1 + k = q^{-1}\cdot q \bmod p.

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

\begin{array}{rl}p = & 128834299396391004790030585185232484938216882076971384178346312186380275645623\\ &  06620214863988447681300666538212918572472128732943784711527013224777474072569.\end{array}

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!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s