# TetCTF 2021: unevaluated

TetCTF is the first CTF I have played in 2021. I recalled from last year that they have cool challenges. This year, there are three crypto challenges. In particular, *unevaluated* is the hardest among them. Although I did not solve them, I dug into rabbit holes and had a lot of struggle, uh, fun.

## Challenge Summary⌗

There is a 128-bit prime $p$. Define $\cdot: \mathbb{Z}_{p^2}^2\times\mathbb{Z}_{p^2}^2\rightarrow\mathbb{Z}_{p^2}^2$ by

\[(x_1, y_1)\cdot(x_2, y_2) := \left(\left(x_1x_2-y_1y_2\right)\ \text{mod}\ p^2, \left(x_1y_2+y_1x_2\right)\ \text{mod}\ p^2\right),\]

where $(x_1, y_1), (x_2, y_2) \in \mathbb{Z}_{p^2}^2$. Also, define for $k\in\mathbb{N}$ and $G \in \mathbb{Z}_{p^2}^2$, $G^k = G \cdot G \cdot ... \cdot G$. Given that $G, H \in \mathbb{Z}_{p^2}^2$, the objective is to find $k\in\mathbb{N}\cap\left[0, 2^{256}\right)$ such that $H = G^k$.

## Solution⌗

**Clickbaited!**This writeup is not original and has referred (or stolen) to several sources (Thanks rkm0959 and CryptoHack!). I would like to write this up for my own reference. Anyway, this is more like a story than a solution.

### Part I: What is the order composed of?⌗

Since $p$ and $k$ are respectively 128 and 256 bits long, it is expected to recover two out of $k\ \text{mod}\ p$, $k\ \text{mod}\ q$ and $k\ \text{mod}\ r$ to compute $k$. It is interesting to see the order being a product of three primes $p, q, r$, with $q | (p-1)$ and $r | (p+1)$.

I have defined $\text{norm}: \mathbb{Z}_{p^2}^2 \rightarrow \mathbb{Z}_{p^2}$ by $\text{norm}(x, y) = (x^2 + y^2)\ \text{mod}\ p^2$ and experimented a bit and discovered some of the properties:

- The imaginary part of $G^{pr}$ is zero.
- $\text{norm}(G^{pq}) = 1$, and

If we are working on $\mathbb{Z}_p$ instead of $\mathbb{Z}_{p^2}^2$, then

- The imaginary part of $G^r$ is zero.
- $\text{norm}(G^q) = 1$, and

The following code snipped is used to verify the above properties.

```
# Under mod n
P = complex_pow(G, p*r, n) # P.im == 0
dQ = norm(complex_pow(G, p*q, n), n) # dQ == 1
# Under mod p
P = complex_pow(G, r, p) # P.im == 0
dQ = norm(complex_pow(G, q, p), p) # dQ == 1
```

This make me think: If we consider a *polar coordinate representation* where $G = \rho e^{i\theta}$, with $\rho\in R$ and $\theta\in A$, then $R \cong \mathbb{Z}_{pq}$ and $A \cong \mathbb{Z}_{pr}$. Hence, we can imagine that the subgroup that $G$ generates is isomorphic to $\mathbb{Z}_{pq}\times\mathbb{Z}_{pr}$.

### Part II: Stealing the ideas from an existing cryptosystem⌗

Solving discrete log under modulo $n^2$ does not seem difficult. For example, we can see from Paillier cryptosystem that discrete logarithms under modulo $n^2$ can be computed easily. In this way, we can compute $x\ \text{mod}\ p$ with:

\[x \equiv \frac{\mathcal{L}(h^{p-1}\ \text{mod}\ p^2)}{\mathcal{L}(g^{p-1}\ \text{mod}\ p^2)}\ (\text{mod}\ p),\]

where $\mathcal{L}(x) = \frac{x-1}{p}$, like how a ciphertext is decrypted with the Paillier cryptosystem. Hence we have $x\ \text{mod}\ p$.

**Mini Checklist**

- $x\ \text{mod}\ p$
- $x\ \text{mod}\ q$
- $x\ \text{mod}\ r$

### Part III: Solving 128-bit discrete logarithm⌗

Let's try to work on $\mathbb{Z}_{p}^2$ instead of $\mathbb{Z}_{p^2}^2$. This reminded me the challenge *galiver* in ASIS CTF Finals 2020. I searched the discussion on CryptoHack's Discord server, and found...

Okay, *works for 128-bit $p$ rather fast*. So this must be discrete logarithm. Let's try it? Since the imaginary part for $G^r, H^r$ are zero, I tried `discrete_log(H^r, G^r, q)`

on Sage. After five minutes, my PC crashed. I could not solve it during the CTF. After the game, rkm0959 publishes the writeup on the CTF and he used `h.log(g)`

and have got it working. In his writeup, he uses a *norm map* which is isomorphic to the subgroup that $G^r$ generates.

```
p = 206109322179011817882783419945552366363
q = 103054661089505908941391709972776183181
r = 17175776848250984823565284995462697197
G = (20878314020629522511110696411629430299663617500650083274468525283663940214962,
16739915489749335460111660035712237713219278122190661324570170645550234520364)
H = (11048898386036746197306883207419421777457078734258168057000593553461884996107,
34230477038891719323025391618998268890391645779869016241994899690290519616973)
Zp = GF(p)
g = Zp(G[0]**2 + G[1]**2) # equivalently, g = Zp(complex_pow(G, r, p).re)
h = Zp(H[0]**2 + H[1]**2) # and h = Zp(complex_pow(H, r, p).re)
assert g^q == 1
x_mod_q = h.log(g)
print('x % q =', x_mod_q) # 26176203815975575469683683780455489251
```

**Takeaway.**Sage is powerful. It tooks 3 minutes for my PC to compute the discrete log, where the time complexity should be $\mathcal{O}(\sqrt{q})$. Also,

*do not use*

`discrete_log(h, g)`

. Use `h.log(g)`

instead.
**Mini Checklist**

- $x\ \text{mod}\ p$
- $x\ \text{mod}\ q$
- $x\ \text{mod}\ r$

### Part IV: Combining the building blocks⌗

With Chinese remainder theorem, we are able to recover $x_0 := x\ \text{mod}\ pq$. It may not equal to $x$, but they are differ from a small multiple of $pq$. We can simply compute $x_0 + kpq$ for some small $k\in\mathbb{N}$ until $k$ is obtained. After that we have the flag - `TetCTF{h0m0m0rph1sm_1s_0ur_fr13nd-mobi:*100*231199111007#}`

. This challenge makes me think more about discrete logarithm, and I am amazed by the capability of Sage. I am still wondering why discrete logarithm of a 128-bit prime can be computed in just a few minutes...