HITCON CTF 2022 | Chimera - crypto-writeup-public

#HITCON_CTF_2022

import os
from Crypto.Util.number import bytes_to_long, getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from secret import flag


p = getPrime(384)
q = getPrime(384)
n = p * q
Gx = bytes_to_long(os.urandom(32))
Gy = bytes_to_long(os.urandom(32))
a = randint(1, n**2)
b = (Gy**2 - (Gx**3 + a * Gx)) % (n**2)

E = EllipticCurve(Zmod(n), [a, b])
gift = int(E.change_ring(GF(p)).order() * E.change_ring(GF(q)).order())
assert gift * E(Gx, Gy) == E(0, 1, 0)
print(f"{gift = }")

E = EllipticCurve(Zmod(n**2), [a, b])
lion_head = E(Gx, Gy)
goat_body = [randint(1, n) * lion_head for _ in range(16)]
snake_tail = [os.urandom(16) for _ in range(64)]
chimera = [sum([x * y for x, y in zip(tail, goat_body)]) for tail in snake_tail]
print("chimera =", [P.xy() for P in chimera])

key = sha256(str(sum(goat_body).xy()[0]).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, b"\0" * 16)
flagct = cipher.encrypt(pad(flag, 16))
print(f"{flagct = }")

まず、EllipticCurve $E$ と点 $G = head = E(G_x, G_y)$ があり、 $P_i = r_iG$ とした $P_i$ を16個生成している

更にそれに対して、 $Q_j = \sum_i u_{i,j} P_i = \sum_i u_{i, j}r_i G$ where $u_{i,j} \in \lbrack 0, 256)$ として $Q_i$ が64個もらえる

このとき $P_0$ を求めよ、というのが問題。

まずは適当に楕円曲線のパラメータ $a, b, n$ を求める
続いて、 $G$ を求める。
- $G_y^2 \equiv G_x^3 + aG_x + b \mod n^2$ が成り立ち、 $n^2$ に比べて $G_x, G_y$ が小さいことから multivariate coppersmith や LLL で求められる
$n$ を素因数分解する。
- $gift$ として楕円曲線の位数が与えられているので $E$ 上の適当な点で、 $lP \in E_p$ だが $lP \not\in E_q$ であるような点を探して（＝ $E$ 上で $l$ 倍できない点を探せば良い）、GCDを取る
- https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization
$Q_j = k_jG$ の $k_j$ を ECDLP を解いて求める
- $E_p, E_q$ に分けて考えると、 zer0pts CTF 2021 | Pure Division と同様に解が $p, q$ 以下なら $E(\mathbb{Z}/p^k\mathbb{Z})$ 上のdiscrete logは簡単にとけて、あとでCRTすればよい
$k_j = r_i \sum u_{i,j}$ を解く
- これは Hidden Subset sum Problem なので Orthogonal Lattice Attack をする
$P_0 = r_0G$ なのでヨシ