SECCON 2021 | XXX - crypto-writeup-public

#seccon2021

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)

$(x, y_i)$ を満たすEllipticCurveのパラメータの組がいくつか与えられている。式同士の引き算をすると

$(y_i^2 - y_j^2) \equiv (a_i - a_j)x + (b_i - b_j) \mod p$

が成り立つので、あとは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