Cryptoverse CTF 2023 - picochip1

solve.py

from sage.all import crt, lcm, reduce
from Crypto.Util.number import *

# fmt: off
pico_r = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283]
# fmt: on


def solve_eqs(eqs):
    if len(eqs) < 2:
        return 0, 0
    ms = [-k for k, _ in eqs]
    ps = [p for _, p in eqs]
    L = reduce(lcm, ps)
    res = crt(ms, ps)
    return L, res


def solve(st, N, t):
    eqs = []
    k = 0
    idx = 0
    while idx < len(st):
        for i, s in enumerate(st[idx : idx + N]):
            idx += 1
            if s == 0:
                eqs.append((k, pico_r[i]))
                # assert (vp + k) % pico.r[i] == 0
                k += 2
                break
        else:
            L, cur_vv = solve_eqs(eqs)
            print(f"{L = }")
            print(f"{cur_vv = }")
            for s in st[idx : idx + t]:
                idx += 1
                if s == 0:
                    k += 2
                    break
                if isPrime(cur_vv + k):
                    print("FOUND1", cur_vv + k)
                    return cur_vv + k, st[idx:]
                if L and (2**37 // L) < 10000:
                    for u in range(2**37 // L):
                        if isPrime(cur_vv + k + u * L):
                            print("FOUND2", cur_vv + k + u * L)
                            return cur_vv + k + u * L, st[idx:]


# fmt: off
gy = [66,66,0,0,10,10,0,0,0,0,1,1,0,0,60,60,0,0,0,0,2,2,0,0,3,3,0,0,0,0,17,17,0,0,60,60,0,0,0,0,12,12,0,0,1,1,0,0,0,0,4,4,0,0,41,41,0,0,0,0,1,1,0,0,6,6,0,0,0,0,65,65,0,0,0,0,2,2,0,0,1,1,0,0,0,0,3,3,0,0,48,48,0,0,0,0,1,1,0,0,2,2,0,0,0,0,29,29,0,0,28,28,0,0,0,0,60,60,0,0,5,5,0,0,0,0,16,16,0,0,1,1,0,0,0,0,25,25,0,0,61,61]
# fmt: on
power = gy[::2]

st = sum([[0] if v == 0 else [1] * v for v in power], [])
print(st)
st = st[60:]
p, stt = solve(st, 60, 1)
print(stt)
q, _ = solve(stt, 60, 1)

e = 65537
ct = 3059648962482294740345
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(ct, d, p * q)
print(int(m).to_bytes(100, "big").strip(b"\x00"))
# cvctf{p1C@-_}