ASIS CTF Finals 2022 | bedouin

#ASIS_CTF_Finals_2022

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import nbit, l, flag

def genbed(nbit, l):
    while True:
        zo = bin(getPrime(nbit))[2:]
        OZ = zo * l + '1'
        if isPrime(int(OZ)):
            return int(OZ)

p, q = [genbed(nbit, l) for _ in '01']
n = p * q
d = 1 ^ l ** nbit << 3 ** 3
phi = (p - 1) * (q - 1)
e = inverse(d, phi)
m = bytes_to_long(flag)
c = pow(m, e, n)

if pow(c, d, n) == m:
    print(f'n = {n}')
    print(f'c = {c}')

Suspicious PrimeなRSA。素数の生成が という01の繰り返しになっているのでSECCON 2020 | This is RSAのようにbranch and pruneで素因数分解できる

def dfs(n, p_: str, q_: str):
    if len(str(n)) <= len(p_):
        return None

    k = len(p_) + 1
    mod = 10**k
    for pb in '01':
        for qb in '01':
            ps = pb + p_
            qs = qb + q_
            p = int(ps)
            q = int(qs)

            if n == p * q:
                return p, q

            if n % mod == (p * q) % mod:
                r = dfs(n, ps, qs)
                if r is not None:
                    return r


p, q = dfs(n, '', '')
# print(p, q)
ps = str(p)[:-1]
qs = str(q)[:-1]
k = 0
while k < len(ps):
    k += 1

    if len(ps) % k != 0 or len(qs) % k != 0:
        continue

    l = len(ps) // k
    if ps[:k] * l == ps and qs[:k] * l == qs:
        d = 1 ^ l ** k << 3 ** 3
        m = pow(c, d, n)
        print(m.to_bytes(100, "big"))