ASIS CTF Finals 2022 | monward

#ASIS_CTF_Finals_2022

#!/usr/bin/env sage

from Crypto.Util.number import *
from secret import C, flag

def monon(C, P):
    a, d, p = C
    x, y = P
    return (a*x**2 + y**2 - d*x**2*y**2) % p == 1

def monadd(C, P, Q):
    a, d, p = C
    assert monon(C, P) and monon(C, Q)
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 * y2 + y1 * x2) * inverse(1 + d * x1 * x2 * y1 * y2, p) % p
    y3 = (y1 * y2 - a * x1 * x2) * inverse(1 - d * x1 * x2 * y1 * y2, p) % p
    return (x3, y3)

def monprod(C, P, l):
    a, d, p = C
    x, y = P
    N, B = (0, 1), bin(l)[2:]
    for i in range(len(B)):
        if B[i] == '1':
            Q = P
            for _ in range(len(B) - i - 1):
                x, y = monadd(C, Q, Q)
                Q = (x, y)
            N = monadd(C, N, Q)
    return N

def encrypt(m, C, P):
    a, d, p = C
    assert m < p and monon(C, P)
    return monprod(C, P, m)

P = (2021000018575600424643989294466413996315226194251212294606, 1252223168782323840703798006644565470165108973306594946199)
Q = (2022000008169923562059731170137238192288468444410384190235, 1132012353436889700891301544422979366627128596617741786134)
R = (2023000000389145225443427604298467227780725746649575053047, 4350519698064997829892841104596372491728241673444201615238)

assert monon(C, P) == monon(C, Q) == monon(C, R) == is_prime(C[2]) == True
flag = flag.lstrip(b'ASIS{').rstrip(b'}')
m = bytes_to_long(flag)
enc = encrypt(m, C, P)
print(f'enc = {enc}')

twisted edwards curve上のECDLP。まずはの4変数から曲線のパラメータを求める。楕円曲線/6点からパラメータを復元するみたいな感じ

その後はMontgomery Curveを経由してWeirstrass 標準形にもちこんで位数を確認するとB-smoothになっているのでPohlig-Hellman AttackをSageにやってもらえば良い

P = (2021000018575600424643989294466413996315226194251212294606, 1252223168782323840703798006644565470165108973306594946199)
Q = (2022000008169923562059731170137238192288468444410384190235, 1132012353436889700891301544422979366627128596617741786134)
R = (2023000000389145225443427604298467227780725746649575053047, 4350519698064997829892841104596372491728241673444201615238)
enc = (3419907700515348009508526838135474618109130353320263810121, 5140401839412791595208783401208636786133882515387627726929)


## find paramter of curve

# find p
(x1v, y1v) = P
(x2v, y2v) = Q
(x3v, y3v) = R
(x4v, y4v) = enc

PR.<x1, y1, x2, y2, x3, y3, x4, y4, a, d> = PolynomialRing(QQ)
f1 = a*x1 ** 2 + y1**2 - d*x1**2*y1**2 - 1
f2 = a*x2 ** 2 + y2**2 - d*x2**2*y2**2 - 1
f3 = a*x3 ** 2 + y3**2 - d*x3**2*y3**2 - 1
f4 = a*x4 ** 2 + y4**2 - d*x4**2*y4**2 - 1
fs = [f1, f2, f3, f4]

gs = []
for i in range(len(fs)):
    for j in range(i+1, len(fs)):
        gs.append(fs[i].resultant(fs[j], a))

hs = []
for i in range(len(fs)):
    for j in range(i+1, len(fs)):
        hs.append(gs[i].resultant(gs[j], d))


vs = []
for h in hs:
    v = h.subs({x1: x1v, y1: y1v, x2: x2v, y2: y2v, x3: x3v, y3: y3v, x4: x4v, y4: y4v})
    vs.append(int(v))

p = factor(gcd(vs))[-1][0]

# find a, d
PR.<x1, y1, x2, y2, a, d> = PolynomialRing(QQ)
f1 = a*x1 ** 2 + y1**2 - d*x1**2*y1**2 - 1
f2 = a*x2 ** 2 + y2**2 - d*x2**2*y2**2 - 1
fs = [f1, f2, f3, f4]
g = f1.resultant(f2, a)
PRQ.<d> = PolynomialRing(GF(p))
gq = g.subs({x1: x1v, y1: y1v, x2: x2v, y2: y2v}).univariate_polynomial().change_ring(PRQ)
d = int(gq.roots()[0][0])

PR.<a> = PolynomialRing(GF(p))
f1 = a*x1v ** 2 + y1v**2 - d*x1v**2*y1v**2 - 1
a = f1.roots()[0][0]


# Convert it to Weierstrass form through Montgomery Curve
A=2*(a+d) / GF(p)(a-d)
B=4 / GF(p)(a-d)

E = EllipticCurve(GF(p), [(3 - A**2)/(3*B**2), (2*A**3 - 9*A)/(27*B**3)])
print(E.order())


def convert_point(u, v):
    x = GF(p)(1 + v)/(1 - v)
    y = x / u

    return E(x/B + A/(3*B), y/B)

P_ = convert_point(P[0], P[1])
enc_ = convert_point(enc[0], enc[1])

m = P_.discrete_log(enc_)
print(b"ASIS{" + bytes.fromhex(hex(m)[2:]) + b"}")