2023-ASISCTF-finals-wp-crypto

期末结束了！找点这段时间的题目做着玩。一共做出三个题目，另外两个不太会。

larisa

题目：

#!/usr/bin/env sage

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

def next_prime(r):
	while True:
		if isPrime(r):
			return r
		r += 1

def keygen(nbit):
	p = getPrime(nbit // 2)
	P, Q = [next_prime(p * getPrime(nbit // 2 - 10)) for _ in '01']
	n, K = P * Q, 2 ** (nbit >> 1)
	u, y = getRandomRange(1, n), getRandomRange(1, K)
	v = - (p + u * y) % n

	pkey = (u, v, n)
	skey = (y, P, Q)

	return pkey, skey

def encrypt(msg, pkey):
	u, v, n = pkey
	m = bytes_to_long(msg)
	assert m < n
	m0 = (u*m - v) % n
	while True:
		if isPrime(u + v):
			break
		else:
			u += 1
	e = u + v
	c = pow(m0, e, n)
	return c

nbit = 1024
pkey, skey = keygen(nbit)
u, v, n = pkey
c = encrypt(flag, pkey)

print(f'u = {u}')
print(f'v = {v}')
print(f'n = {n}')
print(f'c = {c}')

output：

u = 1462429177173255359388007765931796537885368646963625242711326952977985471932962383861842635724040143033586225507124897993946275538644782337485276659791768803892242293535522679957964876776825548307042572518152706215000123872096447939862588392736653305289270336986724756913886373602016050815040147667630379593859685646307913471020561969933852495456652645591262189417744078633139731004839760821762709078987432999550663454348821414654652257866073987807333618308663409376712742627162896125313056171829232263020741802783450992451834392620606043876037571745527804406103083287186596413204262417693475997360716169601004
v = 3361480002432693752626969088049143371033687796839032797315025143270946165139685061767026950394284498430926616845318237749712235930625309923903553850166793512181385788796869552215035455995370731816925378753732950039662516557875218374075823193808692392905081204067496016151667029418998917540743277631790419809752354652686500452367372802836483170592925224959479584778030250914074383997961924181706306681930041686426001864642557173165132110893305941080323382987813126090590272821376238345672517574935462126595211630982601294558596563972548400634497302430346025087052735168147932593694561898028225523940866874133379
n = 4008883280270490147018156798752367239459738170301430156348460445088206527048348763760917689680659443318901951360516237262067529304338022837630483645196033621304254000080347982506422415455884933061116059048068199094286198189562171954474774550333796393036361152513608385296841124457358944339309759412021626022854509621495881349117414093445491445654319715891479654096144019797840785614103437600093538599616479514552612464205903106999476721076731416925688036797972413175747167321276835717505959961674004440955460813234396658192578904514644322909786797887720838286121169342271751904104529587650648676532260230880251
c = 3309629508959584128230612074347190739927545664904299989648238914737928604135368325911619522168319646327710121629807700297133099757696348608872841783442909500945895046635610910032194240479153787968351434814626345330003107353783812257020006242435243345046344898591276950746249307045935633972732008301954536072882886730280063790321460574169136949746594095419049316818205661247488681646844441794828909897999773387001878462330994053758731317170118624021445627807773860715311680550099039292463923535627372276120134300337541349809506039721311255832543793638212911911226396687521214715073293308087345418705502341630822

题目的参数生成看上去有点复杂，但梳理下来信息其实也不多。

首先是：

$$P = pr_1 + \delta_1$$ $$Q = pr_2 + \delta_2$$ $$n = PQ$$

其中，p是512bit的素数，r1,r2是502bit的素数，delta1,delta2是nextprime带来的小偏移量。

然后选择(1,n)的随机数u，和(1,2^512)的随机数y，计算：

$$v = -(p+uy) \quad(mod\;n)$$

然后返回公钥对和私钥对：

$$pk：(u,v,n)$$ $$sk = (y,P,Q)$$

以上就是参数的生成过程，至于加密过程是这样的：

$$c = (um-v)^{u+v+\delta} \quad(mod\;n)$$

其中delta是保证u+v为素数的偏移量。

了解完全部过程后，题目提供给我们公钥u、v、n和c，要我们求解出明文。而很显然，如果能获得n的分解P，Q的话其实解密过程并没有难度，所以关键还是在于如何分解n。为了达到分解n的目的，题目中主要有三个信息可用：

• 生成P，Q时均使用了一个共同素数p

• 各个参数的数量级有区别，可以认为512bit及以下的数字是较小的

• $$v = -(p+uy) \quad(mod\;n)$$

结合以上三个信息，就可以发现由于p，y两个量都较小，所以可以把p，y看成未知数，用上式构造一个可以二元copper的多项式：

$$v + p + uy \equiv 0 \quad(mod\;n)$$

相较于模数n的2000多bit来说这个界肯定足够，所以也很容易就能copper出p和y的值。有了p过后，回顾P，Q的生成过程：

$$P = pr_1 + \delta_1$$ $$Q = pr_2 + \delta_2$$

求出任意一组r，delta都可以得到n的分解。而r为502bit，是可以copper的小量，delta是可以直接爆破的小量。所以就爆破delta去copper得到r，从而得到n的分解，然后就可以解密了。

exp：

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

u = 1462429177173255359388007765931796537885368646963625242711326952977985471932962383861842635724040143033586225507124897993946275538644782337485276659791768803892242293535522679957964876776825548307042572518152706215000123872096447939862588392736653305289270336986724756913886373602016050815040147667630379593859685646307913471020561969933852495456652645591262189417744078633139731004839760821762709078987432999550663454348821414654652257866073987807333618308663409376712742627162896125313056171829232263020741802783450992451834392620606043876037571745527804406103083287186596413204262417693475997360716169601004
v = 3361480002432693752626969088049143371033687796839032797315025143270946165139685061767026950394284498430926616845318237749712235930625309923903553850166793512181385788796869552215035455995370731816925378753732950039662516557875218374075823193808692392905081204067496016151667029418998917540743277631790419809752354652686500452367372802836483170592925224959479584778030250914074383997961924181706306681930041686426001864642557173165132110893305941080323382987813126090590272821376238345672517574935462126595211630982601294558596563972548400634497302430346025087052735168147932593694561898028225523940866874133379
n = 4008883280270490147018156798752367239459738170301430156348460445088206527048348763760917689680659443318901951360516237262067529304338022837630483645196033621304254000080347982506422415455884933061116059048068199094286198189562171954474774550333796393036361152513608385296841124457358944339309759412021626022854509621495881349117414093445491445654319715891479654096144019797840785614103437600093538599616479514552612464205903106999476721076731416925688036797972413175747167321276835717505959961674004440955460813234396658192578904514644322909786797887720838286121169342271751904104529587650648676532260230880251
c = 3309629508959584128230612074347190739927545664904299989648238914737928604135368325911619522168319646327710121629807700297133099757696348608872841783442909500945895046635610910032194240479153787968351434814626345330003107353783812257020006242435243345046344898591276950746249307045935633972732008301954536072882886730280063790321460574169136949746594095419049316818205661247488681646844441794828909897999773387001878462330994053758731317170118624021445627807773860715311680550099039292463923535627372276120134300337541349809506039721311255832543793638212911911226396687521214715073293308087345418705502341630822

#coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

#part1 get p,y
PR.<p,y>=PolynomialRing(Zmod(n))
f= v + p + u*y
res = small_roots(f,bounds=(2^512,2^512),m=3,d=2)
p,y = res[0]

#part2 get r1
if(0):
    for delta1 in trange(1,2000):
        PR.<r1>=PolynomialRing(Zmod(n))
        f = p*r1 + delta1
        f = f.monic()
        res = f.small_roots(X = 2^502,beta = 0.5)
        if(res != []):
            print(delta1)
            print(res)
            break

#part3 get flag
r1 = 9982434694399603508133337302525981381172077094594547911881389765404140839294990193381283506463508822263498107585942085834150918110565475926894148950133
delta1 = 360
P = int(p*r1+delta1)
Q = n // P
phi = (P-1)*(Q-1)
e = u + v
while True:
    if isPrime(int(e)):
        break
    else:
        e += 1
d = inverse(e,phi)
c1 = pow(c,d,n)
flag = (c1+v)*inverse(u,n) % n
print(long_to_bytes(int(flag)))

#ASIS{__fpLLL__4pPL1cA7!0n5_iN_RSA!!!}

flag中提到fpLLL的话应该只是说也可以用Lattice去解p和y，那样做更简单一点。

tricare

题目：

#!/usr/bin/env sage

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

def encrypt(m, seed, precision):
	r = (20 * sin(m) ** 3 * cos(m) ** 3 - 6 * sin(m) * cos(m) * (sin(m) ** 4 + cos(m) ** 4)).n(precision)
	s = (1 - cos(6 * m) - seed * r).n(precision)
	t = (sin(6 * m) + seed * (cos(6 * m) + 1)).n(precision)
	u = (s / t).n(precision)
	return u

def shift(x, precision):
	u, v = (x**3 - 3*x).n(precision), (1 - 3*x**2).n(precision)
	w = (u / v).n(precision)
	return w

precision = 1363
m = bytes_to_long(flag)
t = encrypt(m, seed, precision)
s = shift(t, precision)

print(f's = {s}')

output：

s = 4.4061969948574999706381252707706339596595993989993753525157058049520620878450909599070901658740035834714697099225869545917495720287359577329698453888804452908560270310064490162218842432355207070730163222140239639986509963808182579875037244043013930898502696038143722917574699793054569551851806943599434585896730793457949140792425837528999663586881638690611528789842156130245622849852139290458664441887058153106

题目的加密过程一眼看上去让人害怕，整理一下大概是：

• 设置精度为1363
• 将flag先做如下加密(encrypt)，并返回u：

$$r = 20sin^3mcos^3m-6sinmcosm(sin^4m+cos^4m)$$ $$s = 1-cos6m-seed*r$$ $$t = sin6m + seed(cos6m+1)$$ $$u = \frac{s}{t}$$

• 再对u做如下移位(shift)，并返回s作为最终密文：

$$s = \frac{u^3-3u}{1-3u^2}$$

任务就是用s求解出明文。

首先，直觉上来说这个seed应该就是可以消掉的，因为他的确没什么办法可以求。事实上也确实如此，自己生成一些数据就可以发现seed对最终s值的影响几乎完全可以忽略，那么就直接把seed取成0来简化求解，s和t就分别简化为：

$$s = 1-cos6m$$ $$t = sin6m$$

那么用二倍角公式，显然u就变成：

$$u = \frac{s}{t} = \frac{1-cos6m}{sin6m} = \frac{2sin^23m}{2sin3mcos3m} = tan3m$$

然后再代入s：

$$s = \frac{tan^33m - 3tan3m}{1-3tan^23m}$$

这其实就是三倍角公式，所以有：

$$s = -tan9m$$

注意以上的这些其实并不是等式，因为存在精度问题导致的误差。也就是说现在就变成了已知tan9m的高精度值s，要求解出m。这个问题其实就是小改了一下2023 imaginaryCTF的Tan那道题目，不过就实现来说的话，这个题会麻烦一些。

首先是很容易想到的求解思路，因为tan以pi为周期，所以就有：

$$s = -tan(9m+k\pi)$$

所以就有：

$$arctan(-s) = 9m + k\pi$$

有这样一个式子容易想到造个格来求解。但是格需要的是等式，因此这个时候我们就要把误差加上：

$$arctan(-s) = 9m + k\pi + \delta$$

然后造个格子如下：

$$\left(\begin{matrix} arctan(-s)& 0&0\\ \pi& 1&0\\ 9& 0&1\\ \end{matrix} \right)$$

这个格有线性关系：

$$(1,k,m) \left(\begin{matrix} arctan(-s)& 0&0\\ \pi& 1&0\\ 9& 0&1\\ \end{matrix} \right) = (\delta,k,m)$$

而delta是精度1363带来的误差，因此他一定小于2^-1363，这导致他与整数k和m的差距极大，因此需要乘上大系数2^1363来配平，从而进行规约。

然而这样做我无论如何都规约不出结果，即使再微调系数也没有什么效益。卡了很久后突然发现应该是flag太长了，导致短向量里的m会较显著的大于这个格子的高斯启发式，所以要想办法利用前缀ASIS{和后缀}来进一步缩短向量长度，这就需要爆破一下flag长度，并且小改一下格中的数字。

事实上也的确这样，去除了前后缀的flag仍然有足足79个字符，在这个精度下算是相当极限的了。我自己测试了一下82个字符这个精度就不够了，出题人应该也是有意为之。

exp：

from Crypto.Util.number import *

precision = 1363

flag_len = 6 + 79 #guess
prefix = bytes_to_long(b"ASIS{") * 256^(flag_len-5)
suffix = bytes_to_long(b"}")

#s = -tan(9m)
#9m = arctan(-s) + 2kpi
s = 4.4061969948574999706381252707706339596595993989993753525157058049520620878450909599070901658740035834714697099225869545917495720287359577329698453888804452908560270310064490162218842432355207070730163222140239639986509963808182579875037244043013930898502696038143722917574699793054569551851806943599434585896730793457949140792425837528999663586881638690611528789842156130245622849852139290458664441887058153106
approx_9m = arctan(-s)

T = 2**(precision)
L = Matrix(QQ,3,3,[[(approx_9m-9*prefix-9*suffix)*T,0,0],
                [(pi.n(precision))*T,1,0],
                [9*T,0,1]])

res = L.LLL()
flag = long_to_bytes(abs(int(res[0][-1])) // 2^8)
print(flag)

#ASIS{tr190n0M3tr1c_fuNct10ns_pr0dUc3_r3suLts_1Z_h4rd_t0_r3v3rsE_1nt0_1ts_Or1g!n4l!!?}

m7p

题目：

#!/usr/bin/env python3

import os
from hashlib import *
from binascii import *
from Crypto.Cipher import AES
from Crypto.Util.number import *
from flag import flag

def next_prime(n):
	while True:
		if isPrime(n):
			return n
		n += 1

def find(s, ch):
	return [i for i, ltr in enumerate(ch) if ltr == s]

def worth(c, msg):
	assert len(c) == 1
	w = 0
	if c in msg:
		a = find(c, msg)
		w += sum([(_ + 1)**_ - _ for _ in a])
	return w

def xor(mm, ym):
	xm = []
	for i in range(len(mm)):
		xm.append(mm[i] ^ ym[i])
	return bytes(xm)

def taft(key, otp):
	assert len(key) == len(otp)
	T = []
	for _ in range(len(key)):
		__ = xor(key, otp)
		T.append(hexlify(__))
		otp = sha1(otp).hexdigest().encode()
	return T

def gaz(T):
	G = []
	for t in T:
		R = []
		for c in range(16):
			R.append(worth(hex(c)[2:], t.decode()))
		p = next_prime(sum(R))
		a = getPrime(p.bit_length() >> 3)
		R = [r * a % p for r in R]
		G.append(R)
	return G

def lili(gz, s):
	i, L = 0, []
	for g in gz:
		s_i = bin(bytes_to_long(s[2*i:2*i + 2]))[2:].zfill(16)
		L.append(sum([g[_] * int(s_i[_]) for _ in range(16)]))
		i += 1
	return L

def encrypt(msg, key):
	cipher = AES.new(key, AES.MODE_GCM)
	enc, tag = cipher.encrypt_and_digest(msg)
	return (enc, cipher.nonce, tag)

some = os.urandom(40)
good = os.urandom(40)
keys = os.urandom(80)

T = taft(some, good)
G = gaz(T)
L = lili(G, keys)

mask = xor(flag, sha512(keys).digest()[:len(flag)])
enc = encrypt(mask, sha256(some).digest())

print(f'G = {G}')
print(f'L = {L}')
print("c = ", *enc, sep = "")

output太长就不放在这里，github上有完整的数据(包括剩下题目的源码)：

ctf-archives/ctfs/ASIS/2023/Finals/crypto at main · sajjadium/ctf-archives (github.com)

这个题函数也不算少，就直接从加密流程说起吧。首先题目生成三个随机字节串：

some = os.urandom(40)
good = os.urandom(40)
keys = os.urandom(80)

然后题目最后用以下方式加密flag得到密文：

mask = xor(flag, sha512(keys).digest()[:len(flag)])
enc = encrypt(mask, sha256(some).digest())

其中encrypt是AES的GCM模式加密：

def encrypt(msg, key):
	cipher = AES.new(key, AES.MODE_GCM)
	enc, tag = cipher.encrypt_and_digest(msg)
	return (enc, cipher.nonce, tag)

虽然用GCM在这里确实显得有点刻意，不过有一点是毋庸置疑的：如果能求出some、good、keys这三个随机字节串的话，就可以很轻松的解密密文得到flag。所以现在就是要想有没有办法从题目给的信息中直接求出这几个随机串。

而题目给的相关信息主要就有以下一些内容：

T = taft(some, good)
G = gaz(T)
L = lili(G, keys)

print(f'G = {G}')
print(f'L = {L}')
print("c = ", *enc, sep = "")

那么就一个一个看吧。

T = taft(some, good)

首先，taft函数的功能很简单，他循环做以下操作40次得到40个ci，并放到列表T中返回T：

$$c_i = some \oplus otp$$ $$otp = sha1(otp)$$

这里有一个小细节需要注意，就是otp的初始值是随机字节串，每个字节有256种可能；但是从第一次以后，otp是sha1后得到的20个字节进行16进制编码得到的40个十六进制字符。也就是说otp在这之后仅由16进制字符组成，每个字节只有16种可能了。

而后续中我们可以求出T，那么问题就变成如何由T恢复some和good。这就要用到刚才说的那个细节了，我们知道多组some列表与随机十六进制串的异或结果，而我们现在分析这些异或结果的相同位置的字节，记为ti，就有：

$$t_i = some_i \oplus hex_i$$

而对这些相同位置的十六进制字节来说，与他们异或的就都是some中的同一字节。而其实一共只有16个可能的字节，能够让ti与他们异或后得到一个十六进制字节。所以，我们就可以通过多组异或求交集的方式，逐个确定some里面的每个字符。

G = gaz(T)

这应该是整个题目最难处理的一步，所以首先搬一下它的源码：

def gaz(T):
	G = []
	for t in T:
		R = []
		for c in range(16):
			R.append(worth(hex(c)[2:], t.decode()))
		p = next_prime(sum(R))
		a = getPrime(p.bit_length() >> 3)
		R = [r * a % p for r in R]
		G.append(R)
	return G

首先，worth(c, msg)函数的功能是：找到十六进制字符c在msg中的所有下标i，并且按如下方式求和，并把这个和作为worth的返回值：

$$\sum(i+1)^i - i$$

那么，gaz(T)函数的功能就是：

• 循环列表T的长度次

• 每一次循环开始时，初始化一个空列表R，并取出T中的一个十六进制串t

• 对从0到f的每个十六进制字符k，逐个求worth(k,t)，并将结果放到列表R中

• 对R中的16个求和结果求sum，并取nextprime(sum)作为p
• 随机生成一个素数a，其比特长度为p.bit_length() >> 3
• 对R中的每一个值r，计算 $ra (mod\;p)$ ，并用这些值重新生成R
• 将R放到G中
• 如此循环以上过程T的长度次后，返回G

这个过程一定要好好理一下，不然后面会很乱。总而言之我大概总结出了以下有用信息：

• p是一个可以计算出的定值，这是因为R的求和结果是确定的，因为R的sum其实就是从0-79所有下标求worth的和
• a的比特长度为62(得出上一个结论很自然就得到这个结论)

除此之外，还可以有一些额外信息，比如我们对0-79，生成worth对应的那个数列：

$$(i+1)^i - i$$

可以发现，这个数列是超递增的，并且每个数字的比特长度是：

$$1,1,3,6,10,13,17,21,26,30,35,40,45,50,55,60,66,71,77,83,88,94,100,106,112,118,124,130,137,143,149,155,162,168,175,181,188,195,201,208,215,222,228,235,242,249,256,263,270,277,284,291,298,306,313,320,327,334,342,349,356,364,371,378,386,393,401,408,416,423,431,439,446,454,461,469,477,484,492,500$$

而a比特长度一共也就62，而这些数字中超过(500-62)比特长度的一共也就九个，这其实说明一个重要信息：

• 列表R中一定存在ra，使得ra<p

这个信息告诉我们，对于G中的每一个列表R，其内部都一定存在这样的ra：其本身就小于p。也就是说对于这样的ra来说，模p这个操作没有起作用，所以我们可以尝试获得所有ra的因式分解，如果某一项存在一个62bit的素数因子，那么这个因子就很可能是正确的a。这一步的实施方法也很多，可以factordb查表，也可以直接两两求gcd并消去小因子(因为小于p的ra最多可以有七项)。

而得到a过后，我们要想清楚我们的目标：要通过列表G求出列表T。因此问题到现在转化成对G中的每个列表R：

• 已知a
• 已知R中每个值是 $r_ia (mod\;p)$ ，其中ri是0-f每个十六进制字符在T中对应字符串t里的worth和
• 求出对应字符串t

而因为已经求出了a，所以也就知道ri模p下的值，而我们把刚才worth对应的数列看作一个背包，那么现在问题其实可以看做是一个模p下的01背包问题。就比如，对于十六进制字符”0”，已知其对应的worth和是r0，而这个和其实就是在worth数列中，选择其中一些项求和后模p的值。

因此理论上来说，造一个背包格进行规约，其中不为0的项就是0在原字符串t中的对应下标，以此类推就可以得到所有十六进制字符的下标，从而恢复原字符串t。对G中的每一个R都如此操作，就能得到T列表了。

当然，实际操作的时候会有一些小问题，比如worth数列的第一个数字和第二个数字都是1，所以没有好办法确定他到底是哪一个十六进制字符。但这也不是个问题，因为也只需要在最后AES解密的时候爆破一个字符就行。

如此一来，我们实现了一个目标：由G恢复T

L = lili(G, keys)

这一步就真的很简单，就是一个01背包而已，很容易就能恢复keys。(但是有些地方需要微调一下，因为G中各元素可能线性相关)

总结

以上就是我对这个题目目前的全部思考，不知道预期是不是背包做的。

exp：

from M7P_output import *
from Crypto.Util.number import *
from tqdm import *
from Crypto.Cipher import AES
from hashlib import *

#part1 get keys
def knapsack1(knap,sum):
    L = matrix(ZZ,len(knap)+1,len(knap)+1)
    for i in range(len(knap)):
        L[i,i] = 1
        L[i,-1] = knap[i]
    L[-1,-1] = -sum
    res = L.LLL()
    if(res[1][0] != 0 and res[1][0] != 1):
        return res[0][:-1]
    else:
        ind = 0
        for i in range(len(res[0])):
            if(res[0][i] == 1):
                ind = i
                break
        temp = list(res[1][:-1])
        temp[ind] = 1           
        return temp

if(1):
    keys = b""
    for i in range(len(G)):
        temp = knapsack1(G[i],L[i])
        temp1 = ""
        for j in temp:
            temp1 += str(j)
        keys += long_to_bytes(int(temp1,2)).zfill(2)


#part2 get T
def genknap():
    knap = [(_ + 1)**_ - _ for _ in range(80)][1:]
    p = next_prime(sum(knap))
    return knap,p

def knapsack2(knap,sum):
    L = matrix(ZZ,len(knap)+2,len(knap)+2)
    for i in range(len(knap)):
        L[i,i] = 1
        L[i,-1] = knap[i]
    L[-2,-2] = 1
    L[-2,-1] = -sum
    L[-1,-1] = p
    res = L.LLL()[1][:-2]
    return res

def get_a(Ri):
    def clear_small_factors(num):
        temp = num
        for i in range(2,10000):
            while(temp % i == 0):
                temp //= i
        return temp
    
    for i in range(len(Ri)):
        for j in range(i+1,len(Ri)):
            temp = int(clear_small_factors(GCD(Ri[i],Ri[j])))
            if(isPrime(temp) and temp.bit_length() == 62):
                return temp

if(0):
    knap,p = genknap()
    T = []
    for Ri in tqdm(G):
        ai = get_a(Ri)
        #print(ai)
        if(1):
            this_str = ["*" for i in range(80)]
            count_hex = 0
            for i in Ri:
                sumi = inverse(ai,p)*i % p
                index = knapsack2(knap,sumi)
                for j in range(len(index)):
                    if(index[j] != 0):
                        if(this_str[j+1] != "*"):
                            this_str[j+1] = "!" + this_str[j+1] + hex(count_hex)[2:] + "!"
                        else:
                            this_str[j+1] = hex(count_hex)[2:]
                #print(this_str)
                count_hex += 1
            T.append("".join(this_str))
            print(T)

#part3 get some
def dec_taft(T):
	table = "0123456789abcdef"

	temp = ["*" for i in range(len(T))]
	for i in range(len(T)):
		if(T[i][1] == "!"):
			temp[i] = long_to_bytes(int(T[i][5:],16))
		else:
			temp[i] = long_to_bytes(int(T[i][2:],16))
	temp = temp[1:]

	some = ""
	possible_list = []
	for i in range(40-1):
		possible_set = set()
		for length in range(len(temp)):
			this_possible_set = set()
			tempchr = temp[length][i]
			for j in range(256):
				if(chr(tempchr ^^ j) in table):
					this_possible_set.add(j)
			if(length == 0):
				possible_set = this_possible_set
			else:
				possible_set = possible_set.intersection(this_possible_set)
		possible_list.append(possible_set)
	
	return possible_list

if(0):	
    T = ['*!4c!de96c34bb1561914c71ae71765d734ee29d753ce794f59101646152a8bce350c5cacd70283ea64', '*fe32b81f6daef130496fb6ff2b5be34ee93b8cb7976f8c0240c68842c6faacc90d84a701cb0f391', '*!18!e125d6a7d1eb465299aa6ef6b5ed67b2c1bccd2b70ffc076066dd77f6ca69cc2d349231be7a1c3', '*!26!e7248ca6d4eb4751c5aa34f3bcbc3abb91b89a7a72f8c4225438872b38f69fc6891a2649e0a3cc', '*2b77985f6d4e84f05c3ab31a8e6ba67b296bbcd2f26acc220573684223af7c8c6d81b704eb1a0c3', '*!25!e77c8ca2daeb410c93fe31f4e2ea3ab896e99d7922aa92270339d82333f199c6dc1a701ebbf4c0', '*7b229d7f2d0ee4250c7aa31a1e2e860ba90b4912870f19e77566d822938f5cc97d34d731eb5a5c1', '*!57!b32982a5d6bc420dc7fe63a0b0e635ef9ded907874a99070023680796ca49f95d818714db7f4cc', '*7b07c86f1d6ea415093a26fa2bcbd33ea94efcc2822f996205639807838a7cbc18c1f244db4a396', '*7b22c87aa83e51702c5ad62f1e0bb32b39cbf9c2a74f090700d37d82e3bf798ca89117349b6a797', '*7ee2ed0a483e84557c3f931f1bcef3befc1e99d7c78ae9e235037d02d38a7cb96de1e744be0abcc', '*!27!b52ad7f587e54e0096fb60f1bdbe32b392eaca7f72abc220503ad72e6ea6cfc6d31e234ee1abcc', '*2b32e82aa87bb4f0698ad34f3b0e935e8c3e9c82b23a990230c6fd82f6fa49fc2891e7048e7f4c7', '**ef788da083ec420293a962a3e2ba34b3c1b5917f26fc932a5037802e68a2cdc28811244db2f1cc', '*2ef7e85a4d1b8400399ac65f4bded34be92b99f2823aa9e220c3bd52e32f69f97d24e731eb2f497', '**b42b83abd1b8430794fe35f2b4be33e894b8c87b78f89526573e87296fa5ca92894c2648e1a0c3', '**b42480f080ee4252c2ad64f6bcbd30e996e8997922fc902a576fd42d6eabcbc1da1f794db2a791', '*7ee2b87f7d3ee1005c3ff64a9e0bd3bef95bbca7971f997770137d62d3df099cadf1c794eb7abc7', '*0b07cd1a680bb4f5696ff60f5bcec65b39cb9cb7b72f891250468d12e6fa1cb928b1c2447e2f3c4', '**e279d7a2d3ed420c99ad66f6b2bd30bbc1bbc87976ad97245036d82e3fa79bc5d31c704ee5a3c5', '*!77!b52d81f7daea400298f831f3e5e73bbc94efcd2b78fe9f210439d52d38f5c8c3da4e7919e0a197','**e128d0a384ec415598ad32a2b7bd65b293ba907e22fac3230137d92239a1cc918b107948b6abc6','**b2788daa81eb1202c7f867a5e7be61b290e9cb2d24aa9773533b857b3da39fc2da4a794ce5f697','*!25!b52cd4f5dbea4f06c7fe66f4b0eb65bc97e89b7723fec277066ad07c3ba199c4884e701ee2a392','*!26!b52986f0d4e41701c3f831a1e2ea66b8c6b8cb7c77f194770d3b832a32a49ec28b19724ae1a4c7']
    possible_list = dec_taft(T)
    some = b"*"
    for i in possible_list:
        if(len(i) == 1):
            some += long_to_bytes(list(i)[0])
        else:
            some += b"*"
    print(some)


#part4 get flag
c = b"\x8d\x04>\xeb4S\xf3\xea\x9c\xc1\xec3\x07\xfc'\xf9\xd7\xfcQ\\\xcf&\xc6N\xa1\xf1\xa4\x87\xee\xf6\xe3\x0c\xfbF,yyq\xfdK\x95\x94\x152\x9c\xcbK\x97\n\xe2#"
nonce = b'B\xe3@\xee\x1ex\xee\xca \x14\x1bPT\xee\x92\x9c'
tag = b'\xeb\xacdC\x85=\x17^}\x80/N\xcc\xc4F\xa3'

def xor(mm, ym):
	xm = []
	for i in range(len(mm)):
		xm.append(mm[i] ^^ ym[i])
	return bytes(xm)

def AES_dec(c,nonce,tag,key):
    try:
        cipher = AES.new(key, AES.MODE_GCM,nonce)
        res = cipher.decrypt_and_verify(c,tag)
        return res
    except:
        pass

if(1):
    for i in range(256):
        for j in {169, 250, 253, 174}:
            temp = some
            temp = long_to_bytes(i) + temp[1:]
            temp = temp[:31] + long_to_bytes(j) + temp[32:]
            mask = AES_dec(c,nonce,tag,sha256(temp).digest())
            if(mask != None):
                flag = xor(mask, sha512(keys).digest()[:len(mask)])
                print(flag)
       
#ASIS{h0W_dO_yUo_5oLvE_tH!s_m1X3D_5eMi_H4rD_T4Sk!!?}