[WriteUp] / [CryptoHack - Elliptic Curves, Point Addition]

from sympy import mod_inverse

# Define parameters
p = 9739
a = 497
b = 1768

# Elliptic curve: y^2 = x^3 + a*x + b mod p
def point_add(P, Q):
    if P == Q:
        return point_double(P)

    if P is None:
        return Q
    if Q is None:
        return P

    x1, y1 = P
    x2, y2 = Q

    if x1 == x2 and (y1 + y2) % p == 0:
        return None

    m = ((y2 - y1) * mod_inverse(x2 - x1, p)) % p
    x3 = (m**2 - x1 - x2) % p
    y3 = (m * (x1 - x3) - y1) % p

    return (x3, y3)

def point_double(P):
    if P is None:
        return None

    x, y = P
    m = ((3 * x**2 + a) * mod_inverse(2 * y, p)) % p
    x3 = (m**2 - 2 * x) % p
    y3 = (m * (x - x3) - y) % p

    return (x3, y3)

# Given points
P = (493, 5564)
Q = (1539, 4742)
R = (4403, 5202)

# Compute S = P + P + Q + R
P2 = point_double(P)
PQ = point_add(P2, Q)
S = point_add(PQ, R)

이전문제까지는 익스 안 짜도 됐는데.. 여기서부턴 계산 복잡해져서 익스를 무조건 짜야한다
-> crypto{4215,2162}