[CryptoCTF 2023]Suction chen_xing的WriteUp

这道题给出了n,e,c的高位，三个数据均缺少低8bit位，因此我们只需要进行爆破n并且尝试分解出128bit的p,q.爆破e,c，e在爆破的过程中可以判断是否与phi互质且是否为素数，c在爆破的过程中检验计算得到的flag是否满足全部是utf-8下的可显示字符即可。

from Crypto.Util.number import *
from sage.all import *

def check(flag):
    try:
        flag_str = flag.decode('utf-8')
        return flag_str.isprintable()
    except UnicodeDecodeError:
        return False

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761
PKEY_bin = bin(PKEY)[2:]
e_high = PKEY_bin[-8:]; n_high = PKEY_bin[:-8]
e_high = int(e_high, 2) << 8; n_high = int(n_high, 2) << 8; c_high = ENC << 8

"""
for i in range(2 ** 8):
    n = n_high + i
    factors = factor(n)
    if len(factors) == 2:
        print(factors)
"""
p = 188473222069998143349386719941755726311
q = 292926085409388790329114797826820624883
assert isPrime(p) and p.bit_length() == 128
phi = (p - 1) * (q - 1)
n = p * q
for i in range(2 ** 7):
    e = e_high + i * 2 + 1
    if isPrime(e) and GCD(e, phi) == 1:
        d = inverse(e, phi)
        for j in range(2 ** 8):
            c = c_high + j
            flag = long_to_bytes(pow(c, d, n))
            if check(flag):
                print(b'CCTF{' + flag + b'}')
                exit()
# b'CCTF{6oRYGy&Dc$G2ZS}'
​

但是在爆破n的过程中花费的时间太长了，解题后看了一下鸡块师傅的Wp，也去学习了一下Python中factordb库的使用。
PyPI
通过查表的方式比上面硬分解的时间上缩短了很多:

# exp_pro
from Crypto.Util.number import *
from factordb.factordb import FactorDB

def check(flag):
    try:
        flag_str = flag.decode('utf-8')
        return flag_str.isprintable()
    except UnicodeDecodeError:
        return False

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761
PKEY_bin = bin(PKEY)[2:]
e_high = PKEY_bin[-8:]; n_high = PKEY_bin[:-8]
e_high = int(e_high, 2) << 8; n_high = int(n_high, 2) << 8; c_high = ENC << 8

for i in range(2 ** 8):
    n = n_high + i * 2 + 1
    f = FactorDB(n)
    f.connect()
    factors = f.get_factor_list()
    if len(factors) == 2 and factors[0].bit_length() == 128:
        p, q = factors[0], factors[1]
        break
phi = (p - 1) * (q - 1)
n = p * q
for i in range(2 ** 7):
    e = e_high + i * 2 + 1
    if isPrime(e) and GCD(e, phi) == 1:
        d = inverse(e, phi)
        for j in range(2 ** 8):
            c = c_high + j
            flag = long_to_bytes(pow(c, d, n))
            if check(flag):
                print(b'CCTF{' + flag + b'}')
                exit()
# b'CCTF{6oRYGy&Dc$G2ZS}'
​