SECCON CTF Finals 2023 DLP 4.0

solve.sage

from socket import create_connection


class Tube:
    def __init__(s, host, port, debug=False):
        s.host = host
        s.port = port
        s.sock = create_connection((host, port))
        s.debug = debug

    def recv(s, size=1024) -> bytes:
        buf = s.sock.recv(size)
        if s.debug:
            print(f"[Tube#recv] {buf=}")
        return buf

    def recv_until(s, expected: bytes) -> bytes:
        buf = b""
        while True:
            buf += s.sock.recv(1)
            if expected in buf:
                break
        if s.debug:
            print(f"[Tube#recv_until] {buf=}")
        return buf

    def send(s, buf: bytes):
        if s.debug:
            print(f"[Tube#send] {buf=}")
        s.sock.send(buf)

    def send_line(s, buf: bytes):
        s.send(buf + b"\n")

    def close(s):
        s.sock.close()
        if s.debug:
            print("[Tube#close] closed")


def read_quarternion(tube) -> (int, int, int, int):
    a = int(tube.recv_until(b" ").strip())
    tube.recv_until(b"+ ")
    b = int(tube.recv_until(b"*i").rstrip(b"*i"))
    tube.recv_until(b"+ ")
    c = int(tube.recv_until(b"*j").rstrip(b"*j"))
    tube.recv_until(b"+ ")
    d = int(tube.recv_until(b"*k").rstrip(b"*k"))
    return (a, b, c, d)


def get_eigenvalue(F, a, b, c, d):
    A = 1
    B = -2 * a
    C = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2

    D = sqrt(F(B ^ 2 - 4 * A * C))
    L1 = (-B + D) / (2 * A)
    L2 = (-B - D) / (2 * A)
    return (L1, L2)


def challenge(tube):
    tube.recv_until(b"favorite 333-bit p:")
    p = 15614383950057174190349598797195341142783317747682448840361363700794291170123950129507898918000642787
    tube.send_line(str(p).encode())
    tube.recv_until(b"g = ")
    g_raw = read_quarternion(tube)
    tube.recv_until(b"h = ")
    h_raw = read_quarternion(tube)

    x = var("x")
    F = GF(p ^ 2, "i", modulus=x ^ 2 + 1)
    ii = F.gen()

    ga, gb, gc, gd = g_raw
    ha, hb, hc, hd = h_raw
    G = Matrix(2, 2, [ga + gb * ii, gc + gd * ii, -gc + gd * ii, ga - gb * ii])
    H = Matrix(2, 2, [ha + hb * ii, hc + hd * ii, -hc + hd * ii, ha - hb * ii])
    E = Matrix(2, 2, [1, 0, 0, 1])
    order = p ^ 2 - 1
    print(G)
    print(H)
    assert G ^ order == E
    assert H ^ order == E

    # print(discrete_log(H, G, order))
    # print(factor(order))

    L1, L2 = get_eigenvalue(F, ga, gb, gc, gd)
    M1, M2 = get_eigenvalue(F, ha, hb, hc, hd)
    print(M1, L1)
    print(M2, L2)
    x = None
    y = None
    if "i" not in str(M1):
        y = M1
    elif "i" not in str(M2):
        y = M2
    else:
        return False
    if "i" not in str(L1):
        x = L1
    elif "i" not in str(L2):
        x = L2
    else:
        return False

    K = GF(p)
    x = K(x)
    y = K(y)
    exponent = y.log(x)
    print(exponent)
    tube.send_line(f"{exponent}".encode())
    print(tube.recv(1024))
    print(tube.recv(1024))
    print(tube.recv(1024))
    print(tube.recv(1024))
    return True


def main():
    res = False
    while not res:
        tube = Tube("dlp-4-0.int.seccon.games", int(8888), False)
        res = challenge(tube)
        tube.close()


if __name__ == "__main__":
    main()

"""
Sat Dec 23 15:15:53 JST 2023 ~/Downloads/seccon/dlp40
> sage solve.sage
[ 6631464687709964401638593584282317698086002418701370403451375298554143352342218518442929071743687214*i + 3765457014279809956954260428460280043908869382556850885683433873161873968349753755711085812309759210  1756077780020567359443754915888514185407371957577724923461216434521905705877637149988978040124045765*i + 1881684727616963945842060796788171278039491185096740965627887778594179476105202541456478557304673086]
[1756077780020567359443754915888514185407371957577724923461216434521905705877637149988978040124045765*i + 13732699222440210244507538000407169864743826562585707874733475922200111694018747588051420360695969701  8982919262347209788711005212913023444697315328981078436909988402240147817781731611064969846256955573*i + 3765457014279809956954260428460280043908869382556850885683433873161873968349753755711085812309759210]
[ 1881371858615367495979936456052833089872096441628283057598121060625192177926987544203162878521148159*i + 2786543516685313266376357758565837454350585473891921861545979837196340717363293199705315241832288765 11256877498661346110604063673865090970528886708319285248471932347487536611717097833493040746484556862*i + 7894130681478798794027079182653982044748502187803860895609544400580668595047811770360215666587674870]
[11256877498661346110604063673865090970528886708319285248471932347487536611717097833493040746484556862*i + 7720253268578375396322519614541359098034815559878587944751819300213622575076138359147683251412967917 13733012091441806694369662341142508052911221306054165782763242640169098992196962585304736039479494628*i + 2786543516685313266376357758565837454350585473891921861545979837196340717363293199705315241832288765]
2418647487938229570796016168675436284876845327648781656081662061111385418663188068833989750891784650 5415892221835400173647908582958920513903911956526191842594953242062956188629818670097956727183023943
3154439545432396961956699348456238623824325620135062067010297613281296016063398330576640732772792880 2115021806724219740260612273961639573913826808587509928771914504260791748069688841324214897436494477
8387334036474732265753636830045470359800171486506787888726375311651688036101558463050370202509442336
b'\nGuess x: '
b"SECCON{Yay! You've got a 333-bit useful prime for CTF! <333}\n"
b''
b''
"""