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 $e$ and one point on the elliptic curve $y^2 = x^3 + (a \oplus e) x + (b \oplus e)$. The $x$ coordinate of this point can be specified in corrupted-curves and generated randomly in corrupted-curves+.

Since $e$ is relatively smaller than $a, b$, we can decompose $a \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 $e$. Since we know $(x, y)$ and have many linear relationship, we can leak $a, 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, c$. We are given the point $G$ on the elliptic curve $y^2 = x^3 + ax + b$ on $\mathbb{F}_p$ such that $3G = O$. We also have $\mathrm{pad}(c)^{65537} \mod n$.

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

Now that $a$ is known, $G_y^2 = G_x^3 + aG_x + b \mod p$ can be solved with regard to $b$ using Coppersmith method again. Also, using 2 equations mentioned above, we can find $p$ by GCD. Then $n$ can be factored. $c$ 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 $s$ and the state after $n$ steps be $s'$. We can write $s' = a^n s + (a^{n-1} + a^{n-2} + \cdots + 1) b \mod p$. If we know three kinds of $(s, s')$ in fixed $n$, say, $s_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, $s_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 $(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 $p$.

Such $(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 $p$ by calculating GCD of a few multiples of $p$.

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 $p$ is found, we can enumerate candidates for $a$ by solving $s_1' - s_3' = a^n (s_1 - s_3) \mod p$. Correct $a$ leads to correct $b$ 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 $m$. If we decrypt $\mathrm{Enc}(m) \mathrm{Enc(-x)}$, we get $m - x \mod n$. When $x \le m$, the parity of $m - x$ is $(m \mod 2) \oplus (x \mod 2)$. But when $x > m$, the parity of $m - x$ is $(m \mod 2) \oplus (x \mod 2) \oplus 1$ because $n$ is odd. Since we know $m \mod 2$ and $x \mod 2$, we can check whether $m$ is less than $x$ or not. Using this oracle we can find $m$ 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}