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())