ACSC 2021 | swap on curve

#acsc2021

from params import p, a, b, flag, y

x = int.from_bytes(flag, "big")

assert 0 < x < p
assert 0 < y < p
assert x != y

EC = EllipticCurve(GF(p), [a, b])

assert EC(x,y)
assert EC(y,x)

print("p = {}".format(p))
print("a = {}".format(a))
print("b = {}".format(b))

EllipticCurve上でとが同時に成り立つので式変形すると解ける。groebner basisだと大きいmodのときは計算ができないので、resultantを使うと良い

# import ast
# 
# with open("./distfiles/output.txt") as f:
#     p = ast.literal_eval(f.readline().strip().split(" = ")[1])
#     a = ast.literal_eval(f.readline().strip().split(" = ")[1])
#     b = ast.literal_eval(f.readline().strip().split(" = ")[1])


p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096

F.<x, y> = ZZ[]

f = x^3 + a*x + b - y^2
g = y^3 + a*y + b - x^2

for root in f.resultant(g, y).univariate_polynomial().change_ring(GF(p)).roots():
    flag = int(root[0]).to_bytes(100, "big")
    if b"ACSC{" in flag:
        print(flag[:flag.find(b"}") + 1].strip(b"\0").decode())