corCTF 2022 Writeup

Tue Aug 09 2022

    I participated corCTF 2022 by myself. The results were 14th/978.

    Here are my some write-ups for crypto challs.

    crypto

    rlfsr

    14 solves

    rlfsr.py
    from secrets import randbits
    from random import shuffle
    from hashlib import sha256
    from Crypto.Cipher import AES
    from Crypto.Util.Padding import pad
    
    class LFSR:
        def __init__(self, key, taps):
            self.key = key
            self.taps = taps
            self.state = list(map(int, list("{:0128b}".format(key))))
        
        def _clock(self):
            ob = self.state[0]
            self.state = self.state[1:] + [sum([self.state[t] for t in self.taps]) % 2]
            return ob
    
    key = randbits(128)
    l = LFSR(key, [1, 2, 7, 3, 12, 73])
    out = []
    
    for i in range(118):
        bits = [l._clock() for _ in range(128)]
        shuffle(bits)
        out += bits
    
    print(hex(sum([bit*2**i for i, bit in enumerate(out)])))
    
    flag = open("flag.txt", "rb").read()
    iv = randbits(128).to_bytes(16, 'big')
    aeskey = sha256(key.to_bytes(16, 'big')).digest()[:32]
    print((iv + AES.new(aeskey, AES.MODE_CBC, iv=iv).encrypt(pad(flag, 16))).hex())

    This LFSR is literally linear, but the output is shuffled by 128 each.

    Since the tap is weird (the tap doesn't has 0-th), there is a possibility that the period of this LFSR is quite short. I first tried to leak this period, but it's not the case.

    Then I noticed that the sum of 128 outputs can be calculated, though we didn't know how they were shuffled. Using this fact, we can get 118 bits of output. To leak initial state, we should get another 10 bits, but this can be found by brute force.

    solve.sage
    from hashlib import sha256
    from binascii import unhexlify
    
    from Crypto.Cipher import AES
    
    
    out_int = 0x824edb4620dca76a4abda968ff8eb44a93c5e55fd3e63f4abec458a6141190f7eb94b0da6712aa1a9d087984402fdd3f57bbbc6cca1156967b4c2bdee51885176dd74c91098f71e2aa339af6f7d9ae081b5f794c4c49bc3085d01c34fdee7e7458d38610c5a2f9879a378b985afe2be32c206b6e33b2bc52ff2f9b1919fe824c56badd1f7122be46f2a2308bf89565a55729d4b83f19707a9db9122680b213fb127f58d030a1337ce76e5c7d31a369f57a68ee92dfe81d239104bb307ff25ced4624feb4f5f917335444ef30338566ce1451ec3b2f41f16ac3295a7decb0131033767a1def651eada3b5b2e69dbd486475d6f4552bf3bc1d1462ccd19f20c3da0139cc165a79968bb33858984f0fba5aa7e39ff6ec4fc466f1ca235b0a989542fed4526ed74bc33ff38562d5e842c1431941d345fcdb2eb1d1cae060b05f2084ddc3bff342b6f4fd13c680a331394a42bf3a8fb3d0ab57dcefa90a5bee60c503fb2cd596889716cbe3d880588c8fc58d4bee0f94daccc176fe1b33ba7aca29876a5005e903abbe6c9d02ce7855db027707ea81e93187624738732a8daf756a3d5d3d62eb105e07b4b35aa64e9c0c99725c5e3ac0ef6ce120d54ad68a61cc6841bc76aef197b0b71e5ca42fab3f047b4a64811611d0cb58e707e04ec10b56ead1adfccece3c7068ff15592a281e71697a756b955dd6147e0494f7a846663964063b3a485ad0ff15290e05c46c51af7ffb87eae257c411e66f7214e88c933770c9d4389e36c9a073d9a3137c2a3dc2dfac8e8ef298a75508ef66debc701b81850ccb774f7cce63dc723cc1b13746277345fa0df4146d183ea444e80d8e3825e29e1db1d59903c038f8cbcf8ed6360ad4806c7cab9f440e3d1d38d1c3577f5c6d6ce1e6dbbbeb89a67a04f004854ced5a17a36c3565ca3d3fdd06c4495cf36c333c1babc47c2eb681bc0c539ac0f1b2eb89a86524ffc4f7f5805872d3b30cba8738ca4db6588e2b72db30502861bcdc519033afa13dd1073db094bcf44fee9bd3488ebb446c3278b8b3f7b350e936a7e9b493c4b1b18655571114f1ab4a9c71871487a70b0648c7622753db39d2d53fb8f4bd4ff278a47428cce871338f149305d921623d7de34348ada43a0bc2137ec9b41d7f465cf3fe57eb6f805df8f85f6c6f7eaff26ad1b20495e41292fb33ea97c0b9b69920371231f08044c491518403f553c593894509060414abe47afcf3ad7617b69a9b423daf39a6d865e4ef5c46e8eaafe752fd79b345b49e77bf75b011e079886949d39db8d7fc5719e37480253dea7c00dd4debdd19c08870a90c3ef2f55109dcead09fc67dfc8fca50c577ec67168da5cdd6053edfbfc0f598137ef9ca1edf36009c6a9f879250ff6a323ee63e81306d834162b63f6fb223bb054f2e8c11611274919ee7d3a3721591ac6d7482142e0d54a4bd8fd07b0ac4a16c6b54792e27143489c2588a6b5cac79b24acd78db75cbe059e4c0ce4cb1d45dafba3c09fbf0aac2b8728d74f558ef538ca4ac9799fa558cc2fbb8beeccf1bf6997f3558a33c267742174b6b1e1431498d3e4884c73e126e904d09625247e1feddfcbe0c9a99258d4e282dc5606f1095f81f96924054e5020abd9dfac52973e3cb7005fb07e3fc67db805797eca46ee9cfcb37129879ec9bcda4a3932eac35988a75e635d8fcd1d2195451fb98edc3d5d0a086405e3484ff8dba16c738ff844583ab65fbc9ade0ccc4d0c310b46fe6fb39815ef3f1bd70f3997ee5290a8d0864133ecb668c13211f9fad682811cb123b76c9fb4cf93f32fbbe7a1300421a8d2710de1027c24a139c6978058d3667a9df2caeaad88da5aaa435331013c8aae10a64fe93d7c138a0f84016c6628fa9e7f62648be24474f2f73b5ee36238cbe0132d6d5a0db57650a8d194bcde065d3cdcf374f21df843675495c2baba1bd22a7f644882982a71804fa7aab4c55300471a4f4c10bd687682b90cea92214110098216348ce4115caa5ef1daa79f36511e4ad594394773eeded215b7a855a03985af9121bc83a0615d07355798f5f63e8f8e615ed5c99868136506e7facf153474a063cb5803fa6d83a713370e92ae2cc68d1304272ff1b407afec261138e8a2107767736cbb74aa28a16ef1b68345eed1e794bd4f0ecbac05dfb0b1307e27be71798f969c6177b981da53e2a172cb553a6f897cd1fdb67b35d6cf3410af88aa3a5040c42a06f3d2414605b9dbc882fefa7f2d76e51592f6cce654e00f9837801fee64a21218bd71c17a9c1cbcfe7e522d8da37886f789457047fe8bd7c8f41365762d8ef2a90e1de426faf18def1c4a2013f46cee4d955afbf9dddd4369ca5544a0c0cdba235359a9aba4a61fae81625c7a4ab7c287a905826af1d184c5eef22ee0940d75937f9ac740dbe7360a6c8c21d140b1dba5d7c5a4bc9449179398d67b83555a40ff1b4cad66dc522d75d6c9c6ae3071fd7c404011c054aa67c6122344f7c73cd9de35c37f2ccd5caa3717f1d5f571192c108dbf15557bb0bef72f830c9b6bd9295d5f1d7bd871d1889b1f849ecf5a8efc13233e38efded7a16772878a685e28944c42529abf0577d8027188658313fc80f65f626074c0d4214a826fad70bd8f39dae2ce8547e7bc29a20f064833267b524aa
    tmp = out_int
    out = []
    for _ in range(128 * 118):
        out.append(tmp % 2)
        tmp //= 2
    
    M = matrix(GF(2), 128, 128)
    for i in range(127):
        M[i, i+1] = 1
    tap = [1, 2, 7, 3, 12, 73]
    for t in tap:
        M[127, t] = 1
    
    t = vector(GF(2), [1] + [0] * 127)
    # t_sum = t + t * M + t * M**2 + ... + t * M**127
    # t_sum * initial_state equals to the sum of first 128 outputs.
    t_sum = vector(GF(2), 128)
    for i in range(128):
        t_sum += t * M ** i
    
    # S[i] equals to the sum(out[128*i:128*(i+1)])
    S = matrix(GF(2), 128, 128)
    for i in range(118):
        S[i] = t_sum * M**(128*i)
    target = vector(GF(2), 128)
    for i in range(0, len(out), 128):
        target[i//128] = sum(out[i: i+128])
    
    
    enc = unhexlify("38bd5d4c3f5fa5ef8c34cae70a03111d446361d73c4f315f309f6a7ce602b893fdb6d3ae15e2a12668e97c020bf13e54c6e00125e92f9859d8c2ac71a1534a9a234426f4ba3927c797b0924f04aa7f0f79578afc4c3e6054fb3601f88d511934a5424efa4ba2e6e776d91e398afc3c7f5335fefe78c0b58e98ae838f4ae73379")
    iv = enc[:16]
    enc_flag = enc[16:]
    
    K = S.right_kernel()
    base = S.solve_right(target)
    basis = K.basis()
    for n in range(2**10):
        v = vector(GF(2), 128)
        for i in range(10):
            if n % 2 == 1:
                v += basis[i]
            n //= 2
        ans = base + v
        key = int("".join(map(str, ans.change_ring(ZZ))), 2)
        aeskey = sha256(key.to_bytes(16, 'big')).digest()[:32]
        dec = AES.new(aeskey, AES.MODE_CBC, iv=iv).decrypt(enc_flag)
        if b"corctf" in dec:
            print(dec)

    corctf{m4yb3_w3_sh0uld_ju5t_cut_hum4n5_0ut_0f_th1s_c0mpl3t3ly_1f_th3y_d3c1d3_t0_f4k3_shuffl3_0r_s0m3th1ng}

    corrupted-curves, corrupted-curves+

    20 solves, 15 solves

    corruptedcurves.py
    #!/usr/local/bin/python
    from secrets import randbits
    from Crypto.Util.number import getPrime
    
    def square_root(a, p):
        if legendre_symbol(a, p) != 1:
            return 0
        elif a == 0:
            return 0
        elif p == 2:
            return 0
        elif p % 4 == 3:
            return pow(a, (p + 1) // 4, p)
        s = p - 1
        e = 0
        while s % 2 == 0:
            s //= 2
            e += 1
        n = 2
        while legendre_symbol(n, p) != -1:
            n += 1
        x = pow(a, (s + 1) // 2, p)
        b = pow(a, s, p)
        g = pow(n, s, p)
        r = e
        while True:
            t = b
            m = 0
            for m in range(r):
                if t == 1:
                    break
                t = pow(t, 2, p)
            if m == 0:
                return x
            gs = pow(g, 2 ** (r - m - 1), p)
            g = (gs * gs) % p
            x = (x * gs) % p
            b = (b * g) % p
            r = m
    
    def legendre_symbol(a, p):
        ls = pow(a, (p - 1) // 2, p)
        return -1 if ls == p - 1 else ls
    
    class EllipticCurve:
        
        def __init__(self, p, a, b):
            self.a = a
            self.b = b
            self.p = p
            if not self.check_curve():
                raise Exception("Not an elliptic curve!")
            
        def check_curve(self):
            discrim = -16 * (4*pow(self.a, 3) + 27*pow(self.b, 2))
            if discrim % self.p:
                return 1
            return 0
        
        def lift_x(self, px):
            y2 = (pow(px, 3) + self.a*px + self.b) % self.p
            py = square_root(y2, self.p)
            if py == 0:
                raise Exception("No point on elliptic curve.")
            return py
    
    with open("flag.txt", "rb") as f:
        flag = f.read()
        flag = int.from_bytes(flag, 'big')
    
    print("Generating parameters...")
    while True:
        p = getPrime(512)
        a, b = randbits(384), randbits(384)
        try:
            E = EllipticCurve(p, a, b)
            fy = E.lift_x(flag)
            print(f"p = {p}")
            print(f"flag y = {fy}")
            break
        except:
            continue
    print(a, b)
    checked = set()
    count = 0
    while count < 64:
        x = int(input("x = ")) % p
        if int(x) in checked or x < 2**384 or abs(x - p) < 2**384:
            print(">:(")
            continue
        e = randbits(64)
        print(f"e = {e}")
        try:
            E = EllipticCurve(p, a^e, b^e)
            py = E.lift_x(x)
            checked.add(int(x))
            print(f"y = {py}")
            count += 1
        except:
            print(":(")
    print("bye!")

    We can get random ee and one point on the elliptic curve y2=x3+(ae)x+(be)y^2 = x^3 + (a \oplus e) x + (b \oplus e). The xx coordinate of this point can be specified in corrupted-curves and generated randomly in corrupted-curves+.

    Since ee is relatively smaller than a,ba, b, we can decompose ae,bea \oplus e, b \oplus e into MSB part and LSB part. MSB part is always fixed, while LSB part is different in each time because of ee. Since we know (x,y)(x, y) and have many linear relationship, we can leak a,ba, b by LLL.

    The solver is almost the same in corrupted-curves and corrupted-curves+. I pasted one for corrupted-curves.

    solve.sage
    from pwn import remote
    
    
    M = 6
    
    io = remote("be.ax", 31345)
    io.recvuntil(b"p = ")
    p = int(io.recvline())
    io.recvuntil(b"flag y = ")
    flag_y = int(io.recvline())
    
    points = []
    for _ in range(100):
        x = random.randint(2**384, p - 2**384)
        io.sendlineafter(b"x = ", str(x).encode())
        io.recvuntil(b"e = ")
        e = int(io.recvline())
        ret = io.recvline().strip().decode()
        if "y = " in ret:
            y = int(ret[4:])
            points.append((x, y, e))
        if len(points) >= M:
            break
    
    mat = matrix(ZZ, 3*M+3, 3*M+3)
    mat[0, 0] = 1
    mat[1, 1] = 1
    mat[2, 2] = 1
    for i in range(2*M):
        mat[3+i, 3+i] = 1
    for i in range(M):
        x, y, e = points[i]
        j = 3+2*M+i
        mat[0, j] = x * 2**64
        mat[1, j] = 2**64
        mat[2, j] = (x**3 - y**2) % p
        mat[3+2*i, j] = x
        mat[3+2*i+1, j] = 1
        mat[3+2*M+i, j] = -p
    weights = diagonal_matrix([1, 1, 2**320] + [2**256] * 2*M + [round(2**320 * sqrt(3*M+3))] * M)
    mat *= weights
    res = mat.LLL()
    mat /= weights
    res /= weights
    C = mat.solve_left(res)
    
    for data in res:
        if abs(data[2]) != 1:
            continue
        if data[2] == -1:
            data = -data
        for i in range(M):
            e = points[i][2]
            a = int(data[0] * 2**64 + data[3+i]) ^^ e
            b = int(data[1] * 2**64 + data[4+i]) ^^ e
            PR.<x> = PolynomialRing(GF(p))
            f = x**3 + a*x + b - flag_y**2
            roots = f.roots()
            # not necessarily found correct a, b. I don't know why...so I print all patterns
            print([long_to_bytes(int(root[0])) for root in roots])
        break

    corctf{i_h0pe_you_3njoyed_p1ecing_t0geth3r_th4t_curv3_puzz1e_:)} corctf{cr4ftin6_f3as1ble_brut3s_unt1l_y0u_mak3_it!}

    threetreasures

    19 solves

    source.py
    from sage.all import *
    from Crypto.Util.number import bytes_to_long, getPrime
    from random import getrandbits
    from secret import flag, p, x, y
    
    def random_pad(n, length):
        return (n << (length - n.bit_length())) + getrandbits(length - n.bit_length())
    
    flag = bytes_to_long(flag)
    fbits = flag.bit_length()
    piece_bits = fbits // 3
    a, b, c = flag >> (2 * piece_bits), (flag >> piece_bits) % 2**piece_bits, flag % 2**piece_bits
    print(a, b, c)
    print(f'flag bits: {fbits}')
    assert p.bit_length() == 512
    q = getPrime(512)
    n = p * q
    ct = pow(random_pad(c, 512), 65537, n)
    E = EllipticCurve(GF(p), [a, b])
    G = E(x, y)
    assert G * 3 == E(0, 1, 0)
    print(f"n = {n}")
    print(f"ct = {ct}")
    print(f"G = {G}")

    flag is separated into three parts, a,b,ca, b, c. We are given the point GG on the elliptic curve y2=x3+ax+by^2 = x^3 + ax + b on Fp\mathbb{F}_p such that 3G=O3G = O. We also have pad(c)65537modn\mathrm{pad}(c)^{65537} \mod n.

    First consider about 3G=O3G = O. This is equivalent to 2G=G2G = -G, which means xx of 2G2G equals to xx of GG. From this relation, we have a2+6Gx2a+9Gx412GxGy2=0modpa^2 + 6G_x^2a + 9G_x^4 - 12G_xG_y^2 = 0 \mod p. Since aa is relatively small in this equation and pnp | n, we can use Coppersmith method to find aa. I tried it but it took much time...So I used information of the prefix of the flag. Using this, aa was found fast.

    Now that aa is known, Gy2=Gx3+aGx+bmodpG_y^2 = G_x^3 + aG_x + b \mod p can be solved with regard to bb using Coppersmith method again. Also, using 2 equations mentioned above, we can find pp by GCD. Then nn can be factored. cc can be found by simple calculation like RSA.

    solve.sage
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    
    
    n = 97915144495462666300795364589570761584322186881492143950078938328867290046424857019504657598883431857075772605985768551863478086544857915637724181292135280539943713583281151707224031808445390796342632369109562433275679473233398168787639940620683354458292117457239552762694657810883738834935391913698852811737
    ct = 20363336204536918055183609604474634074539942561101208682977506918349108499764147141944713060658857301108876346227077713201766486360148051069618774935469969057808945271860025712869868421279488925632657486125211168314387620225601572070169746014988350688548088791906161773656057212229972967244998930356157725393
    Gx = 3115938227771961657567351113281194074601897467086373590156577019504528350118731801249444974253028485083440228959842232653488953448859690520619223338133881
    Gy = 2665631524518629436093690344927156713668794128141943350227439039472817541262750706395352700109556004195261826476428128993836186741129487842876154876730189
    
    
    PR.<a_lsb> = PolynomialRing(Zmod(n))
    a = bytes_to_long(b"corctf{") * 2**(125-55) + a_lsb
    f = a ** 2 + 6 * Gx**2 * a + 9 * Gx**4 - 12 * Gx * Gy**2
    beta = 0.5
    delta = 2.0
    X = 2**70
    epsilon = RR(beta**2/delta - log(X) / log(n))
    a_lsb = f.small_roots(X=X, beta=0.5, epsilon=epsilon)[0]
    a = bytes_to_long(b"corctf{") * 2**(125-55) + a_lsb
    
    PR.<b> = PolynomialRing(Zmod(n))
    f = Gx**3 + Gx * a + b - Gy**2
    b = f.small_roots(beta=0.5)[0]
    
    tmp1 = (Gx**3 + Gx * a + b - Gy**2) % n
    tmp2 = a ** 2 + 6 * Gx**2 * a + 9 * Gx**4 - 12 * Gx * Gy**2
    p = int(gcd(tmp1, tmp2))
    assert is_prime(p)
    assert n % p == 0
    q = n // p
    d = int(pow(0x10001, -1, (p - 1) * (q - 1)))
    c = int(pow(ct, d, n))
    c = c >> (c.bit_length() - 125)
    
    long_to_bytes(int(2**250 * a + 2**125 * b + c))

    corctf{you_have_conquered_the_order_of_three!!}

    leapfrog

    36 solves

    leapfrog.py
    from Crypto.Util.number import long_to_bytes, getPrime
    from Crypto.Cipher import AES
    from Crypto.Util.Padding import pad
    from hashlib import sha256
    from secrets import randbelow
    from random import sample
    
    p = getPrime(256)
    a = randbelow(p)
    b = randbelow(p)
    s = randbelow(p)
    
    def f(s):
        return (a * s + b) % p
    
    jumps = sample(range(3, 25), 12)
    output = [s]
    for jump in jumps:
        for _ in range(jump):
            s = f(s)
        output.append(s)
    
    print(jumps)
    print(output)
    
    flag = open("flag.txt", "rb").read()
    key = sha256(b"".join([long_to_bytes(x) for x in [a, b, p]])).digest()[:16]
    iv = long_to_bytes(randbelow(2**128))
    
    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    print(iv.hex() + cipher.encrypt(pad(flag, 16)).hex())

    This is the hardest (maybe) of a series of LCG-related challenges.

    Let the current state be ss and the state after nn steps be ss'. We can write s=ans+(an1+an2++1)bmodps' = a^n s + (a^{n-1} + a^{n-2} + \cdots + 1) b \mod p. If we know three kinds of (s,s)(s, s') in fixed nn, say, s1=ans1+(an1++1)bmodp,s2=ans2+(an1++1)bmodp,s3=ans3+(an1++1)bmodps_1' = a^n s_1 + (a^{n-1} + \cdots + 1) b \mod p, s_2' = a^n s_2 + (a^{n-1} + \cdots + 1) b \mod p, s_3' = a^n s_3 + (a^{n-1} + \cdots + 1) b \mod p, we can have two equations, s1s3=an(s1s3)modp,s2s3=an(s2s3)modps_1' - s_3' = a^n (s_1 - s_3) \mod p, s_2' - s_3' = a^n (s_2 - s_3) \mod p. Using these two equations, we have (s1s3)(s2s3)(s1s3)(s2s3)=0modp(s_1' - s_3')(s_2 - s_3) - (s_1 - s_3)(s_2' - s_3') = 0 \mod p, which means that we find a multiple of pp.

    Such (s,s)(s, s') pairs are easily found by brute force:

    for n in range(40):
        for i in range(n - 1):
            for j in range(i, len(jumps)):
                if sum(jumps[i: j+1]) == n:
                    print(n, i, j)
    """
    16 5 6
    16 7 8
    16 11 11
    ...
    30 4 5
    30 6 9
    30 8 10
    """
    

    We can find pp by calculating GCD of a few multiples of pp.

    p_mul1 = (output[5] - output[11]) * (output[9] - output[12]) - (output[7] - output[12]) * (output[7] - output[11])
    p_mul2 = (output[4] - output[8]) * (output[10] - output[11]) - (output[6] - output[11]) * (output[6] - output[8])
    p_mul = gcd(p_mul1, p_mul2)
    # factor p_mul
    p = 82854189798454303629690440183768928075006051188051668052925581650741089039941

    After pp is found, we can enumerate candidates for aa by solving s1s3=an(s1s3)modps_1' - s_3' = a^n (s_1 - s_3) \mod p. Correct aa leads to correct bb and, therefore, key for AES.

    PR.<a> = PolynomialRing(Zmod(p))
    f = a**30 * (output[4] - output[8]) - (output[6] - output[11])
    g = a**16 * (output[5] - output[11]) - (output[7] - output[12])
    for a, _ in set(f.roots()) & set(g.roots()):
        PR.<b> = PolynomialRing(Zmod(p))
        f = a**3 * output[1] + (a**2 + a + 1) * b - output[2]
        b = f.roots()[0][0]
    
        key = sha256(b"".join([long_to_bytes(int(x)) for x in [a, b, p]])).digest()[:16]
        cipher = AES.new(key, AES.MODE_CBC, iv=iv)
        print(cipher.decrypt(enc_flag))

    corctf{:msfrog:_is_pr0ud_0f_y0ur_l34pfr0gg1ng_4b1lit135}

    generous

    49 solves

    generous.py
    #!/usr/local/bin/python
    from Crypto.Util.number import getPrime, inverse, bytes_to_long
    from random import randrange
    
    with open("flag.txt", "rb") as f:
    	flag = f.read().strip()
    
    def gen_keypair():
    	p, q = getPrime(512), getPrime(512)
    	n = (p**2) * q
    	while True:
    		g = randrange(2, n)
    		if pow(g, p-1, p**2) != 1:
    			break
    	h = pow(g, n, n)
    	return (n, g, h), (g, p, q)
    
    def encrypt(pubkey, m):
    	n, g, h = pubkey
    	r = randrange(1, n)
    	c = pow(g, m, n) * pow(h, r, n) % n
    	return c
    
    def decrypt(privkey, c):
    	g, p, q = privkey
    	a = (pow(c, p-1, p**2) - 1) // p
    	b = (pow(g, p-1, p**2) - 1) // p
    	m = a * inverse(b, p) % p
    	return m
    
    def oracle(privkey, c):
    	m = decrypt(privkey, c)
    	return m % 2
    
    pub, priv = gen_keypair()
    n, g, h = pub
    print(f"Public Key:\n{n = }\n{g = }\n{h = }")
    print(f"Encrypted Flag: {encrypt(pub, bytes_to_long(flag))}")
    while True:
    	inp = int(input("Enter ciphertext> "))
    	print(f"Oracle result: {oracle(priv, inp)}")

    This cryptosystem is Okamoto-Uchiyama cryptosystem. As mentioned in wiki, it has homomorphic property.

    Let flag be mm. If we decrypt Enc(m)Enc(x)\mathrm{Enc}(m) \mathrm{Enc(-x)}, we get mxmodnm - x \mod n. When xmx \le m, the parity of mxm - x is (mmod2)(xmod2)(m \mod 2) \oplus (x \mod 2). But when x>mx > m, the parity of mxm - x is (mmod2)(xmod2)1(m \mod 2) \oplus (x \mod 2) \oplus 1 because nn is odd. Since we know mmod2m \mod 2 and xmod2x \mod 2, we can check whether mm is less than xx or not. Using this oracle we can find mm by bisection method.

    solve.py
    from Crypto.Util.number import long_to_bytes
    from pwn import remote
    
    io = remote("be.ax", 31244)
    io.recvuntil(b"n = ")
    n = int(io.recvline())
    io.recvuntil(b"g = ")
    g = int(io.recvline())
    io.recvuntil(b"h = ")
    h = int(io.recvline())
    io.recvuntil(b"Encrypted Flag: ")
    enc_flag = int(io.recvline().strip().decode())
    
    
    def oracle(c):
        io.sendlineafter(b"ciphertext> ", str(c).encode())
        io.recvuntil(b"result: ")
        return int(io.recvline())
    
    
    parity = oracle(enc_flag)
    lb = 0
    ub = 2**512
    prev_c = None
    while True:
        c = (lb + ub) // 2
        print(c)
        tmp_parity = oracle(pow(g, -c, n) * enc_flag % n)
        expected_parity = (parity + c) % 2
        if tmp_parity == expected_parity:
            lb = c
        elif tmp_parity != expected_parity:
            ub = c
        if c == prev_c:
            break
        prev_c = c
    print(long_to_bytes(c))

    corctf{see?1_bit_is_very_generous_of_me}

      ;