# K3RN3L CTF - Tick Tock

In this challenge we are given multiple diffie-hellman instances over a weird group. It is necessary to solve for the shared secret in each session to decrypt the flag.

The group $(G,+)$ is implemented in the class `TickTock`, each element is represented as a point $(x,y)$ in a prime field $F_p$ such that $x^2+y^2 \equiv 1 \pmod{p}$.

The addition formula is defined as $(x,y)+(z,w)=(xw+yz,yw-xz)$. It is easy to see that $(xw+yz,yw-xz)$ is still on the curve using [Brahmagupta's identity](https://en.wikipedia.org/wiki/Brahmagupta%27s_identity).

The prime $p$ is only 48 bits, so solving DLP with BSGS seems feasible. But I think having 8 DLP to solve is meant to stop this.

Since $p=4q+1$ for some prime $q$, and generator $G$ is generated by a random point multiply by $4$. It is reasonable to expect the order of this group is $p-1$, and `G.mult((P - 1) // 4)` is `(0, 1)` matches our expectation too.

Define a map $\varphi:G \rightarrow \mathbb{F}_p^\times$ as

$$
\varphi(x,y)=y+ix
$$

where $i^2 \equiv -1 \pmod{p}$.

> Because $\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=(-1)^{2q}=1$ so $i$ always exists.

We can show that $\varphi$ is a group homomorphism:

$$
\varphi(x,y) \cdot \varphi(z,w) = (y+ix) \cdot (w+iz) = yw-xz+i(xw+yz) = \varphi((x,y)+(z,w))
$$

So we can easily transfer the DLP problem from $(G,+)$ to $(\mathbb{F}_p,\times)$:

$$
\varphi(xP)=\varphi(P+P+\cdots+P)=\varphi(P)\cdot\varphi(P)\cdots\varphi(P)=\varphi(P)^x
$$

And sage can handle this DLP without a problem.

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from hashlib import sha256
import ast


class TickTock:
    def __init__(self, x, y, P):
        self.x = x
        self.y = y
        self.P = P
        assert self.is_on_curve()

    def __repr__(self):
        return "({}, {}) over {}".format(self.x, self.y, self.P)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y and self.P == other.P

    def is_on_curve(self):
        return (self.x * self.x + self.y * self.y) % self.P == 1

    def add(self, other):
        assert self.P == other.P
        x3 = (self.x * other.y + self.y * other.x) % self.P
        y3 = (self.y * other.y - self.x * other.x) % self.P
        return self.__class__(x3, y3, self.P)

    def mult(self, k):
        ret = self.__class__(0, 1, self.P)
        base = self.__class__(self.x, self.y, self.P)
        while k:
            if k & 1:
                ret = ret.add(base)
            base = base.add(base)
            k >>= 1
        return ret


def key_derivation(point):
    dig1 = sha256(b"x::" + str(point).encode()).digest()
    dig2 = sha256(b"y::" + str(point).encode()).digest()
    return sha256(dig1 + dig2 + b"::key_derivation").digest()


def dlog(P, G, A):
    F = GF(P)
    i = F(-1).sqrt()

    def phi(pt):
        x, y = pt
        return y + i * x

    return ZZ(phi(A).log(phi(G)))


with open("output.txt") as f:
    for _ in range(8):
        f.readline()
        f.readline()
        P = ast.literal_eval(f.readline().split("= ")[-1])
        G = ast.literal_eval(f.readline().split("= ")[-1])
        f.readline()
        A = ast.literal_eval(f.readline().split("= ")[-1])
        B = ast.literal_eval(f.readline().split("= ")[-1])
        f.readline()
        enc = bytes.fromhex(ast.literal_eval(f.readline().split("= ")[-1]))
        f.readline()
        f.readline()
        f.readline()
        f.readline()
        a = dlog(P, G, A)
        S = TickTock(*B, P).mult(a)
        key = key_derivation(S)
        iv = enc[:16]
        ct = enc[16:]
        cip = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
        print(unpad(cip.decrypt(ct), 16).decode(), end="")

Flag: `flag{c0m1ng_up_w1th_4_g00d_fl4g_1s_qu1t3_d1ff1cult_und3r_4ll_th1s_t1m3_pr3ssur3}`

> writeups for some other challenges I solved (in Chinese):　https://blog.maple3142.net/2021/11/14/k3rn3l-ctf-2021-writeups/