Crytpo CTF 2021 | Elegant Curve

#cryptoctf2021

#!/usr/bin/env python3

from Crypto.Util.number import *
import sys
from flag import flag

def tonelli_shanks(n, p):
    if pow(n, int((p-1)//2), p) == 1:
        s = 1
        q = int((p-1)//2)
        while True:
            if q % 2 == 0:
                q = q // 2
                s += 1
            else:
                break
        if s == 1:
            r1 = pow(n, int((p+1)//4), p)
            r2 = p - r1
            return r1, r2
        else:
            z = 2
            while True:
                if pow(z, int((p-1)//2), p) == p - 1:
                    c = pow(z, q, p)
                    break
                else:
                    z += 1
            r = pow(n, int((q+1)//2), p)
            t = pow(n, q, p)
            m = s
            while True:
                if t == 1:
                    r1 = r
                    r2 = p - r1
                    return r1, r2
                else:
                    i = 1
                    while True:
                        if pow(t, 2**i, p) == 1:
                            break
                        else:
                            i += 1
                    b = pow(c, 2**(m-i-1), p)
                    r = r * b % p
                    t = t * b ** 2 % p
                    c = b ** 2 % p
                    m = i
    else:
        return False

def add(A, B, p):
    if A == 0:
        return B
    if B == 0:
        return A
    l = ((B[1] - A[1]) * inverse(B[0] - A[0], p)) % p
    x = (l*l - A[0] - B[0]) % p
    y = (l*(A[0] - x) - A[1]) % p
    return (int(x), int(y))

def double(G, a, p):
    if G == 0:
        return G
    l = ((3*G[0]*G[0] + a) * inverse(2*G[1], p)) % p
    x = (l*l - 2*G[0]) % p
    y = (l*(G[0] - x) - G[1]) % p
    return (int(x), int(y))

def multiply(point, exponent, a, p):
    r0 = 0
    r1 = point
    for i in bin(exponent)[2:]:
        if i == '0':
            r1 = add(r0, r1, p)
            r0 = double(r0, a, p)
        else:
            r0 = add(r0, r1, p)
            r1 = double(r1, a, p)
    return r0

def random_point(a, b, p):
    while True:
        x = getRandomRange(1, p-1)
        try:
            y, _ = tonelli_shanks((x**3 + a*x + b) % p, p)
            return (x, y)
        except:
            continue

def die(*args):
    pr(*args)
    quit()

def pr(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def sc():
    return sys.stdin.readline().strip()

def main():
    border = "+"
    pr(border*72)
    pr(border, " hi talented cryptographers, the mission is decrypt a secret message", border)
    pr(border, " with given parameters for two elliptic curve, so be genius and send", border)
    pr(border, " suitable parameters, now try to get the flag!                      ", border)
    pr(border*72)

    nbit = 160

    while True:
        pr("| Options: \n|\t[S]end ECC parameters and solve the task \n|\t[Q]uit")
        ans = sc().lower()
        if ans == 's':
            pr("| Send the parameters of first ECC y^2 = x^3 + ax + b like: a, b, p ")
            params = sc()
            try:
                a, b, p = params.split(',')
                a, b, p = int(a), int(b), int(p)
            except:
                die("| your parameters are not valid!!")
            if isPrime(p) and 0 < a < p and 0 < b < p and p.bit_length() == nbit:
                pr("| Send the parameters of second ECC y^2 = x^3 + cx + d like: c, d, q ")
                pr("| such that 0 < q - p <= 2022")
                params = sc()
                try:
                    c, d, q = params.split(',')
                    c, d, q = int(c), int(d), int(q)
                except:
                    die("| your parameters are not valid!!")
                if isPrime(q) and 0 < c < q and 0 < d < q and 0 < q - p <= 2022 and q.bit_length() == nbit:
                    G, H = random_point(a, b, p), random_point(c, d, q)
                    r, s = [getRandomRange(1, p-1) for _ in range(2)]
                    pr(f"| G is on first  ECC and G =", {G})
                    pr(f"| H is on second ECC and H =", {H})
                    U = multiply(G, r, a, p)
                    V = multiply(H, s, c, q)
                    pr(f"| r * G =", {U})
                    pr(f"| s * H =", {V})
                    pr("| Send r, s to get the flag: ")
                    rs = sc()
                    try:
                        u, v = rs.split(',')
                        u, v = int(u), int(v)
                    except:
                        die("| invalid input, bye!")
                    if u == r and v == s:
                        die("| You got the flag:", flag)
                    else:
                        die("| the answer is not correct, bye!")
                else:
                    die("| invalid parameters, bye!")
            else:
                die("| invalid parameters, bye!")
        elif ans == 'q':
            die("Quitting ...")
        else:
            die("Bye ...")

if __name__ == '__main__':
    main()

EllipticCurve どうせ anomalous curveとかでしょと思っている