CryptoCTF解题记录

2023

Blue Office

#!/usr/bin/enc python3

import binascii
from secret import seed, flag

def gen_seed(s):
	i, j, k = 0, len(s), 0
	while i < j:
		k = k + ord(s[i])
		i += 1
	i = 0
	while i < j:
		if (i % 2) != 0:
			k = k - (ord(s[i]) * (j - i + 1))            
		else:
			k = k + (ord(s[i]) * (j - i + 1))
	
		k = k % 2147483647
		i += 1

	k = (k * j) % 2147483647
	return k

def reseed(s):
	return s * 214013 + 2531011

def encrypt(s, msg):
	assert s <= 2**32
	c, d = 0, s
	enc, l = b'', len(msg)
	while c < l:
		d = reseed(d)
		enc += (msg[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
		c += 1
	return enc

enc = encrypt(seed, flag)
print(f'enc = {binascii.hexlify(enc)}')

# enc = b'b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce'

题目未知种子，但是发现并没用到gen_seed函数，简化一下看：

import binascii
from secret import seed, flag

def reseed(s):
	return s * 214013 + 2531011

def encrypt(s, msg):
	assert s <= 2**32
	c, d = 0, s
	enc, l = b'', len(msg)
	while c < l:
		d = reseed(d)
		enc += (msg[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
		c += 1
	return enc

enc = encrypt(seed, flag)
print(f'enc = {binascii.hexlify(enc)}')

# enc = b'b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce'

每轮加密对种子进行一个运算，然后取低$24$位的高$8$位和flag进行异或，由于计算时$d$的更高位运算不会影响到低$24$位的结果，所以可以直接取模爆破这$24$位找flag：

from Crypto.Util.number import *
from tqdm import tqdm

enc = long_to_bytes(int("b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce", 16))

def reseed(s):
    return s * 214013 + 2531011

for d in tqdm(range(2**24)):
    dec = ""
    for i in enc:
        dec += chr(i ^ ((d >> 16) & 0xFF))
        d = reseed(d) % 2**24
    if "CTF{" in dec:
        print(dec)

Derik

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import C, e, d, p, q, r, flag

O = [1391526622949983, 2848691279889518, 89200900157319, 31337]

assert isPrime(e) and isPrime(d) and isPrime(p) and isPrime(q) and isPrime(r)
assert C[0] * p - C[1] * q >= 0
assert C[2] * q - C[3] * r >= 0
assert C[4] * r - C[5] * p >= 0
assert (C[0] * p - C[1] * q) ** e + (C[2] * q - C[3] * r) ** e + (C[4] * r - C[5] * p) ** e == d * (C[0] * p - C[1] * q) * (C[2] * q - C[3] * r) * (C[4] * r - C[5] * p)
assert C[6] * e - C[7] * d == O[3]

n = e * d * p * q * r
m = bytes_to_long(flag)
c = pow(m, 65537, n)
print(f'C = {C}')
print(f'c = {c}')

# C = [5960650533801939766973431801711817334521794480800845853788489396583576739362531091881299990317357532712965991685855356736023156123272639095501827949743772, 6521307334196962312588683933194431457121496634106944587943458360009084052009954473233805656430247044180398241991916007097053259167347016989949709567530079, 1974144590530162761749719653512492399674271448426179161347522113979158665904709425021321314572814344781742306475435350045259668002944094011342611452228289, 2613994669316609213059728351496129310385706729636898358367479603483933513667486946164472738443484347294444234222189837370548518512002145671578950835894451, 8127380985210701021743355783483366664759506587061015828343032669060653534242331741280215982865084745259496501567264419306697788067646135512747952351628613, 5610271406291656026350079703507496574797593266125358942992954619413518379131260031910808827754539354830563482514244310277292686031300804846114623378588204, 10543, 4]
# c = 80607532565510116966388633842290576008441185412513199071132245517888982730482694498575603226192340250444218146275844981580541820190393565327655055810841864715587561905777565790204415381897361016717820490400344469662479972681922265843907711283466105388820804099348169127917445858990935539611525002789966360469324052731259957798534960845391898385316664884009395500706952606508518095360995300436595374193777531503846662413864377535617876584843281151030183895735511854

题目给了很多式子，找几个有价值的看一下：

定义：

$$\begin{cases} C_0p-C_1q=A\\ C_2q-C_3r=B\\ C_4r-C_5p=C\\ \end{cases}$$

有：

$$A^e+B^e+C^e=dABC$$ $$C_6e-C_7d=O_3$$

这里注意到$C$的最后两个值分别为$10543,4$，这两个和$e,d$线性组合得到的$O_3$值为$31337$：

$$10543e-4d=31337$$

跑出几组解：

3 73
27 63331
43 105503
67 168761
115 295277
123 316363
.......

这里回到这个方程：

$$A^e+B^e+C^e=dABC$$

$ABC$数量级差不多的情况下，左边是求和，右边是求积，观察了一下跑出的几组解，当$e=3$时大概能和左右两侧的数量级关系对上，此时$d=73$也不影响数量级，如果$e$更大些的话左侧数量级会迅速增长，就会变得不合理。所以这里近乎可以肯定$e=3$：

$$A^3+B^3+C^3=73ABC$$

此外这个题目还有一个有趣的事情：

O = [1391526622949983, 2848691279889518, 89200900157319, 31337]

assert C[0] * p - C[1] * q >= 0
assert C[2] * q - C[3] * r >= 0
assert C[4] * r - C[5] * p >= 0
assert (C[0] * p - C[1] * q) ** e + (C[2] * q - C[3] * r) ** e + (C[4] * r - C[5] * p) ** e == d * (C[0] * p - C[1] * q) * (C[2] * q - C[3] * r) * (C[4] * r - C[5] * p)
assert C[6] * e - C[7] * d == O[3]

这里的$O$数组有四个值，但是实际上这个题只出现了其中的一个，另外三个如果只是单纯给出这个数又显得有些突兀。于是可以推测：

$$\begin{cases} C_0p-C_1q=O_0\\ C_2q-C_3r=O_1\\ C_4r-C_5p=O_2\\ C_6e-C_7d=O_3 \end{cases}$$

看起来很合理，我们依照这种假设继续做下去，能得到：

$$\begin{bmatrix} C_0&-C_1&0\\ 0&C_2&-C_3\\ -C_5&0&C_4\\ \end{bmatrix} \begin{bmatrix} p\\ q\\ r\\ \end{bmatrix} = \begin{bmatrix} O_0\\ O_1\\ O_2\\ \end{bmatrix}$$

两侧同时乘三维矩阵的逆矩阵，就可以得到$pqr$向量了，用sage解一下：

from Crypto.Util.number import *

C = [
    5960650533801939766973431801711817334521794480800845853788489396583576739362531091881299990317357532712965991685855356736023156123272639095501827949743772,
    6521307334196962312588683933194431457121496634106944587943458360009084052009954473233805656430247044180398241991916007097053259167347016989949709567530079,
    1974144590530162761749719653512492399674271448426179161347522113979158665904709425021321314572814344781742306475435350045259668002944094011342611452228289,
    2613994669316609213059728351496129310385706729636898358367479603483933513667486946164472738443484347294444234222189837370548518512002145671578950835894451,
    8127380985210701021743355783483366664759506587061015828343032669060653534242331741280215982865084745259496501567264419306697788067646135512747952351628613,
    5610271406291656026350079703507496574797593266125358942992954619413518379131260031910808827754539354830563482514244310277292686031300804846114623378588204,
    10543,
    4,
]
c = 80607532565510116966388633842290576008441185412513199071132245517888982730482694498575603226192340250444218146275844981580541820190393565327655055810841864715587561905777565790204415381897361016717820490400344469662479972681922265843907711283466105388820804099348169127917445858990935539611525002789966360469324052731259957798534960845391898385316664884009395500706952606508518095360995300436595374193777531503846662413864377535617876584843281151030183895735511854
O = [1391526622949983, 2848691279889518, 89200900157319, 31337]

e = 3
d = (C[6] * e - O[3]) // C[7]

A = Matrix([[C[0], -C[1], 0], [0, C[2], -C[3]], [-C[5], 0, C[4]]])
U = Matrix([[O[0]], [O[1]], [O[2]]])
p, q, r = [int(i[0]) for i in A.inverse() * U]

n = p * q * r * e * d
phi = (p - 1) * (q - 1) * (r - 1) * (e - 1) * (d - 1)
E = 0x10001
D = inverse(E, phi)
m = pow(c, D, n)
print(long_to_bytes(int(m)))

Barak

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def on_barak(P, E):
	c, d, p = E
	x, y = P
	return (x**3 + y**3 + c - d*x*y) % p == 0

def add_barak(P, Q, E):
	if P == (0, 0):
		return Q
	if Q == (0, 0):
		return P
	assert on_barak(P, E) and on_barak(Q, E)
	x1, y1 = P
	x2, y2 = Q
	if P == Q:
		x3 = y1 * (c - x1**3) * inverse(x1**3 - y1**3, p) % p
		y3 = x1 * (y1**3 - c) * inverse(x1**3 - y1**3, p) % p
	else:

		x3 = (y1**2*x2 - y2**2*x1) * inverse(x2*y2 - x1*y1, p) % p
		y3 = (x1**2*y2 - x2**2*y1) * inverse(x2*y2 - x1*y1, p) % p
	return (x3, y3)

def mul_barak(m, P, E):
	if P == (0, 0):
		return P
	R = (0, 0)
	while m != 0:
		if m & 1:
			R = add_barak(R, P, E)
		m = m >> 1
		if m != 0:
			P = add_barak(P, P, E)
	return R

def rand_barak(E):
	c, d, p = E
	while True:
		y = randint(1, p - 1)
		K = Zmod(p)
		P.<x> = PolynomialRing(K) 
		f = x**3 - d*x*y + c + y^3
		R = f.roots()
		try:
			r = R[0][0]
			return (r, y)
		except:
			continue

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1
E = (c, d, p)

P = rand_barak(E)

FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
m = bytes_to_long(FLAG) 
assert m < p
Q = mul_barak(m, P, E)
print(f'P = {P}')
print(f'Q = {Q}')

题目给出了一个椭圆曲线：

$$X^3+Y^3+1\equiv dXY\pmod p$$

取了椭圆曲线一个随机点$P$，计算倍乘$Q=mP$，给出了$P,Q$求$m$：

这题的曲线和Derik题目的一个式子非常相似，可以考虑换元尝试转到那个多项式上：

$$X = \frac{X'}{Z'},Y = \frac{Y'}{Z'}$$ $$X'^3+ Y'^3 +Z'^3 = dX'Y'Z' \pmod p$$

这个可以构造出一条曲线，尝试在曲线上求解DLP即可，这里用的构造方法是E = EllipticCurve_from_cubic(cubic,morphism=True)，可以根据一个三次方程cubic来构造方程：

from Crypto.Util.number import *

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1
P = (71451574057642615329217496196104648829170714086074852, 69505051165402823276701818777271117086632959198597714)
Q = (40867727924496334272422180051448163594354522440089644, 56052452825146620306694006054673427761687498088402245)

R.<x,y,z> = Zmod(p)[]
cubic = x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)

最后求出的$m$直接解密并不能得到真正的flag，知道$m<p$，所以可能比曲线阶order稍微大一些，可以爆破一下：

from Crypto.Util.number import *

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1
P = (71451574057642615329217496196104648829170714086074852, 69505051165402823276701818777271117086632959198597714)
Q = (40867727924496334272422180051448163594354522440089644, 56052452825146620306694006054673427761687498088402245)

R.<x,y,z> = Zmod(p)[]
cubic = x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
m = P.discrete_log(Q)
order = P.order()

for i in range(10000):
    try:
        flag = long_to_bytes(int(m)).decode()
        print(flag,i)
        break
    except:
        m += order

Suction

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def keygen(nbit, r):
	while True:
		p, q = [getPrime(nbit) for _ in '__']
		e, n = getPrime(16), p * q
		phi = (p - 1) * (q - 1)
		if GCD(e, phi) == 1:
			N = bin(n)[2:-r]
			E = bin(e)[2:-r]
			PKEY = N + E
			pkey = (n, e)
			return PKEY, pkey

def encrypt(msg, pkey, r):
	m = bytes_to_long(msg)
	n, e = pkey
	c = pow(m, e, n)
	C = bin(c)[2:-r]
	return C

r, nbit = 8, 128
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

'''
PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761
'''

一个RSA题目，提供了一个PKEY，是n的高120位和e的高8位组合起来的，未知两个值的低八位。

想到的思路是先把n低位爆破一下，然后得到分解，由于这里的n位数很小所以可以使用factordb库进行在线分解：

from factordb.factordb import FactorDB

f = FactorDB(n)
f.connect()
fs = f.get_factor_list()

分解完之后如果能得到我们符合的两个因子，也就是爆破出了正确的n，继续爆破e，同时还需要爆破密文c的低八位，实际上这样爆破下来耗时会比较长，可以寻找一些简化方法：

由于质数都是模二余一的，两个质数相乘应该还是模二余一的，所以模数n应该是模二余一，可以确定最后一位一定为1。同理，e作为质数也应该满足这个规则。

当某一轮爆破的e不是质数，直接忽略爆破密文的部分即可。

from Crypto.Util.number import *
from tqdm import *
from factordb.factordb import FactorDB
from gmpy2 import *

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672
ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761
eh = int(bin(PKEY)[2:][-8:], 2) * 2**8
nh = int(bin(PKEY)[2:][:-8], 2) * 2**8
ch = int(bin(ENC)[2:], 2) * 2**8

for nl in trange(2**7):
    n = nh + nl * 2 + 1
    f = FactorDB(n)
    f.connect()
    fs = f.get_factor_list()
    if len(fs) == 2:
        p, q = fs[0], fs[1]
        if (
            len(bin(p)[2:]) == 128
            and len(bin(q)[2:]) == 128
            and isPrime(p)
            and isPrime(q)
        ):
            phi = (p - 1) * (q - 1)
            break

for el in trange(2**7):
    e = eh + el * 2 + 1
    if not isPrime(e):
        continue
    d = invert(e, phi)
    for cl in range(2**8):
        try:
            c = ch + cl
            m = pow(c, d, n)
            print('CCTF{'+long_to_bytes(m).decode()+'}')
        except:
            pass

risk

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import m, flag

def genPrime(m, nbit):
	assert m >= 2
	while True:
		a = getRandomNBitInteger(nbit // m)
		r = getRandomNBitInteger(m ** 2 - m + 2)
		p = a ** m + r
		if isPrime(p):
			return (p, r)

def genkey(m, nbit):
	p, r = genPrime(m, nbit // 2)
	q, s = genPrime(m, nbit // 2)
	n = p * q
	e = r * s
	return (e, n)

def encrypt(msg, pkey):
	e, n = pkey
	m = bytes_to_long(msg)
	c = pow(m, e, n)
	return c

pkey = genkey(m, 2048)
enc = encrypt(flag, pkey)

print(f'pkey = {pkey}')
print(f'enc = {enc}')

'''
pkey = (150953688, 373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983)
enc = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883
'''

题目有一个未知的$m$，可以根据$e$的生成和位数来大致得到，先看看已知：

$$\begin{cases}p=a_1^m+r\\ q=a_2^m+s\\ e=rs \end{cases}$$

我们知道$e$的值，其二进制位数为$28$，发现r = getRandomNBitInteger(m ** 2 - m + 2)，$r$的数量级应该和$14$相近，此时$m=4$时符合取值。也就得到：

$$\begin{cases}p=a_1^4+r\\ q=a_2^4+s\\ e=rs \end{cases}$$ $$n=pq=(a^4_1+r)(a^4_2+s)=a_1^4a_2^4+sa_1^4+ra_2^4+rs$$

已知$m$之后得到$a$的位数应该为$256$，$n$展开的多项式首项远大于后三项，所以直接对其开四次方，就可以得到$a_1a_2$乘积。

还要想办法求出中间两项，就可以直接得到$a_1,a_2$了，这里已知：

$$sa_1^4+ra_2^4 = n -a_1^4a_2^4 - rs$$

平方化简后可以构造：

$$sa_1^4\times ra_2^4 = rs(a_1^4a_2^4)$$

可以用韦达定理构造解得两项：

$$sa_1^4-ra_2^4 = \sqrt{(sa_1^4+ra_2^4)^2-4sa_1^4 ra_2^4}$$

得到$p,q$之后发现解RSA时出现$e,phi$不互素，且公因子较大不好直接求解，由于这题$p,q$位数较大，尝试将模数设置在$p$或$q$内，发现$q$时还存在一个$72$的公因子，可以使用有限域开方得到flag：

from Crypto.Util.number import *
from gmpy2 import *
from tqdm import *

e, n = (
    150953688,
    373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983,
)
c = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883


a1a2 = iroot(n, 4)[0]
t1addt2 = n - e - a1a2**4
t1t2 = e * a1a2**4
delta = t1addt2**2 - 4 * t1t2
t1 = (t1addt2 + iroot(delta, 2)[0]) // 2
t2 = (t1addt2 - iroot(delta, 2)[0]) // 2
a1 = gcd(a1a2, t1)
a2 = gcd(a1a2, t2)

for r in range(1, 2**14):
    if e % r == 0:
        s = e // r
        if (a1**4 + r) * (a2**4 + s) == n:
            break

p = a1**4 + r
q = a2**4 + s

phi = q - 1
e = e // 72
d = invert(e, phi)
mb = pow(c,d,q)
PR.<x> = Zmod(q)[]
f = x ^ 72 - mb
res = f.roots()
for i in res:
    try:
        print(long_to_bytes(int(i[0])).decode())
    except:
        pass

也可以用AMM：

import random
import time
from tqdm import tqdm
from Crypto.Util.number import *
# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def onemod(p,r): 
    t=random.randint(2,p)
    while pow(t,(p-1)//r,p)==1: 
         t=random.randint(2,p)
    return pow(t,(p-1)//r,p) 
 
def solution(p,root,e):  
    while True:
        g=onemod(p,e) 
        may=[] 
        for i in tqdm(range(e)): 
            may.append(root*pow(g,i,p)%p)
        if len(may) == len(set(may)):
            return may


def solve_in_subset(ep,p):
    cp = int(pow(c,inverse(int(e//ep),p-1),p))
    com_factors = []
    while GCD(ep,p-1) !=1:
        com_factors.append(GCD(ep,p-1))
        ep //= GCD(ep,p-1)
    com_factors.sort()

    cps = [cp]
    for factor in com_factors:
        mps = []
        for cp in cps:
            mp = AMM(cp, factor, p)
            mps += solution(p,mp,factor)
        cps = mps
    for each in cps:
        assert pow(each,e,p)==c%p
    return cps

p = 24854995563762799317055160315647073592768859410925406616067526817964296709994775588158311030813096922905657553370793515214591086698010302872311633588541111630338981703494212247996116660819640489213219705595382514374022123356637290058228183400682431815794876393612877273757515867990847040787313812864434536969
q = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675938807
e = 150953688
c = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883

ep = 10728
eq = 72
m_p = solve_in_subset(ep,p)
m_q = solve_in_subset(eq,q)

start = time.time()
print('Start CRT...')
for mpp in m_p:
    for mqq in m_q:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if solution < 2^800 :   # Always the bit_length of flag is less than 800
            print(long_to_bytes(solution))

end = time.time()
print("Finished in {} seconds.".format(end - start))