# 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. ```python 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/