# 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}$

and

$\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

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