# TU CTF – Secure Auth

This was a 150 point challenge with the description:

We have set up this fancy automatic signing server!
We also uses RSA authentication, so it’s super secure!

nc 104.196.116.248 54321

Connecting to the service, we get the following

Obviously, we cannot feed the message get_your_hands_off_my_RSA! to the oracle. So, we will only receive signatures, but no way to verify them; this means we don’t know either the public modulus, nor the public exponent. But, of course, we could guess the public exponent… there are a few standard ones: $3, 17, 65537...$

First, I obtained the signatures for $3$ and $4$ from the provided service. Denote these $s_3, s_4$, respectively. We note that given a correct public exponent $e$, we may compute $s_3^e = 3 + k \cdot N$ and $s_4^e = 4 + l \cdot N$. Inevitably, $\textnormal{gcd}(s_3^e-3,s_4^e-4) = \textnormal{gcd}(k,l)\cdot N$. Hoping for $\textnormal{gcd}(k,l)$ to be small, we can use serveral pairs until we find one that works.

Trying all the listed (guessed) public exponents, we find that $e = 65537$ (this was performed surprisingly fast in Sage with my Intel hexacore). Hence, we have now determined the modulus

$\begin{array}{rl} N = & 24690625680063774371747714092931245796723840632401231916590850908498671935961736 \\ &33219586206053668802164006738610883420227518982289859959446363584099676102569045 \\ &62633701460161141560106197695689059405723178428951147009495321340395974754631827 \\ &95837468991755433866386124620786221838783092089725622611582198259472856998222335 \\ &23640841676931602657793593386155635808207524548748082853989358074360679350816769 \\ &05321318936256004057148201070503597448648411260389296384266138763684110173009876\\ &82339192115588614533886473808385041303878518137898225847735216970008990188644891 \\ &634667174415391598670430735870182014445537116749235017327.\end{array}$

Now, note that

libnum.strings.s2n('get_your_hands_off_my_RSA!') % 3 == 0


OK, so we may split this message $m$ into a product of two message factors: $m_1 = 3$ and $m_2 = 166151459290300546021127823915547539196280244544484032717734177$ and sign them. Then, we compute the final signature $s = m^d = (m_1 \cdot m_2)^d = m_1^d \cdot m_2^d = s_1 \cdot s_2 \bmod N$. Mhm, so what now?

Phew 🙂