aeroctf-2021-boggart-1.py

from tqdm import tqdm
import itertools

a = 2821195960321037446898632288244857039957436317435079530335838687362728781410518376744718668720674542350849058769480974085257339164002397119874864207374402
n = 40740327153595270257184780086389953086261120133330698714430641164791044793765728073225136444807495004396268705143115221155717342774153766221474052678956440685995627998728286518422095251317829948639280532042852083900018149268443333895256994879066082385467247811575697036554762935124165948190148187259065768291
c1 = 15299456059343864873123154423984261053470218681269222999806760034801685415379067250969562401321861706151458942840378672266201861683639418278459552822540046204949846903038296947417264184399589146790321851766505139908198090643208050906176021749895564834817658625411004900331537016317911934175301113463305243807
c2 = 3267717973811111609903663596742254164063220133087752184817781695697908008925137677479510304910242404913861174791103168198130734948188615352598500632087933572038101234710649413034772756931619820126488033076322005589499275550327993762859918547931137968414798501640493731151872472338268205516239441527853522482

print(f'a = {a}')
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

# should be all true when i >= 20
set_bits = []
for i in range(512):
    if (a&(1<<i)) == 0: continue
    set_bits.append(i)
print(f'set_bits = {set_bits}')
while set_bits[0] < 20: set_bits.pop(0)

md = 1<<set_bits[0]
tg = n % md
parts = []
for p in tqdm(range(1, md, 2)):
    q = tg * pow(p, md//2-1, md) % md
    parts.append((p, q))

for i in range(1, len(set_bits)):
    pos = set_bits[i]

    b  = 1<<set_bits[i-1]
    md = 1<<set_bits[i]
    tg = n % md

    new_parts = []
    print(f'[ ] Trying new pos = {pos}')
    for p, q in tqdm(parts):
        for dp, dq in itertools.product(range(b, md, 2*b), repeat=2):
            p2, q2 = p + dp, q + dq
            if p2 * q2 % md != tg: continue
            new_parts.append((p2, q2))

    parts = new_parts
    print(f'[*] pos = {pos} | len(parts) = {len(parts)}')

# Last bit
if True:
    b  = 1<<set_bits[-1]

    cnt = 0
    new_parts = []
    print(f'[ ] Trying new pos = {pos}')
    for p, q in tqdm(parts):
        for dp, dq in itertools.product(range(b, 2**512, 2*b), repeat=2):
            p2, q2 = p + dp, q + dq
            if p2 * q2 != n: continue
            cnt += 1
            new_parts.append((p2, q2))
            assert cnt < 10000000, 'Too heavy!'

    parts = new_parts
    print(f'[*] pos = {pos} | len(parts) = {len(parts)}')

print(f'[*] parts = {parts}')