Codegate 2024 Quals - FactorGame (Crypto)

factorgame.py

from sage.all import *
from binteger import Bin
from sock import Sock
from tqdm import tqdm
import time

known = 264
t = known + 4


@parallel(ncpus=8)
def try_sol(N, lo, epsilon):
    R, x = Zmod(N)['x'].objgen()
    beta = 0.5000001
    X = 2**(512 - t)
    # epsilon = RR(beta**2 - log(2*X, N)) * 1.8
    # epsilon = 0.019

    poly = (x * 2**t + lo) / 2**t
    res = poly.small_roots(X=X, beta=beta, epsilon=epsilon)
    if res:
        x = int(res[0])
        q = x * 2**t + lo
        return q


def try_solve(rnd, p_redacted, p_mask, q_redacted, q_mask, N):
    tt = max(Bin(p_mask).n, Bin(q_mask).n)
    print("bits", tt, "using", t)
    sols = {(0, 0)}
    for e in range(1, t+1):
        sols2 = set()
        bit = 2**(e-1)
        mask = 2**e - 1
        Nmask = N & mask
        for (p, q) in sols:
            for pbit in range(2):
                for qbit in range(2):
                    pp = p + bit * pbit
                    qq = q + bit * qbit
                    if (pp * qq) & mask != Nmask:
                        continue
                    if pp & p_mask & mask != p_redacted & mask:
                        continue
                    if qq & q_mask & mask != q_redacted & mask:
                        continue
                    sols2.add((pp, qq))
        sols = sols2
        #assert (sol_p & mask, sol_q & mask) in sols, e
        if len(sols) >= 100_000:
            raise RuntimeError("too many sols mid %d" % len(sols))
    #assert sol_p & p_mask == p_redacted
    #assert sol_q & q_mask == q_redacted

    if rnd <= 1 and len(sols) > 16:
        raise RuntimeError("too many sols end %d for round 1" % len(sols))

    if len(sols) <= 32:
        epsilon = 0.018
    elif len(sols) <= 128:
        epsilon = 0.020
    else:
        raise RuntimeError("too many sols end %d" % len(sols))

    print("sols", len(sols), "eps", epsilon)

    todo = []
    for plo, qlo in sols:
        for lo in plo, qlo:
            todo.append((N, lo, epsilon))

    res = try_sol(todo)
    #print("res", res)
    for item in tqdm(res, total=len(todo)):
        q = item[-1]
        if q:
            print("got q", q)
            if N % q == 0:
                p = N // q
                return p, q
    raise RuntimeError("no sol found")


def one_round(f, rnd, att):
    print(repr(f.read_until("p : 0x")))
    p_red = int(f.read_line(), 16)

    f.read_until("p_mask : 0x")
    p_mask = int(f.read_line(), 16)

    f.read_until("q : 0x")
    q_red = int(f.read_line(), 16)

    f.read_until("q_mask : 0x")
    q_mask = int(f.read_line(), 16)

    f.read_until("N : 0x")
    N = int(f.read_line(), 16)

    try:
        p, q = try_solve(rnd, p_red, p_mask, q_red, q_mask, N)
        print("good")
        assert p * q == N
        print("N =", N)
        print("p =", p)
        print("q =", q)
        if p & p_mask != p_red:
            print("weird")
            p, q = q, p
            if p & p_mask != p_red:
                print("weird x2")
            else:
                print("fixed with swap!")
        assert p & p_mask == p_red
        assert q & q_mask == q_red
    except RuntimeError as err:
        print("fail at", rnd, att, err)
        p = q = 1

    f.read_until("format : ")
    f.send_line("%x" % p)
    f.read_until("format : ")
    f.send_line("%x" % q)
    print(repr(f.read_line()))
    return p > 1

def try_game():
    f = Sock("3.38.106.210 8287")
    n_fail = 0
    t0 = time.time()
    for rnd in range(1, 11):
        for att in range(5):
            print("game", itr, ":", "round", rnd, "attempt", att, "elapsed %.1fs" % (time.time() - t0), "fails", n_fail)
            try:
                if one_round(f, rnd, att):
                    break
            except EOFError:
                print(repr(f.buf))
                with open("flag", "a") as fd:
                    print(repr(f.buf), file=fd)
                quit()
            print()
        else:
            n_fail += 1
            if rnd <= 3:
                print("too bad")
                return
            if n_fail > 2:
                print("failed total")
                print()
                print()
                return

        print()
        print()
        print()

    res = f.read_all()
    print(repr(res))
    with open("flag", "a") as fd:
        print(repr(res), file=fd)
    quit()


itr = 0
while True:
    itr += 1
    try_game()

'''
game 5 : round 10 attempt 2 elapsed 234.6s fails 0
b'3 lives left\np : 0x'
bits 264 using 268
sols 32 eps 0.018
 78%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                            | 50/64 [00:32<00:11,  1.22it/s]got q 10997054323561818225627930817190121870148076872349532984029966049428755873173999306760450827117779835552778242892163554479516673800668045007996629716550507
 81%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                     | 52/64 [00:32<00:07,  1.61it/s]
good
N = 108729213560919453489017769490842645201939299979770347745129782893279538126376182879520512315802214211263942903425302844178219568345447116061716258640605345728813575388707796220205379498000564369176418445429518637166016916708308075828824268610139009340073450585700499976197745794152877808312438678227042727661
p = 9887121620192499285864777756915217008323970163039899027117253454822412299040807448238708159185682656399718238795947740522734631896783324628630204920438023
q = 10997054323561818225627930817190121870148076872349532984029966049428755873173999306760450827117779835552778242892163554479516673800668045007996629716550507
b'success!\n'



b'master of factoring!!\nhere is your flag : codegate2024{53da1bba1185a69190cd95233fa0504229461dd0d304fd088caad30035ee93e147db5caebf23c73c0edbea5d0b2ca57ca1afd75cb73a80}\n\n'

________________________________________________________
Executed in  311.54 secs    fish           external
   usr time   27.01 mins    0.00 micros   27.01 mins
   sys time    0.95 mins  892.00 micros    0.95 mins

'''