LCG未知a,b求seed
题目
from Crypto.Util.number import getPrime, inverse
from secret import seed, flag
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()
assert flag == '0xGame{' + MD5(seed) + '}'
assert seed.bit_length() == 510
class LuanGao:
def __init__(self, bits:int, seed:int):
self.bits = bits
self.m = getPrime(self.bits)
self.a = getPrime(self.bits // 2)
self.cur = (self.a * seed) % self.m
def extract(self):
ret = self.cur
b = getPrime(self.bits // 4)
self.cur = ( self.a * self.cur + b ) % self.m
return ret
C = LuanGao(512, seed)
Cs = [C.extract() for _ in range(5)]
print(f'Cs = {Cs}')
print(f'C.m = {C.m}')
'''
Cs = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
C.m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
'''
exp
# 0xGame 2024
# LLL-II
from Crypto.Util.number import *
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()
m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753
c = [11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
ge = [
[m,0,0,0,0,0],
[0,m,0,0,0,0],
[0,0,m,0,0,0],
[0,0,0,m,0,0],
[c[0],c[1],c[2],c[3],1,0],
[c[1],c[2],c[3],c[4],0,1]]
Ge = Matrix(ZZ,ge)
L = Ge.LLL()
a = abs(L[0][-2])
seed = c[0]*inverse(a,m)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')
# '0xGame{2db84757dd4197f9b9441be25f35bfd5}'
# 2512273436977220996062855314655393786244910444920037228737234078954182704102442213664768806368325362960908940985195233026259876194811260795362098878115082LCG已知state高位求seed
题目
from Crypto.Util.number import *
from secret import seed,flag
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()
assert flag == '0xGame{' + MD5(seed) + '}'
assert seed.bit_length() == 256
class LCG:
def __init__(self,bits:int,seed:int):
self.m = getPrime(bits+1)
self.a = getPrime(bits)
self.b = getPrime(bits)
self.cur = ( self.a * seed + self.b ) % self.m
def extract(self):
ret=self.cur >> 115
self.cur = ( self.a * self.cur + self.b ) % self.m
return ret
lcg=LCG(bits=256,seed=seed)
out = []
for _ in range(20):
out.append(lcg.extract())
print(f'm = {lcg.m}')
print(f'a = {lcg.a}')
print(f'b = {lcg.b}')
print(f'out = {out}')
'''
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
out = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]
'''exp
# 0xGame 2024
# LLL-III
from Crypto.Util.number import *
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()
m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
c = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]
ge = [[0]*21 for i in range(21)]
for i in range(19):
ge[i][i] = m
ge[-2][-2],ge[-1][-1] = 1,1
ge[-2][0], ge[-1][0] = a,a*(c[0]<<115)+b-(c[1]<<115)
for i in range(1,19):
ge[-2][i]=a^(i+1)
ge[-1][i]=ge[-1][i-1]*a+a*(c[i]<<115)+b-(c[i+1]<<115)
Ge = Matrix(ZZ,ge)
Ge = Ge.LLL()
assert Ge[0][-1] == 1
state = abs(Ge[0][-2])+(c[0]<<115)
seed = pow(a,-1,m)*(state-b)%m
print(seed)
print('0xGame{' + MD5(seed) + '}')
# 101639613050544872292192629515273562035022699788445344858455157668840828973361
# '0xGame{459049e068d93f6d70f1ea0da705264a}'LWE问题
咕咕ing
AGCD问题
咕咕ing
HSSP问题
问题描述
有一个大整数$M$，行向量$\alpha \in \mathbb{Z} _M^n$和一个由$n$个行向量$x_i \in \mathbb{Z} _2^m$构成的矩阵$A_{n \times m}$
计算$h=\alpha A$
已知$M,h,n,m$，求$\alpha , A$
其中满足$M.bits = 2 \iota n^2 + n \cdot log\ n,\iota = 0.035$
求解
主要思路：寻找A的正交格（因为A未知，于是要从h去构造），然后计算正交格的右核空间，并规约即可得到A
寻找向量$u$使得$u,h$垂直
$$h \cdot u = \alpha Au = \sum_{i=1}^n\alpha_i(x_i \cdot u) = 0\ mod\ M$$
令向量$p_u$
$$p_u=Au=(x_1u,x_2u,\cdots,x_nu)$$
所以满足
$$\alpha p_u=0\ mod\ M$$
这表明$p_u$和$\alpha$在模M下相互垂直
当$p_u=0$时，即可认为$u$垂直于$A$的行向量$x_i$为基构成的格，即$u\in L_x^{\perp}$
由于$L_x$的维度是n，因此$L_x^{\perp}$的维度是$m-n$，也就是说找到$m-n$个线性无关的$u$就能复原$L_x^{\perp}$，再计算出与其正交的格即可找到$L_x$，由于$x_i \in \mathbb{Z} _2^m$是短向量，对$L_x$规约即可得到构成矩阵$A$的基
$$h\cdot u=\sum_{i=1}^mh_iu_i\ mod\ M$$
可以尝试构造格，由于$p_u=0$可知$p_u$是短向量，而$x_i$的元素是$0,1$，所以$u$也是短向量
$$(u_1,u_2,\cdots,u_m,-k) \begin{pmatrix} h_1& 0&\cdots& 0&1\\ h_2& 0&\cdots& 1&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ h_m& 1&\cdots& 0&0\\ M& 0&\cdots& 0&0\\ \end{pmatrix} =(0,u_m,\cdots,u_2,u_1)$$还有一种构造格的方法
$$h\cdot u=h_1u_1+\sum_{i=2}^mh_iu_i\ mod\ M$$
$$kM-\sum_{i=2}^mu_ih_ih_1^{-1}=u_1$$
$$(k,u_2,\cdots,u_m) \begin{pmatrix} M& 0&\cdots& 0&0\\ -h_2h_1^{-1}& 1&\cdots& 0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ -h_3h_1^{-1}& 0&\cdots& 1&0\\ -h_mh_1^{-1}& 0&\cdots& 0&1\\ \end{pmatrix} =(u_1,u_2,\cdots,u_m)$$对$L_x$规约无法恢复矩阵$A$，因为矩阵$A$是在基上的进一步线性组合，不一定是最短基，所以可以通过类似背包密码的方式将基转化为$2x_i-e,e=(1,\cdots,1)$，以此筛选出目标基(元素落在$\{0,1\}$)，因为非目标基(元素落在$\{-1,0,1\}$)在新格中会使得模变长，而在规约中被筛去。此算法对数据大小有要求$m\ge \frac{n^2}{2}$
于是进行如下的构造
$$B=\begin{pmatrix}-e\\2L_x\end{pmatrix}_{(n+1)\times m}$$
令$L_x,A$存在如下线性关系
$$UL_x=A$$
于是有
$$(e^T,U)_{n\times (n+1)}B=(2UL_x-e^Te)_{n\times m}=\begin{pmatrix} 2x_1-e\\\vdots\\2x_n-e \end{pmatrix}$$
所以最终对$B$规约后去除加入的$e$的影响，即可恢复出矩阵$A$
# HSSP
def checkMatrix(M, wl=[-1, 1]):
M = [list(i) for i in list(M)]
ml = list(set(flatten(M)))
return sorted(ml) == sorted(wl)
def hssp_solve(n,m,M,h):
ge1 = [[0]*m for _ in range(m)]
tmp = pow(h[0], -1, M)
for i in range(1,m):
ge1[i][0] = -h[i]*tmp
ge1[i][i] = 1
ge1[0][0] = M
Ge1 = Matrix(ZZ,ge1)
L1 = Ge1.BKZ()
Lx_orthogonal = Matrix(ZZ, L1[:m-n])
Lx = Lx_orthogonal.right_kernel(algorithm='pari').matrix()
e = Matrix(ZZ, [1] * m)
B = block_matrix([[-e], [2*Lx]])
L2 = B.BKZ()
assert checkMatrix(L2)
E = matrix(ZZ, [[1]*L2.ncols() for _ in range(L2.nrows())])
L2 = (L2 + E) / 2
assert set(L2[0]) == {0}
L2 = L2[1:]
space = Lx.row_space()
Lx2 = []
e = vector(ZZ, [1] * m)
for lx in L2:
if lx in space:
Lx2 += [lx]
continue
lx = e - lx
if lx in space:
Lx2 += [lx]
continue
return None
Lx = matrix(Zmod(M), Lx2)
vh = vector(Zmod(M), h)
va = Lx.solve_left(vh)
return Lx, va
n = ?
m = ?
M = ?
h = ?
A,a = hssp_solve(n,m,M,h)
for row in A:
ans = "".join(str(i) for i in row)
try:
print(long_to_bytes(int(ans,2)).decode())
except:
NoneAHSSP问题
问题描述
有模数$p$，行向量$\alpha_{1 \times n} \in \mathbb{Z} _p^n$，一个由$n$个行向量$x_i \in \mathbb{Z} _2^m$构成的矩阵$A_{n \times m}$和行向量$e_{1 \times m}\in \mathbb{Z} _p^m$，$s$
计算$h = \alpha A-se\ mod\ p$，已知$h,e,p$，求$s$
求解
主要思路还是利用正交格来求解，然后之后的步骤和HSSP是大致相同的
构造正交矩阵$M$，使得满足$hM=\alpha AM-seM\ mod\ p$
构造如下的格对其规约，即可得到正交格M
$$(M_1,M_2,\cdots,M_m,k_1,k_2) \left(\begin{array}{cc|cc} h_1& e_1& 1& 0&\cdots& 0&0\\ h_2& e_2& 0& 1&\cdots& 0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ h_m& e_m& 0& 0&\cdots& 0&1\\ \hline p& 0& 0& 0&\cdots& 0&0\\ 0& p& 0& 0&\cdots& 0&0\\ \end{array}\right) =(0,0,M_1,M_2,\cdots,M_m)$$再采用和HSSP同样的方法即可恢复出A
接下来再构造$eM=0\ mod\ p$，即可得到$hM=\alpha AM\ mod\ p$，然后就能解得$\alpha$，最终就能解出$s$
构造如下的格用来构造$M$，可能需要对第一列乘p进行配平
$$(M_1,M_2,\cdots,M_m,k_1) \left(\begin{array}{c|cc} e_1& 1& 0&\cdots& 0\\ e_2& 0& 1&\cdots& 0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ e_m& 0& 0&\cdots& 1\\ \hline p& 0& 0&\cdots& 0\\ \end{array}\right) =(0,M_1,M_2,\cdots,M_m)$$下面是自己搓的一个板子
from Crypto.Util.number import *
def ahssp(h:list, e:list, n:int, m:int, p:int):
tmp = block_matrix([[vector(h).column(), vector(e).column()]])
Ge = block_matrix([[tmp, identity_matrix(m)],[identity_matrix(2)*p,zero_matrix(2, m)]])
# Ge[:,:2] *= p
L = Ge.BKZ()
M = L[:m-n,2:]
A_ = M.right_kernel().matrix()
e_ = matrix(ZZ, [1] * m)
B = block_matrix([[-e_],[2*A_]])
L = B.BKZ()
assert set(flatten(list(map(list, L)))) == {-1,1}
E = matrix(ZZ, [[1]*L.ncols() for _ in range(L.nrows())])
L = (L + E) / 2
assert set(L[0]) == {0}
L = L[1:]
space = A_.row_space()
A = []
e_ = vector(ZZ, [1] * m)
for i in L:
if i in space:
A += [i]
continue
i = e_ - i
if i in space:
A += [i]
continue
return None
A = matrix(Zmod(p), A)
L = block_matrix(ZZ, [[vector(e).column(), matrix.identity(m)],[p, zero_matrix(1, m)]])
L[:, :1] *= p
L = L.LLL()
res = []
for row in L:
if row[0] == 0:
res.append(row[1:])
M = matrix(res)
assert all(i == 0 for i in vector(e) * M.T % p)
a = (A*M.T).solve_left(vector(h)*M.T)
s = matrix(e).solve_left(a*A-vector(h))
assert len(s) == 1
return A, a, int(s[0])
if __name__ == "__main__":
p = ...
n = ...
m = ...
e = ...
h = ...
A,a,s = ahssp(h,e,n,m,p)下面是网上搜到的板子，对于例题计算时间可以减一半
# reference: https://algellar.github.io/2023/02/25/Lattice/Affine%20Hidden%20Subset%20Sums%20Problem/
# https://eprint.iacr.org/2020/461.pdf
from Crypto.Util.number import *
def allpmones(v):
return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)
def orthoLattice(B, x0):
r, m = B.nrows(), B.ncols()
M = identity_matrix(m).change_ring(ZZ)
B1 = B[:, :r]
B2 = B[:, r:]
V = Matrix(Zmod(x0), B1)
W = V.inverse()
M[r:m,:r] = -(W * B2.change_ring(Zmod(x0))).change_ring(ZZ).transpose()
M[:r, :r] = x0 * identity_matrix(r)
return M
def allones(v):
if len([vj for vj in v if vj in [0, 1]]) == len(v):
return v
if len([vj for vj in v if vj in [0, -1]]) == len(v):
return -v
return None
def recoverBinary(M5):
lv = [allones(vi) for vi in M5 if allones(vi)]
n = M5.nrows()
for v in lv:
for i in range(n):
nv = allones(M5[i] - v)
if nv and nv not in lv:
lv.append(nv)
nv = allones(M5[i] + v)
if nv and nv not in lv:
lv.append(nv)
return Matrix(lv)
def kernelLLL(M):
n = M.nrows()
m = M.ncols()
if m < 2 * n:
return M.right_kernel().matrix()
K = 2 ^ (m//2) * M.height()
MB = Matrix(ZZ, m + n, m)
MB[:n] = K * M
MB[n:] = identity_matrix(m)
MB2 = MB.T.LLL().T
assert MB2[:n, : m - n] == 0
Ke = MB2[n:, : m - n].T
return Ke
n = ...
m = ...
p = ...
h = ...
e = ...
e = vector(e)
h = vector(h)
print("n =", n, "m =", m)
E = matrix(ZZ, 2, m, [e.list(), h.list()])
M = orthoLattice(E, p)
t = cputime()
M2 = M.LLL()
print("LLL step1: %.1f" % cputime(t))
MOrtho = M2[: m-n-1]
print(" log(Height,2)=",int(log(MOrtho.height(),2)))
t2 = cputime()
ke = kernelLLL(MOrtho)
print(" Kernel: %.1f" % cputime(t2))
print(" Total step1: %.1f" % cputime(t))
beta = 2
tbk = cputime()
while beta < n:
if beta == 2:
M5 = ke.LLL()
else:
M5 = M5.BKZ(block_size=beta)
# we break when we only get vectors with {-1,0,1} components
if len([True for v in M5 if allpmones(v)]) == n:
break
if beta == 2:
beta = 10
else:
beta += 10
print("BKZ beta=%d: %.1f" % (beta, cputime(tbk)))
t2 = cputime()
MB = recoverBinary(M5)
print(" Recovery: %.1f" % cputime(t2))
L = matrix(Zmod(p), MB).transpose()[:n+1]
L = L.augment(-e[:n+1].column())
h_ = h[0:n+1]
a = L^-1*h_
a = [long_to_bytes(ZZ(i)).strip() for i in a]
for block in a:
try:
print(block.decode())
except:
None*论文题
关键字：RSA、相同私钥、格基规约、格、同一明文多次加密
题目
from Crypto.Util.number import *
flag = b'******'
flag = bytes_to_long(flag)
d = getPrime(400)
for i in range(4):
p = getPrime(512)
q = getPrime(512)
n = p * q
e = inverse(d, (p-1)*(q-1))
c = pow(flag, e, n)
print(f'e{i} =', e)
print(f'n{i} =', n)
print(f'c{i} =', c)
'''
e0 = 14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0 = 104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0 = 66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1 = 62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1 = 89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1 = 75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2 = 5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2 = 53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2 = 22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3 = 57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3 = 97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3 = 56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465
'''依据论文内容同理构造格子
from Crypto.Util.number import *
import gmpy2
e0 = 14663634286442041092028764808273515750847961898014201055608982250846018719684424125895815390624536073501623753618354026800118456911536861815261996929625814961086913500837475340797921236556312296934664701095834187857404704711288771338418177336783911864595983563560080719582434186801068157426993026446515265411
n0 = 104543450623548393448505960506840545298706691237630183178416927557780858213264769135818447427794932329909731890957245926915280713988801182894888947956846369966245947852409172099018409057129584780443712258590591272371802134906914886744538889099861890573943377480028655951935894660286388060056770675084677768397
c0 = 66400441793466385558399002350812383744096354576421495899465166492721568297592616443643465864544107914461044325088868615645524260480104397769130582397209585192620565774001015221725536884170662700337565613181799442382460047295553807602785067421981837709831158111951991854109179278733629950271657405211417740374
e1 = 62005504700456859456675572895620453845623573672275890584145949847469951381521709553504593023003977393014834639251022203398533914340078480147377747715528821418445514563871411209895815634752533151145061594791024551625615960423026244560340983481137777162236719939420428613005457949228517914830194749293637917667
n1 = 89410873947410184231222334229470195622685051370058935269198780539059522679122059486414591834635266301335656798768270022060656655274640699951736588085471509424575027153387518893978494158981314217195561629375189515702124478687925014362857206223379284909134299260355456357407022417434961226383007916607728238843
c1 = 75133250536426006056029454024900058936095761927174304108454764308417889983571094946046507426319589437822458959089546795698076608690695326741772662156830944126301658579142020817338297043884836598263468494533324693019866746045910394812656639124276516075062088756043949581789436307373276242558429450971458945061
e2 = 5365316217065391632204029784515519544882379449147835081003675696051077792179684123668298103660153980837519314114793091112163153158510344440829742753002176560016265852613076363394396640641504813912550948776926622696268531691467015580417575287779607009068332802842890478748171958455354463809356050553832863427
n2 = 53325942266099921615667538877103327425435396909592382386684073177331528393295928518724880712900970020425481561110366696624090824641115147978830715508666547064446891727446073538022824237798568413003419382767587742032676311751819789672319289920011033523044026418650515529084031754775286163358926609712626506433
c2 = 22289960513520782629306709529908652726794465066357062923684089176607114605563538085483920152508469429311012652149406853144200001391310165612163442404181970125704785325670969551080086517236489885046039799676581310781945432599048686184762485374030278657826206433571162451649808912276118945302558580745346371321
e3 = 57257245945110486431680573908783487217316546039634811903637650579658516537372808464426294780698320301497615457264001148504941375058983426920721566040576604013497311914160175024860226623138659970105781812246471618831032554729317463745699993647224910498474869868186318188994237457335796911524629938029123055027
n3 = 97233843381238063550322854422952777734101562842513647224354265328843953949189054347560960321126304504554067163501318212533606313039536188796999575130115659250566231010092273206623114900781284076452654791214088764465615154940874231056251107863895697778665275804663487113266180838319536762473697586368100928379
c3 = 56606672064789484727896188434430896229911224588055894584797861263107870392831242138537980507537270618683458635389444257040355313948352917061971042629958646854593628522401074068536976581232979947149230764268377747754284783531803366391759725774562719884482404532619163798580872386794273190532863916038929461465
M = gmpy2.iroot(n0,2)[0]
mat = [[M, e0, e1, e2,e3],
[0,-n0, 0, 0, 0],
[0, 0,-n1, 0, 0],
[0, 0, 0,-n2, 0],
[0, 0, 0, 0,-n3]]
L = Matrix(ZZ,mat)
hh = L.LLL()[0]
d = hh[0] // M
m = gmpy2.powmod(c0,d,n0)
flag = long_to_bytes(m)
print(flag)
# NSSCTF{12514adb-2c14-4777-96ff-90e95bc2b5cb}