jailctf2025-pycryptojail-solver.sage

import os

os.environ['PWNLIB_NOTERM'] = '1'
os.environ['TERM'] = 'linux'

from pwn import *

from Crypto.Util.number import long_to_bytes, bytes_to_long

def message_not_define(name):
    return b'Traceback (most recent call last):\n  File "<string>", line 3, in <module>\nNameError: name \'' + name + b'\' is not defined\n'

def message_did_you_mean(name):
    m = b'Traceback (most recent call last):\n  File "<string>", line 3, in <module>\nNameError: name \'' + name + b'\' is not defined. Did you mean: \'flag_you_will_never_guess_this_6b9a295e978fe39a\'?\n'
    return m[:192]

def pdivmod(u, v):
    """
    polynomial version of divmod
    """
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    """
    Calculate Half-GCD of (u, v)
    f and g are univariate polynomial
    <http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf>
    """
    x = u.parent().gen()

    if u.degree() < v.degree():
        u, v = v, u

    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])

    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)

    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)

    g0 = e // x^(m//2)
    g1 = f // x^(m//2)

    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    """
    fast implementation of polynomial GCD
    using hgcd
    """
    if u.degree() < v.degree():
        u, v = v, u

    if v == 0:
        return u

    if u % v == 0:
        return v

    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u

    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1

    return pgcd(b1, r)

def franklinreiter(c_1, c_2, e_1, e_2, n, a, b):
    F = Zmod(n)
    P.<X> = PolynomialRing(F)
    g_1 = X^e_1 - c_1
    g_2 = (a*X + b)^e_2 - c_2
    h = pgcd(g_1, g_2)
    s0 = F(-h.monic()[0])
    return s0

if __name__ == '__main__':
    r = remote("challs1.pyjail.club", 17549, level='debug')

    m_import = bytes_to_long(b'  File "<string>", line 3\n    print(import)\n          ^^^^^^\nSyntaxError: invalid syntax\n')

    r.recvuntil(b'>>> ')

    r.sendline(b"import")
    lines = r.recvuntil(b'>>> ').split(b'\n')
    c_import = int(lines[-2], 16)

    e = 0x10001

    ma = bytes_to_long(b'Traceback (most recent call last):\n  File "<string>", line 3, in <module>\nNameError: name \'a\' is not defined\n')
    mb = bytes_to_long(b'Traceback (most recent call last):\n  File "<string>", line 3, in <module>\nNameError: name \'b\' is not defined\n')

    r.sendline(b"a")
    lines = r.recvuntil(b'>>> ').split(b'\n')
    ca = int(lines[-2], 16)
    r.sendline(b"b")
    lines = r.recvuntil(b'>>> ').split(b'\n')
    cb = int(lines[-2], 16)

    n = gcd(ma^e - ca, mb^e - cb)
    while int(n) % 2 == 0:
        n //= 2
    print(f"{n=}")

    S = '0123456789abcdef'

    prefix = "flag_you_will_never_guess_this_"
    secret = ""
    suffix = "zzzzzzzzzzzzzzz"

    for _ in range(32):
        if len(secret) == 16:
            break
        found_chars = ""

        for ch in S:
            query = (prefix + secret + ch + suffix).encode()
            print(f"{query=}")

            r.sendline(query)
            lines = r.recvuntil(b'>>> ').split(b'\n')
            c0 = int(lines[-2], 16)

            m0 = bytes_to_long(message_did_you_mean(query))

            c_dym = pow(m0, e, n)

            # did you mean
            if c0 == c_dym:
                found_chars += ch
                if len(found_chars) > 1:
                    suffix += "z"
                    break
            else:
                if len(found_chars) == 1:
                    break

        if len(found_chars) == 1:
            secret += found_chars

    flag_var = (prefix + secret).encode()
    print(f"{flag_var=}")


    r.sendline(flag_var)
    lines = r.recvuntil(b'>>> ').split(b'\n')
    c0 = int(lines[-2], 16)
    r.sendline(b"__name__+" + flag_var)
    lines = r.recvuntil(b'>>> ').split(b'\n')
    c1 = int(lines[-2], 16)

    for i in range(1, 200):
        content = b"*" * i

        m0 = b"jail{" + content + b"}\n"
        m1 = b"__main__" + m0
        m0 = bytes_to_long(m0)
        m1 = bytes_to_long(m1)

        res = franklinreiter(c0, c1, e, e, n, 1, m1 - m0)
        flag = long_to_bytes(int(res))
        print(i, flag)
        if flag.startswith(b"jail{"):
            print(flag)
            break

# jail{pyth0n_tr4c3b4ck_is_a_l3v3n5ht31n_d15t4nc3_0r4cle}