1st Crypto CTF 2019 – Least Solved Challenges

Brief solution ideas to the least solved Crypto CTF challenges.

Midnight Moon

We can see that the primes are generated as follows. Let $m$ be the right half of the flag (as an integer) and $l$ be its byte length. We repeat the transformation $m \mapsto ((m+1)\cdot l)\oplus l$ until $m$ is prime. This is the first prime $p$. Then we set $m = (2m+1)$ and repeat the first transformation until we get another prime. As a result, the second prime $q$ is approximately equal to $2 l^e p$, where $e$ is the number of iterations in the last process. We can guess $e$ and $l$ (note that $e$ is upper bounded by $log_l n$) and then apply the Fermat factorization method to the number $2 l^e n = 2 l^e p q$. It should work since $2 l^e p \approx q$. Since $e$ can vary a lot, we can only hope that the approximation is good enough. However, there is a little subtlety with the Fermat method. It works only if both close factors have the same parity, which is not the case: $2l^e p$ is even and $q$ is odd. This of course can be easily overcome by multiplying the number by $4$, which corresponds to multiplying both close factors by 2.

In the challenge the modulus can be factored with $l=27$ and $e=442$. The next step is to guess the number of applications of the transformation $m \mapsto ((m+1)\cdot l)\oplus l$ when going from initial $m$ to the first prime $p$. After trivial inversion of the transformation, we obtain the right half of the flag: “4D3_1n__m1dNi9hT_witH_L0v3!}”. We could study the encryption function to decrypt the first half, but we can already guess the whole flag: “CCTF{M4D3_1n__m1dNi9hT_witH_L0v3!}”, which is correct.

Starving Parrot

The primes are generated by taking two random values and applying some fixed unknown polynomial to them. Once the two values are primes, the process is finished. Since we have access to the polynomial, we can easily recover it, for example by putting 10000000000000000000000000000000 as input we can clearly see the output 100…003700..002019. The polynomial is trivially deduced: $x^{13} + 37x+2019$. It follows that
$$n = (r^{13} + 37r+2019) \cdot (s^{13} + 37s+2019)$$
for some $r,s$ of size roughly 55 bits. Observe that $\sqrt[13]{n}$ provides a good approximation of $rs$. In fact, in the given setting $\lfloor \sqrt[13]{n} \rfloor = rs$. This number has 108 bits and can be easily factored:
$$\begin{multline*}251970989651144357978582196759904 = 2^5 \cdot 11 \cdot 13^2 \cdot 61 \cdot 239 \cdot 491\cdot\\ \cdot 3433 \cdot 137383 \cdot 1254599604823.\end{multline*}$$
This number has 2304 divisors in total. Each divisor gives a candidate for $r$ and its complement is a candidate for $s$. By applying the polynomial to them, we can obtain potential prime factors and check if they result in the same modulus. In the challenge we obtain
$$\begin{align*}r &= 30132816491977336,\\ s &= 15416171199104228.\end{align*}$$
Given the factorization, we can easily decrypt the message (don’t forget to invert the operations applied to the message before squaring):

“CCTF{it5____Williams____ImprOv3d_M2_Crypt0yst3m!!!}”.

Oliver Twist

We can recognize the (twisted) Edwards curve addition formulas:
$$\begin{align*}
x_3 &\equiv (x_1 y_2 + y_1 x_2) / (1 + d  x_1 x_2 y_1 y_2)\pmod{p},\\
y_3 &\equiv (y_1 y_2 – a x_1 x_2) / (1 – d x_1 x_2 y_1 y_2) \pmod{p}.
\end{align*}$$
In our case $a=3$ and $d=2$. You can learn a bit about twisted Edwards curves for example from slides by Christiane Peters. We are given $y$-coordinate of a point that was generated from the flag in a particular way. In order to find the $x$ coordinate, we have to plug the $y$ coordinate into the curve equation and solve for $x$:
$$3x^2 + y^2 – 2x^2y^2-1\equiv 0 \pmod{p}.$$
This is a quadratic equation in $x$ and we can easily find both roots. One of them is significantly smaller than $p$, so we can assume that this is the one we are looking for. This point $(x,y)$ is obtained from doubling the point $(m’, y)$ $(m’ \mod 3)$ times, where $m’$ is generated from the flag. Since we found a small $x$, we can guess that $m’ \mod 3 = 0$ and no squarings occured and that $x = m’$. Now, $m’$ is generated from the flag $m$ by adding $\sum_{i=1}^t 2^i + 3i$ to it for some small integer $t \ge 313$. We guess $t$ and subtract the added terms. We obtain for $t=313$ the flag:

“CCTF{N3w_But_3a5Y_Twisted_Edwards_curv3_Crypt0sys7em}”.