dice-vs-kymn-upsolve.sage

from functools import cache

def division_polynomial(a, b, x, n):
    F = 4*(x**3 + a*x + b)

    @cache
    def f(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            return 1
        elif n == 3:
            return 3*x**4 + 6*a*x**2 + 12*b*x - a**2
        elif n == 4:
            return 2*(x**6 + 5*a*x**4 + 20*b*x**3 - 5*a**2*x**2 - 4*a*b*x - 8*b**2 - a**3)
        elif n % 2 == 0:
            m = n//2
            return (f(m + 2) * f(m - 1)**2 - f(m-2)*f(m+1)**2) * f(m)
        elif n % 4 == 1:
            m = (n - 1) // 2
            return F**2*f(m+2)*f(m)**3 - f(m-1)*f(m+1)**3
        elif n % 4 == 3:
            m = (n - 1) // 2
            return f(m+2)*f(m)**3 - F**2*f(m-1)*f(m+1)**3
        else:
            assert False, "unreachable"
    return f(n)

def check_order(aa, bb):
    x = randrange(1, 1 << 64)
    A = aa*x**2
    B = bb*x**3
    for _ in range(10):
        p = random_prime(1 << 256)
        if legendre_symbol(x^3 + A*x + B, p) == 1:
            break
    else:
        return False

    F = GF(p)
    E = EllipticCurve(F, [F(A), F(B)])
    G = E.lift_x(F(x))

    for k in range(7):
        if k == 1 or k == 7:
            if k*G != G:
                return False
        else:
            if k*G == G:
                return False
    return True


def search_param():
    PR.<a, b, x> = PolynomialRing(ZZ)
    f = division_polynomial(a, b, x, 6)


    found = False
    for aa in range(-100, 100):
        for bb in range(-100, 100):
            if f.subs({a: aa*x**2, b: bb*x**3}) == 0:
                print((aa, bb), end="-->")
                if check_order(aa, bb):
                    found = True

                    # re-check
                    for _ in range(10):
                        if not check_order(aa, bb):
                            found = False

                    if found:
                        print("found!")
                        break
                else:
                    print("negative")
        if found:
            break
    else:
        raise ValueError("not found")

    return aa, bb


def add(a, b, P, Q):
    if P == (0, 0):
        return Q

    if Q == (0, 0):
        return P

    a1, b1 = P
    a2, b2 = Q
    if a1 != a2:
        r = (b1 - b2) / (a1 - a2)

        a3 = r**2 - a1 - a2
        b3 = r * (a1 - a3) - b1
        return a3, b3

    else:
        # 2 bai
        r = (3*a1**2 + a) / (2*b1)

        a3 = r**2 - a1 - a2
        b3 = r * (a1 - a3) - b1
        return a3, b3


def scalar(a, b, P, k):
    Q = (0, 0)
    while k > 0:
        if k % 2 == 1:
            Q = add(a, b, Q, P)
        P = add(a, b, P, P)
        k = k >> 1
    return Q


from ptrlib import Socket
import ast

aa, bb = search_param()

# sock = Socket("localhost", 9999)
sock = Socket("nc dice-vs-kymn.2023.ricercactf.com 5963")

for turn in range(77):
    print(f"\n==== TURN: {turn} ====")
    x = int(sock.recvlineafter("x:"))

    A = aa*x**2
    B = bb*x**3
    sock.sendlineafter("a: ", str(A))
    sock.sendlineafter("b: ", str(B))

    Gy, Qy = ast.literal_eval(sock.recvlineafter("commitment: ").decode())
    print(Gy, Qy)

    G = (x, Gy)
    if Qy == 1:
        k = 0
    elif Gy == Qy:
        k = 1
    elif Qy == 0:
        k = 3
    else:
        for k in range(6):
            Q = scalar(A, B, G, k)
            if type(Q[1]) is int:
                g = int(gcd(G[1]**2 - (G[0]**3 + A*G[0] + B), Q[1] - Qy))
            else:
                g = int(gcd(G[1]**2 - (G[0]**3 + A*G[0] + B), Q[1].numerator() - Qy*Q[1].denominator()))
            if g > 2**200:
                break
        else:
            raise ValueError("so sonna...")

    dice = 7 - (k + 1)
    print(f"{k=}, {dice=}")
    sock.sendlineafter("dice: ", str(dice))
    print(sock.recvline())

sock.interactive()