SECCON 2022 CTF Quals: this_is_not_lsb

this_is_not_lsb.py

from Crypto.Util.number import *
from gmpy2 import powmod as pow
from pwn import *


def get_var(rmt, f): return f(rmt.recvline().split()[2])

rmt = remote('this-is-not-lsb.seccon.games', 8080)
n = get_var(rmt, int)
e = get_var(rmt, int)
flag_length = get_var(rmt, int)
c = get_var(rmt, int)

pattern = 0xFF << (n.bit_length() - 10)
flag_str_length = (flag_length + 1) // 8

def check(k):
    c_k = pow(k, e, n) * c % n
    rmt.sendline(str(c_k).encode())
    return get_var(rmt, lambda s: s == b'True')

# The range of strings that the flags can take is
# `SECCON{\x20\x00...\x00` - `SECCON{\x7F\x00...\x00`
lo = pattern // bytes_to_long(b'SECCON{\x7F' + bytes(flag_str_length - 8))
hi = pattern // bytes_to_long(b'SECCON{\x20' + bytes(flag_str_length - 8))
assert(check(lo) == False)
assert(check(hi) == True)

while hi - lo > 1:
    k = (lo + hi) >> 1
    if check(k): hi = k
    else: lo = k

print(long_to_bytes(pattern // lo).decode())