ふるつき

v('=')v かに

XXX - SECCON CTF 2021 Author's Writeup

SECCON CTF 2021に出題したXXXという問題のwriteupです。適当になって申し訳ない。作問したときの自分用のメモをそのまま転記しています

overview
solution

overview

共通の法 $p$ のもとで、複数の楕円曲線のインスタンスが作られている。 $k$ 個の楕円曲線はそれぞれ点 $P_0, P_1, P_2, \dots$ を曲線上にもち、それぞれの点の $x$ 座標は共通である（これがフラグ）。楕円曲線のパラメータのみから、この $x$ が復元できるだろうか

import os

flag = os.getenv("FLAG", "fake{fakeflag_blahblah}")
x = int.from_bytes(flag.encode(), "big")

p = random_prime(1 << int(x.bit_length() * 2.5))
Fp = GF(p)

params = []
while len(params) != 6:
    try:
        y = randint(2, x)
        a = randint(2, p-1)
        b = (y^2 - (x^3 + a*x)) % p

        EC = EllipticCurve(Fp, [a, b])
        EC(x, y)

        params.append([a, b])
    except ValueError:
        pass

print(p)
print(params)

solution

まず、楕円曲線上の点 $P_i$ が満たす式を書くと $y_i^2 \equiv x^3 + a_ix + b_i \mod p$ である。 $P_i$ と $P_{i+1}$ に関する式を減算すると $x^3$ の項を消すことができる。

$y_{i+1}^2 - y_i^2 \equiv (a_{i+1} - a_i)x + (b_{i+1} - b_{i}) \mod p$

ここで式をぐっとにらみそれぞれの項を置き直すと $y'_i \equiv a'_i x + b'_i \mod p$ となり、かつ $x$ が小さいのでこれはHidden Number Problemと捉えられる。

import ast

with open("output.txt") as f:
    p = ast.literal_eval(f.readline().strip())
    params = ast.literal_eval(f.readline().strip())

n = len(params) - 1
ts = [(params[i][0] - params[i+1][0]) % p for i in range(n)]
bs = [(params[i][1] - params[i+1][1]) % p for i in range(n)]

M = matrix(ZZ, n+2, n+2)
M.set_block(  0, 0, matrix.identity(n) * p)
M.set_block(  n, 0, matrix(ZZ, 1, n, ts))
M.set_block(n+1, 0, matrix(ZZ, 1, n, bs))
M[  n,   n] = 1
M[n+1, n+1] = p

L = M.LLL()

for row in L:
    try:
        x = int(abs(row[-2])).to_bytes(100, "big")
        print(x.strip(b"\0").decode())
        break
    except:
        pass