SCTF 2024 Crypto WriteUp

Author: dawn1ight

这次题目质量都可以，每一个题都能学到新东西。

References:

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

class RSA():
    def __init__(self, nbits):
        self.nbits = nbits
        self.p, self.q = self.getPrimes()
        self.n = self.p*self.q
        self.Gift = self.Gift()
        self.priv, self.pub = self.keyGen()
        
    
    def getPrimes(self):
        nbits = self.nbits
        p = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        while p == q:
            q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        return p,q
    
    def Gift(self):
        p,q = self.p, self.q
        return (p^2 + p + 1)*(q^2 + q + 1)
    
    def keyGen(self):
        nbits = self.nbits
        while True:
            d = randint(2^(nbits//4),2^(nbits//2))
            if gcd(d,self.Gift) != 1:
                d = randint(2^(nbits//4),2^(nbits//2))
            e = pow(d,-1,self.phi)
            return (self.p,self.q,self.n,e,d),(self.n,e)
    

RRR = RSA(512)

bp = long_to_bytes(int(RRR.p))
FLAG = 'SCTF{'+md5(bp).hexdigest()+'}'


print(f'N = {RRR.n}')
print(f'e = {RRR.pub[1]}')

'''
N = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840
'''

开始算了很久，发现题中的e = pow(d,-1,self.phi)中的self.phi并没有在__init__(self, nbits)中说明

结合题目提示：Oops! Ψ is not good for encrypt, but good for gift.

这个self.phi = self.Gift（实际上gcd(d,self.Gift) != 1也是提示这个）

然后就是推导

\begin{gather*} e \times d \equiv 1 \mod phi \\ e \times d = 1 + k \times phi \\ e \times d = 1 + k \times (p^2+p+1) \times (q^2+q+1) \\ e \times d = 1+k\times((n^2)+n\times(p+q)+n+p^2+q^2+p+q+1) \\ let\;s = p + q \\ 1+1+k\times(n^2+n\times s+s^2-n+s+1) = 0 \mod e \end{gather*}

上面模方程中有两个未知量k和s

根据 $e \times d = 1 + k \times (p^2+p) \times (q^2+q)$ ，其中e.bit_length=4*nbits，nbits//4<d.bit_length<nbits//2，所以k.bit_length<nbits//2，

用二元coppersmith解

import itertools

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	if isinstance(f, Polynomial):
		x, = polygens(f.base_ring(), f.variable_name(), 1)
		f = f(x)

	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 []

n = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840

R.<s,k> = PolynomialRing(Zmod(e))
f = 1+k*(n^2+n*s+s^2-n+s+1)
bounds=(2^513,2^256)
print(small_roots(f , bounds , m=3 , d=4))
print(root)

不完全阻塞干扰

一个intelligence.pkl文件，从文件中读取序列化的对象并还原为原来的Python对象

import pickle

# 打开一个文件用于读取
with open('intelligence.pkl', 'rb') as f:
    # 使用pickle.load()从文件中读取序列化的对象并还原为原来的Python对象
    loaded_data = pickle.load(f)

# 打印加载的数据
print(loaded_data)

得到

# The ship crashed into the sun, causing a massive magnetic storm
#part of script
msg = bytes_to_long(FLAG)
n = p^5*q^2
phi = p^4*(p-1)*q*(q-1)
e = 65537
d = inverse(d,phi)
c = pow(m,e,n)
# c = 145554802564989933772666853449758467748433820771006616874558211691441588216921262672588167631397770260815821197485462873358280668164496459053150659240485200305314288108259163251006446515109018138298662011636423264380170119025895000021651886702521266669653335874489612060473962259596489445807308673497717101487224092493721535129391781431853820808463529747944795809850314965769365750993208968116864575686200409653590102945619744853690854644813177444995458528447525184291487005845375945194236352007426925987404637468097524735905540030962884807790630389799495153548300450435815577962308635103143187386444035094151992129110267595908492217520416633466787688326809639286703608138336958958449724993250735997663382433125872982238289419769011271925043792124263306262445811864346081207309546599603914842331643196984128658943528999381048833301951569809038023921101787071345517702911344900151843968213911899353962451480195808768038035044446206153179737023140055693141790385662942050774439391111437140968754546526191031278186881116757268998843581015398070043778631790328583529667194481319953424389090869226474999123124532354330671462280959215310810005231660418399403337476289138527331553267291013945347058144254374287422377547369897793812634181778309679601143245890494670013019155942690562552431527149178906855998534415120428884098317318129659099377634006938812654262148522236268027388683027513663867042278407716812565374141362015467076472409873946275500942547114202939578755575249750674734066843408758067001891408572444119999801055605577737379889503505649865554353749621313679734666376467890526136184241450593948838055612677564667946098308716892133196862716086041690426537245252116765796203427832657608512488619438752378624483485364908432609100523022628791451171084583484294929190998796485805496852608557456380717623462846198636093701726099310737244471075079541022111303662778829695340275795782631315412134758717966727565043332335558077486037869874106819581519353856396937832498623662166446395755447101393825864584024239951058366713573567250863658531585064635727070458886746791722270803893438211751165831616861912569513431821959562450032831904268205845224077709362068478

另有一个损毁的私钥文件cert.pem

文件以损坏，无法用openssl读取，写代码将base64转为16进制hex

import libnum
import base64
with open('cert.pem', 'r') as f:
    data = f.read()

key_64 = ''.join(data.split('\n')[1:-1])
key_num = libnum.s2n(base64.b64decode(key_64))
key_hex = hex(key_num)[2:]
print(key_hex)

得到

3082081502820380067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e50203010001028203800400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000028181008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e5701940000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002818100e4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a3900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

找资料学习了一下RSA私钥文件格式

私钥中各参数顺序n,e,d,p,q,dp,dq,iq，后面几个参数非必须写入私钥中

私钥文件首先是标签头30820815，其中82表示后面的两个字节0815为文件长度（这里注意是字节长度，换算成bit位要再×8），即私钥长0x0815bytes

后面02820380中02是分隔符，82表示后面两个字节0380为参数n的长度，即n.length=0x0380bytes，得到

n = 0x067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5

后面0203含义：02是分隔符，03表示后面3个字节为加密指数e，即e=0x10001(65537)

接下来02820380：02是分隔符，82表示后面两个字节0380为参数d的长度，即d.length=0x0380bytes，显然d被损坏了

接下来028181：02是分隔符，81表示后面1个字节81为参数p的长度，即p.length=0x81bytes，题目只给出了p的高位

p_high = 0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e57019400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

同理：q的高位

q_high = 0x00e4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a3900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

p_high中已知的部分有524bit，满足p的高位攻击

n = 0x067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
c = 145554802564989933772666853449758467748433820771006616874558211691441588216921262672588167631397770260815821197485462873358280668164496459053150659240485200305314288108259163251006446515109018138298662011636423264380170119025895000021651886702521266669653335874489612060473962259596489445807308673497717101487224092493721535129391781431853820808463529747944795809850314965769365750993208968116864575686200409653590102945619744853690854644813177444995458528447525184291487005845375945194236352007426925987404637468097524735905540030962884807790630389799495153548300450435815577962308635103143187386444035094151992129110267595908492217520416633466787688326809639286703608138336958958449724993250735997663382433125872982238289419769011271925043792124263306262445811864346081207309546599603914842331643196984128658943528999381048833301951569809038023921101787071345517702911344900151843968213911899353962451480195808768038035044446206153179737023140055693141790385662942050774439391111437140968754546526191031278186881116757268998843581015398070043778631790328583529667194481319953424389090869226474999123124532354330671462280959215310810005231660418399403337476289138527331553267291013945347058144254374287422377547369897793812634181778309679601143245890494670013019155942690562552431527149178906855998534415120428884098317318129659099377634006938812654262148522236268027388683027513663867042278407716812565374141362015467076472409873946275500942547114202939578755575249750674734066843408758067001891408572444119999801055605577737379889503505649865554353749621313679734666376467890526136184241450593948838055612677564667946098308716892133196862716086041690426537245252116765796203427832657608512488619438752378624483485364908432609100523022628791451171084583484294929190998796485805496852608557456380717623462846198636093701726099310737244471075079541022111303662778829695340275795782631315412134758717966727565043332335558077486037869874106819581519353856396937832498623662166446395755447101393825864584024239951058366713573567250863658531585064635727070458886746791722270803893438211751165831616861912569513431821959562450032831904268205845224077709362068478
e = 0x10001
p0 = 0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e570194
q0 = 0x00e4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a39

R.<x> = PolynomialRing(Zmod(n))
f = ((p0>>2)*2^502+x)^5
print(f.small_roots(X = 2^(502), beta = 0.45, epsilon = 0.03))

得到p，后面就可以正常解RSA了

这里要说明一下，对于上面为什么p要位移2bit，这就是我在比赛的时候踩的坑（在这里卡了一晚上……还是树哥有经验）

因为p的已知部分

0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e570194

转为二进制后

0b10000000011000111101000010100010000110000111011011100101110011100001111000100001000000011100001000000000000101010101001010010000011001101110110110011001011101101000100000101101000100000000001010100010100111101111111000001111001011111101111111001100001001110100001111111100100110100100101101011011011001010001110011001001011100010000100001101001100111101100101000101111101100011111001111011001001100010111010110111010111000110100001111100111110010010010111001001010010000011100011100101101000001011110010101110000000110010100

最后的两位是0，不一定是已知的真实值，可能是损坏的值，所以要把这两个bit去掉再进行高位攻击

验证：最后得到

p = 90158455407064353226740172256637847571736267390156796413259819366666851822735984542845914678308585714535762114331991779976105574125437982741541925319918477642851700979718859437613437250733519320418663913659250175079815430032463049804595241254755873838742300889891959766753209758679639806589383714664811420277
bin(p) = 0b1000000001100011110100001010001000011000011101101110010111001110000111100010000100000001110000100000000000010101010100101001000001100110111011011001100101110110100010000010110100010000000000101010001010011110111111100000111100101111110111111100110000100111010000111111110010011010010010110101101101100101000111001100100101110001000010000110100110011110110010100010111110110001111100111101100100110001011101011011101011100011010000111110011111001001001011100100101001000001110001110010110100000101111001010111000000011001011000001100100111000010111001100110101000111010111111110010011010111101001011000010011001011000011010101000010100000001111111111010101100000101010001000001110111111101110100100101110110100010110110110011111010010011110100100001001110000001111001000100001111001001000101110111001001011101011110010110000101000100010011111001110010101110101010010110101011111110000111111010010110100110010011001001101010010011000001001010101010001101100010001011001100011010110011010100101100100111000001010101101001110101

可以发现：那两位bit是10而不是00，说明p_high最后这两个bit位确实不是真实值

吸取这次教训，以后高位攻击是先转成二进制看看最后面的bit位，如果是0，要添加位移

Whisper

hint: Two public key certificates were monitored. And Mr. Dual intercepted a ciphertext. Just when he was in the rough, a Careless Whisper told that the length of a key parameter is carelessly set to 345 bits.

给了两个公钥文件和一个加密文件

用openssl读取一下，得到

N1 = 19216005446310864558409934096148904703198882317083224129431545386380435777354723744624028053518278514595663319253560114239018542660582960464010994454707936550902872627309424890333127288994449006783158078916602020794628546065674981593736606481809198149080696037584037699638293870122512237711498004090515845499
N2 = 4992911943798277344804876549224813326447469267517432903838084455752417287982320183584988170455130118418117937196562948710115292838538880218156469801938645463822391931977946975012481667095710882823897026534267366981015926659114785262116088548568215969555191689632109516970297562458267207338397574333407150103
e = 5352708372343813403035593638037107517373724079700735571091908193413083617555211472255125798199165859811237950085789893649651552088125747433480591652396404710788778815075048587264350078253899425987466937040099316084273123603046629945048298154353920118466252136326911019666012632927688983695457057246503276867
c = 15215414324218119514166856548319827087347975479953435757551380183481824597666586239577164581282639891207362199632694698810120856780147289618566227285967212830337320315326701453355443595245474646348352728630245065334265985318506260363891869088324717641979951184093710784542525865784982264295576662469010725462

Dual RSA是一种由Sun等人在2007年提出的RSA变体，其主要特点是两个实例共享相同的公钥和私钥指数，但具有不同的模数。这种设计的主要优势在于减少了存储需求，因为只需要存储一套公钥和私钥即可处理两个不同的RSA实例。

Dual RSA——双生RSA，对偶RSA | 独奏の小屋 (hasegawaazusa.github.io)

这个知识点在 61dctf 和 0ctf-2017-final 出现过

看了关于低解密指数Dual RSA的exp都来自 [Authentication&Secrecy (Crypto 1000pts) - MDWiki (elliptic-shiho.github.io)](https://elliptic-shiho.github.io/ctf-writeups/#!ctf/2017/0CTF Finals/cr1000-AuthenticationSecrecy/README.md)

代码来自：SCTF 2024 By W&M - W&M Team (wm-team.cn)

from sage.all import *
import math
import itertools

def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = f'{ii:02d} '
        for jj in range(BB.dimensions()[1]):
            a += ' ' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

def dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt):
    N = (n1 + n2) // 2
    A = ZZ(math.floor(N**0.5))

    _XX = ZZ(math.floor(N**delta))
    _YY = ZZ(math.floor(N**0.5))
    _ZZ = ZZ(math.floor(N**(delta - 1./4)))
    _UU = _XX * _YY + 1

    M = Matrix(ZZ, [[A, e], [0, n1]])
    B = M.LLL()
    l11, l12 = B[0]
    l21, l22 = B[1]
    l_11 = ZZ(l11 // A)
    l_21 = ZZ(l21 // A)

    modulo = e * l_21
    F = Zmod(modulo)

    PR = PolynomialRing(F, 'u, x, y, z')
    u, x, y, z = PR.gens()

    PK = PolynomialRing(ZZ, 'uk, xk, yk, zk')
    uk, xk, yk, zk = PK.gens()

    PQ = PK.quo(xk * yk + 1 - uk)
    f = PK(x * (n2 + y) - e * l_11 * z + 1)
    fbar = PQ(f).lift()

    gijk = {}
    for k in range(mm + 1):
        for i in range(mm - k + 1):
            for j in range(mm - k - i + 1):
                gijk[i, j, k] = PQ(xk**i * zk**j * PK(fbar)**k * modulo**(mm - k)).lift()

    hjkl = {}
    for j in range(1, tt + 1):
        for k in range(math.floor(mm / tt) * j, mm + 1):
            for l in range(k + 1):
                hjkl[j, k, l] = PQ(yk**j * zk**(k - l) * PK(fbar)**l * modulo**(mm - l)).lift()

    monomials = []
    for k in gijk.keys():
        monomials += gijk[k].monomials()
    for k in hjkl.keys():
        monomials += hjkl[k].monomials()

    monomials = sorted(set(monomials), reverse=True)
    assert len(monomials) == len(gijk) + len(hjkl)
    dim = len(monomials)

    M = Matrix(ZZ, dim)
    row = 0
    for k in gijk.keys():
        for i, monomial in enumerate(monomials):
            M[row, i] = gijk[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
        row += 1
    for k in hjkl.keys():
        for i, monomial in enumerate(monomials):
            M[row, i] = hjkl[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
        row += 1

    matrix_overview(M)
    print('=' * 128)

    B = M.LLL()

    matrix_overview(B)

    H = {i: 0 for i in range(dim)}
    for j in range(dim):
        for i in range(dim):
            H[i] += PK((monomials[j] * B[i, j]) / monomials[j].subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ))
    H = list(H.values())

    PQ = PolynomialRing(QQ, 'uq, xq, yq, zq')
    uq, xq, yq, zq = PQ.gens()

    for i in range(dim):
        H[i] = PQ(H[i].subs(uk=xk * yk + 1))

    I = Ideal(*H[1:20])
    g = I.groebner_basis('giac')[::-1]
    mon = [t.monomials() for t in g]

    PX = PolynomialRing(ZZ, 'xs')
    xs = PX.gen()

    x_pol = y_pol = z_pol = None

    for i in range(len(g)):
        if mon[i] == [xq, 1]:
            print(g[i] / g[i].lc())
            x_pol = g[i] / g[i].lc()
        elif mon[i] == [yq, 1]:
            print(g[i] / g[i].lc())
            y_pol = g[i] / g[i].lc()
        elif mon[i] == [zq, 1]:
            print(g[i] / g[i].lc())
            z_pol = g[i] / g[i].lc()

    if x_pol is None or y_pol is None or z_pol is None:
        print('[-] Failed: we cannot get a solution...')
        return

    x0 = x_pol.subs(xq=xs).roots()[0][0]
    y0 = y_pol.subs(yq=xs).roots()[0][0]
    z0 = z_pol.subs(zq=xs).roots()[0][0]

    assert f(x0 * y0 + 1, x0, y0, z0) % modulo == 0

    a0 = z0
    a1 = (x0 * (n2 + y0) + 1 - e * l_11 * z0) // (e * l_21)

    d = a0 * l_11 + a1 * l_21
    return d

if __name__ == '__main__':
    delta = 0.334
    mm = 4
    tt = 2

    n1 = 0x1b5d4fe0aa6782e275d4ce12a6d57562efbbe7db6f5277255b891729bfa2a18d3edb49843d7989a37b9516be2df8ca939058e65f64b5fb2071bea4f5f8d1392895b32bf0377d99f4f79979125e5db01cdb5080a1c2d665c9ac31b5823025499c9513277bae5e7a846cd271c4396e2ba219020e58a9055cb18a28d36a00bf717b
    e = 0x079f5ccc665767b4a257e5c1ff56e9803df2e5650302daad420105fe672447743bd3f0bea1c46a4987932e9a886ca87a7afd7796abf1e5629c4986fe4f22e89cdce7abb06624465146a2e2b6ca9ab3196ceab7467974c1dc45608a200411b291fdaf99f7d80dce4db3566f4a9e2e574c6224cd07d80638d28f7820bcf4b49143
    n2 = 0x071c324e8769493187c15f72d5cc695729b48488ee3fbd01db00d5c478f08c7cf32093ba61745051d3e9d169523aa91438181f47679aff5edd22950f74a1eb1443320aaa5d97f5c1e81b5ef9a3e69ba669abc4c6c4b405f5088a603a74f9bcef88823b4523574114c810600838728196f8e5e0d4aeeeeab79dd8683a72f3c017

    d = dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt)
    print(d)

LinearARTs

from random import choices
import json
from sage.all import *
from Crypto.Util.number import *
from sage.groups.perm_gps.permgroup_named import SymmetricGroup



def Young(FLAG):
    f = int.from_bytes(FLAG, "big")
    q = 65537

    s = []
    while f:
        s.append(f % q)
        f //= q
    s = vector(GF(q), s)

    n, m = len(s), len(s) ** 2

    A = Matrix(GF(q), m, n, lambda i, j: randint(0, q - 1))
    e = vector(choices(range(2^8), k=m), GF(q))*Matrix(ZZ,PermutationGroupElement(SymmetricGroup(m).random_element()).matrix())
    b = (A*s) + e


    return A,b


def Old(m, nbits):
    Sn = SymmetricGroup(m)
    p = [getPrime(360) for i in range(m)]
    N = sorted([getRandomNBitInteger(nbits) for _ in range(m)])
    S = []
    for i in range(m):
        r = [N[_] % p[i] for _ in range(m)]
        r = vector(ZZ,r)

        Per = Sn.random_element()
        P = PermutationGroupElement(Per)
        Pm = Matrix(ZZ,P.matrix())
        r *= Pm
        S.append(r)
    S = matrix(ZZ,S)

    with open('Old.matrix','w') as f:
        json.dump({"S": str(list(S)),"p": str(p)}, f)
    
    return N

def chall(nn):
    # The challenge lasted nn rounds
    # Young_level * virtue >= Old_level , where virtue = nn + 1

    h = []
    HP = []
    MP = []
    Old_level = 625*2*2
    Young_level = 25*5*5*2

    M = getPrime(Old_level)
    XP = getRandomRange(1,M)
    for _ in range(nn):
        a = getRandomRange(1,M)
        b = a*XP % M
        HP.append(a)
        MP.append(b)
        delta_level = Old_level - Young_level
        h.append(b >> delta_level << delta_level)


        

    return XP,M,HP,MP,h
    

mm = 16
nn = 9
nbits = 3840


A,b = Young(FLAG)
N = Old(mm, nbits)

XP,M,HP,MP,h = chall(nn)

# MP is useful ,I can use him to cast five lightning spells
D = diagonal_matrix(GF(0x10001),N+MP)
Sn = SymmetricGroup(5*5)
Per = Sn.random_element()

P = PermutationGroupElement(Per)
PM = Matrix(GF(0x10001),P.matrix())




AA = A*D*PM

with open('D.matrix','w') as f:
    json.dump({"D": str(list(D))}, f)



# OK! Find your martial arts, and then you can get the flag.


with open("output.txt", "w") as f:
    json.dump({"AA": str(list(AA)), "b": str(b)}, f)


print(f'My SymmetricGroup is {Sn}, and my element is {Per}')
print(f'M = {M}')
print(f'h = {h}')
print(f'HP = {HP}')



'''
My SymmetricGroup is Symmetric group of order 25! as a permutation group, and my element is (1,23,2,13,3,16,15,6,22,18,14,4,25,11,20,24,21,9,5,17,7,19,10,12,8)
M = 309169501373330124045649100152326414225457160505584328527283516968464416389302355829097052128714780092162406614467026044744098784954762500832278190406881802198303575338158311874491341970444579146638248815636164413771772581964591833455055886833879504320098506335328910379223983277573694356846337961823081287986674791459748001014087760336006966850192999063236788568848765812192775492248445517060690151700498331622538367493718859724934115228375142396923937735633684527869745420378950550480692200706066019831688796077313463059296313396035429537407627377675974680696279162072713257960965681304091009329215383850223530139165455326927677102783057396241883175412729216204807235187239596365892879371542214145426492827777125727970815789114727245511828912252143569
h = [3565625090222584896920916237461241765625829204082396377386021101162536812411479309464325956424849651112502540095796665989782448302150047491000013081443589381171861802823657878857754676608742927932812781165716659755896099505195018830422885342733139127785165794897376463794696074605473512720672450888626374504772116915620258088753289255996096552892614801083370595759624402874902282635442418547645823133641783382626721416313803991932439793168113855890150599332984583295219543856049901518912201443065300476561372304830840276820139993555523469165273121628823953454126151208689489078628524850757272649061955436843893289237414654732290904213005377463766762255194199607599718375650615493280298611532927519686558670313416090562438894368509350896602591065538560, 286740894693471986151090603562932147965458822098297907353215124508138484491994267754471216888566417392843923796488725160656461314962959042706124173470952968241147487040483767911639159119505992553207913863135028688626896196178757909088128827455625174341894140582939848620368540355056452428553556546413465430152617836247505772663758606552662729528340901377490256234099815707208769579251833692482247933846648593307680305448986314447242583396656418769737861680456297522358131674037354880608888487272985141452871763297604747444764332049229204365395410106847606241968638474099061876569990163879954288002836750959104349076854993248516655758322107956062243468530601256243967323153547535726777712582210098524981336526310800007425464476736381605758610129914167296, 202445786178968197828946112166667682571891905248793492278433983415264905988886412319222803698650008275405441752508434114212113517053913972304515710532012288036732448805044856628337036478357496484044773293960097063848568051250774170422935810965491124102107450786197166927290614807575403261921855599437944525251033428950982061449203659272914014109623656149839199935645660386382459896840619916225080206084500617856222897968865436783548821187873430635315967325778835200418210099836625362334832448337496843986398001079590846483593452928602841826412074751479179471599709999916393508418744578599831517548843854866251289525136765297969136698285441109232446206843977149859059568434871554288377088102779550812057943402777376610057499017696210394059743209313009664, 114630215368349491250326648494149748728124718005857201833657753308980378360823813480094685056650954220208569495921715772409260048257134505583210349697604470912610748671738387322753221966031149012764535612682778184882174392537951540598166408100353995693537007226929298573802177602978136134506604598926968767277963229517115896872176785224081721198822306288029114228955110090342800494317915814873698062519566559427796027618459996738296291782097320521350172532923653864250838232011730592925952612867718426259229217480911558421879422300001641170190840092379605603655701803649801243406059797147753118709730213303123683329677068533772082060407549189564758770771711148071596602056935716438347268248190581386987972757911856155781563899140822797888004226036006912, 128249367678574240079270694387429301574447189368221420750047602082333294620192478593526403955673394674124614483528399397766799072294205407818283464218350759458734269850052374022374583516046462573242829813776315162366850512131805663098817008453376098230770350796562755291771240680188153978483320771657621585572523650775437065002970862224206343896650474078023744187172724827284900132434561870157274624749481073656218832950661419154809116630241897087363941068977482336058825222409922455565132842885044852488100437379745993397785019888492704177085025661715401393223084613786993440233186999961708361656323625565518221228007812487647507152403406194060777071074419667727156839380340460479471882700515901974677682591933244024896502221255164137619867236474814464, 59331241745881917257932833661253483407124868132789104057434303748460794035055450167305496229505776497962206681068504038089886777631651664100577079680933516972657892279730519042800959265778075851643260975944157575808540832473360789304763830393990596483325556391563383526131388426655998362610795663009444329530380313582369506744601127066018505286584082074112032220681653032998814836135211241601616761559477125123260865574463289315537641250468595444847485104869371846138937594815717839233479424297762637589843061706537365341325349697086472650360732699495909942722893269089976271337217878676728476285757191230122449283410993290558727101211299826258005529280347023431637543174327095221833097882251371141896661614980087581376418853642047359092191718247759872, 194175487858295065586566223420720835354218714701012787036868166885106803179611016852320235121944886794854103233580220709024806072743993477154116046455972680314714490810103482613775169723949822599089353607462687446238694112422779778557153306320141326888706724709408146840971915646939721136724368012432988045478440516756541030644897102338343015620307071124895653986756365725579987250601332133147888516462970772662004254372283824275049130754409522022155104472953510056515893487814795314057133448327072939691256835996305152489881345263632544581620669637374642183724635278556621665654137071320546871015687481523597402928763713183489458838102245889150936728919959706046092027960728825776566021949524779914956226078468441681639597976295123311554992063660425216, 115807966653135071136266364151575193370063353963428994232152558690537462513652457844803096649471511022423130391640990718769139833768597282872892832632006932256100725142377601958457582836326282142674470340977659300588249614977457789078637672424804434580082554677223019302922992562279282682989740074843377451539592513262883913515900320935326048141177654658002842824967867990878423576079246988742657580816398545604320575322509216636723893917401586976250940528255869144608693606581992658961868351662299980182039083401570931369157275822911645710245831972301615048181855392924402552747776587682847866506513589721569586179062186510923857682304736484524409943982860419833114775174973677241133994963586243092033231181717755422868113246798964708435895447826989056, 35892864763676162390876495832131732661057713103645821857653105944898881372368808709419507620431545862639883539544774550258981962490994311035563824804791343118179784911204081384298523734092852978345353083620780025983844560713535542579917199852557029443606552741189260726705956142592472777625642697686483587065598383553745177190736612246797880186504227507540789056735743669295160656843457591270441961646851151123270490417727787782300206183313402455683157806373799412772262389178947152383087432869175216907112201344491993073522598897459497720231382736974467891671184580545749653915968971302794570679028312275641136161418552643700105215949462752782765599606395043723535992514850129235084780569665298381129831228968986167487292913320768400938041503014453248]
HP = [182123398439336131233484419016500805950625530876289136147992418330368556518782504528500478328506268530182121028338611308706301778495117293952384271741141930454826813234222655694969514594179399691491676343267560926415204796892285953757083137635724586246679285504584200603423040990857955982592545447321735123888380669252758270022750955484747603018957220340523162322224297824154306196315662236519394066376582303992842999145368668536271548561974662730580382535581064544751603313110317522142473855128127879421866476758202400277448627166191464212616826131845112048518089279156877724351779259697512559047606602356481432326384500230304234630224805224043299183292854524931957718694768306272627669496947333830650701612740067754226344379590044087735385490127725862, 143170049879066655087340950742576943114220056125957541251904657597420632960015895981469092773424062349481612793313849969949143634455140221504418524950906026552571808412365313452770620316647140315635576351924131570731151371864300979486246561311374091503771233474221846682477948158595874825046725186096019808916856990568087679235183223125111635340379631262792582193894921427748477534899648278496684573736979116799130367368459501772350225298850161734598992871658808303947946703790369232633550983464071710073626283163523659905448412753809088559015473221667463885047754120012784534383142422681768521744011385759111784771218858429141270195947803513052066866898605116497618560152428747336114471742600059289342252682494024257280492765302681978041917175224445454, 181932081065216017223259767432026159751069100962417675256904857171174594214631105569878401257202843288868067795959660425655397502682572819329811836847256980387967545675607257191386494389870983892416162767006265255985611267066664459013834260578459679814704254643652527448346657946799415019242620362556994094217501805852227552561431064112972359577708305419407712233651342990435225577864469921706228376386943352990854043536613387681781610381704457332320684886669558444649325853462867815167473502469305672972117003639658784729134706896312010708005781941993559519054971159338636279746679220293668476785752715272037394473281514117697060980377364913173031572794672785720241295564153405600993322639561228795731008971285970805298272968367327982292736365952177736, 152197501838094386559667505260111556746524794647762036036984156853293482749405051706379215782024625767996604204199239858042655575156447769644733342469940464962491758196879181740442958683860120188153222622045687386550968060691333980045707578681522952010130720785366069103645756481641865768541014660604224000448808608848607142992914438243019336580286597455942208546183871629991237012627078724041815698483916930337697145596477943636313719062754662224057190310995369364817444976298713991954316505112491477110025799278176478205958831032614361098570277711286905522504386261323350696026797810604096448605140635754896533192146402989175530945145957561334345659035675075518654525640506611082619111666729303712983450765181951782352125875791130477959487243678637091, 13260127114160132039578764564277724908293717164091148143281881592450508800268944502885346275659282139962084615098549527321116911955505649119891798866789702019684393024690093331965422247341532921411724247274538089836518071897735012248880718279028139698315282234778842097294789834605571276706239190589177804771135138639650083317735678737873354475068162084129555751126946723880482765306519620594499615623179141020788167278111494656031619604249830332631535459164808166638124806843052957919064456863967475953053614347964520430672883482509352453640521720313380086324061829310129198351733197836811498655541708077300463414261809122652381872563486116022996781876662952751320598808796685963865092538114154484684417346701057121540968905340884852819266786655758589, 7726965701613058376939617426173930484905424609871511448979899585789330472291184137208473525618669017229437131718602138062693323242254540169837667647945751730728109543890184121875756549720616016417689684297714982752898170211522441794931085191911567142756874944612942983995000585648922927662513704308624388978740497618316239028274910398075357992565743563209649419566296437582035744561981287334953927069851636537379718348745797306743042426246174030053256711319421877929342022143063981126785133505358707977994735220823800241921524140116409926290245600210702333580796340264633188699655847265231481741281891892263047439742010063674785264961945504178892794083333407945969304699309469264200568906760592035714702098416830232068808480043043046899584880476365211, 180019050945153380400290419089497765220330628588910896281952550416089875088850281952204916892735263785902815673400396668990373595469072648699918494008065197996354855591310768398651316061183602708507734278231600299784123286043254063248471261126675877896352754705297219631260970186401862696837291306580096200621090959901083133979809165850290006958174043988594120292941019793669119321273860506863788556691180109910206811333775009617945993184652622929206661236756401337666271307645630166144277622050610823301758570383783302397752531144991093835433241988398747399949918853848203882961092951831645541246295873588649289531107814613167236073250185453276804880016561013769084225682634383784489652871867815664211238325551136693769474979447466046146633345857611195, 153629149463789849413429112784055293255734339122176408662359601604336509143473758509975758863274395783633189549584941125392600362702091233425733911049553699926215208790821097092121122480643207790283486114884596194662369389215802952635756543090033023067139610689568413680910122744788001731552268160061684744631583107942765508030881967516350806276166348479082293252825499156766363138008724860360262292088895234376252334258828427316419408016153682496909981178280572676774045522450227853270448821337580837554794712541359286413423248459963738684095208415746808201768526760043282181933350859027227907243501251390338333188167931974689538439823388790515993422873395205982049903304374197483641428361419371833919139638015039992779119950859870347438758668679332495, 276427336329209668688130277925589460360311327851014652110707325284581770430564994121969230515633704248812997375123175470056237355182594647858048847262042361717893313893682161435196235153101006253340527909451448103893104917041136181377802230394106849393237486928849495116195885563734324888330607632821513438897200091110205098807840437587357564885934968344589488833398453563587665373858111713149172110412979734635024012258145628247175689960363707897865274630069427102722542299814253018238192096822853168130596686909789751383470674093768125446566821380042192204089190375373896356618809538058749144194802493153530124585829617231928160073305696376878930156414497547968857648212679322981790227182840452493558367673102471438871220031633314842129410346869161197]
'''

题目名字取自《线性代数的艺术》《The Art of Linear Algebra》

Old函数来自d3ctf2023 - d3noisy

from Crypto.Util.number import *
from random import shuffle
from sympy import nextprime

def getKey():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    N = [getRandomNBitInteger(3211) for _ in range(15)]
    d = 0
    for _ in N:
        d = d ^ _
    d = nextprime(d)
    e = inverse(d,(p-1)*(q-1))
    return N, n, e

def leak(N):
    p,S = [],[]
    for i in range(15):
        p.append(getPrime(321))
        r = [N[_]%p[i] for _ in range(15)]
        shuffle(r)
        S.append(r)
    return p, S

m = bytes_to_long(flag)
N,n,e = getKey()
p,S = leak(N)
c = pow(m,e,n)

print(f"n = {n}")
print(f"p = {p}")
print(f"S = {S}")
print(f"c = {c}")

原理：2023 AntCTF x D^3CTF Writeup By S1uM4in

exp: SCTF 2024 By W&M - W&M Team (wm-team.cn)

Sn = (1,23,2,13,3,16,15,6,22,18,14,4,25,11,20,24,21,9,5,17,7,19,10,12,8)
M = 309169501373330124045649100152326414225457160505584328527283516968464416389302355829097052128714780092162406614467026044744098784954762500832278190406881802198303575338158311874491341970444579146638248815636164413771772581964591833455055886833879504320098506335328910379223983277573694356846337961823081287986674791459748001014087760336006966850192999063236788568848765812192775492248445517060690151700498331622538367493718859724934115228375142396923937735633684527869745420378950550480692200706066019831688796077313463059296313396035429537407627377675974680696279162072713257960965681304091009329215383850223530139165455326927677102783057396241883175412729216204807235187239596365892879371542214145426492827777125727970815789114727245511828912252143569
h = [3565625090222584896920916237461241765625829204082396377386021101162536812411479309464325956424849651112502540095796665989782448302150047491000013081443589381171861802823657878857754676608742927932812781165716659755896099505195018830422885342733139127785165794897376463794696074605473512720672450888626374504772116915620258088753289255996096552892614801083370595759624402874902282635442418547645823133641783382626721416313803991932439793168113855890150599332984583295219543856049901518912201443065300476561372304830840276820139993555523469165273121628823953454126151208689489078628524850757272649061955436843893289237414654732290904213005377463766762255194199607599718375650615493280298611532927519686558670313416090562438894368509350896602591065538560, 286740894693471986151090603562932147965458822098297907353215124508138484491994267754471216888566417392843923796488725160656461314962959042706124173470952968241147487040483767911639159119505992553207913863135028688626896196178757909088128827455625174341894140582939848620368540355056452428553556546413465430152617836247505772663758606552662729528340901377490256234099815707208769579251833692482247933846648593307680305448986314447242583396656418769737861680456297522358131674037354880608888487272985141452871763297604747444764332049229204365395410106847606241968638474099061876569990163879954288002836750959104349076854993248516655758322107956062243468530601256243967323153547535726777712582210098524981336526310800007425464476736381605758610129914167296, 202445786178968197828946112166667682571891905248793492278433983415264905988886412319222803698650008275405441752508434114212113517053913972304515710532012288036732448805044856628337036478357496484044773293960097063848568051250774170422935810965491124102107450786197166927290614807575403261921855599437944525251033428950982061449203659272914014109623656149839199935645660386382459896840619916225080206084500617856222897968865436783548821187873430635315967325778835200418210099836625362334832448337496843986398001079590846483593452928602841826412074751479179471599709999916393508418744578599831517548843854866251289525136765297969136698285441109232446206843977149859059568434871554288377088102779550812057943402777376610057499017696210394059743209313009664, 114630215368349491250326648494149748728124718005857201833657753308980378360823813480094685056650954220208569495921715772409260048257134505583210349697604470912610748671738387322753221966031149012764535612682778184882174392537951540598166408100353995693537007226929298573802177602978136134506604598926968767277963229517115896872176785224081721198822306288029114228955110090342800494317915814873698062519566559427796027618459996738296291782097320521350172532923653864250838232011730592925952612867718426259229217480911558421879422300001641170190840092379605603655701803649801243406059797147753118709730213303123683329677068533772082060407549189564758770771711148071596602056935716438347268248190581386987972757911856155781563899140822797888004226036006912, 128249367678574240079270694387429301574447189368221420750047602082333294620192478593526403955673394674124614483528399397766799072294205407818283464218350759458734269850052374022374583516046462573242829813776315162366850512131805663098817008453376098230770350796562755291771240680188153978483320771657621585572523650775437065002970862224206343896650474078023744187172724827284900132434561870157274624749481073656218832950661419154809116630241897087363941068977482336058825222409922455565132842885044852488100437379745993397785019888492704177085025661715401393223084613786993440233186999961708361656323625565518221228007812487647507152403406194060777071074419667727156839380340460479471882700515901974677682591933244024896502221255164137619867236474814464, 59331241745881917257932833661253483407124868132789104057434303748460794035055450167305496229505776497962206681068504038089886777631651664100577079680933516972657892279730519042800959265778075851643260975944157575808540832473360789304763830393990596483325556391563383526131388426655998362610795663009444329530380313582369506744601127066018505286584082074112032220681653032998814836135211241601616761559477125123260865574463289315537641250468595444847485104869371846138937594815717839233479424297762637589843061706537365341325349697086472650360732699495909942722893269089976271337217878676728476285757191230122449283410993290558727101211299826258005529280347023431637543174327095221833097882251371141896661614980087581376418853642047359092191718247759872, 194175487858295065586566223420720835354218714701012787036868166885106803179611016852320235121944886794854103233580220709024806072743993477154116046455972680314714490810103482613775169723949822599089353607462687446238694112422779778557153306320141326888706724709408146840971915646939721136724368012432988045478440516756541030644897102338343015620307071124895653986756365725579987250601332133147888516462970772662004254372283824275049130754409522022155104472953510056515893487814795314057133448327072939691256835996305152489881345263632544581620669637374642183724635278556621665654137071320546871015687481523597402928763713183489458838102245889150936728919959706046092027960728825776566021949524779914956226078468441681639597976295123311554992063660425216, 115807966653135071136266364151575193370063353963428994232152558690537462513652457844803096649471511022423130391640990718769139833768597282872892832632006932256100725142377601958457582836326282142674470340977659300588249614977457789078637672424804434580082554677223019302922992562279282682989740074843377451539592513262883913515900320935326048141177654658002842824967867990878423576079246988742657580816398545604320575322509216636723893917401586976250940528255869144608693606581992658961868351662299980182039083401570931369157275822911645710245831972301615048181855392924402552747776587682847866506513589721569586179062186510923857682304736484524409943982860419833114775174973677241133994963586243092033231181717755422868113246798964708435895447826989056, 35892864763676162390876495832131732661057713103645821857653105944898881372368808709419507620431545862639883539544774550258981962490994311035563824804791343118179784911204081384298523734092852978345353083620780025983844560713535542579917199852557029443606552741189260726705956142592472777625642697686483587065598383553745177190736612246797880186504227507540789056735743669295160656843457591270441961646851151123270490417727787782300206183313402455683157806373799412772262389178947152383087432869175216907112201344491993073522598897459497720231382736974467891671184580545749653915968971302794570679028312275641136161418552643700105215949462752782765599606395043723535992514850129235084780569665298381129831228968986167487292913320768400938041503014453248]
HP = [182123398439336131233484419016500805950625530876289136147992418330368556518782504528500478328506268530182121028338611308706301778495117293952384271741141930454826813234222655694969514594179399691491676343267560926415204796892285953757083137635724586246679285504584200603423040990857955982592545447321735123888380669252758270022750955484747603018957220340523162322224297824154306196315662236519394066376582303992842999145368668536271548561974662730580382535581064544751603313110317522142473855128127879421866476758202400277448627166191464212616826131845112048518089279156877724351779259697512559047606602356481432326384500230304234630224805224043299183292854524931957718694768306272627669496947333830650701612740067754226344379590044087735385490127725862, 143170049879066655087340950742576943114220056125957541251904657597420632960015895981469092773424062349481612793313849969949143634455140221504418524950906026552571808412365313452770620316647140315635576351924131570731151371864300979486246561311374091503771233474221846682477948158595874825046725186096019808916856990568087679235183223125111635340379631262792582193894921427748477534899648278496684573736979116799130367368459501772350225298850161734598992871658808303947946703790369232633550983464071710073626283163523659905448412753809088559015473221667463885047754120012784534383142422681768521744011385759111784771218858429141270195947803513052066866898605116497618560152428747336114471742600059289342252682494024257280492765302681978041917175224445454, 181932081065216017223259767432026159751069100962417675256904857171174594214631105569878401257202843288868067795959660425655397502682572819329811836847256980387967545675607257191386494389870983892416162767006265255985611267066664459013834260578459679814704254643652527448346657946799415019242620362556994094217501805852227552561431064112972359577708305419407712233651342990435225577864469921706228376386943352990854043536613387681781610381704457332320684886669558444649325853462867815167473502469305672972117003639658784729134706896312010708005781941993559519054971159338636279746679220293668476785752715272037394473281514117697060980377364913173031572794672785720241295564153405600993322639561228795731008971285970805298272968367327982292736365952177736, 152197501838094386559667505260111556746524794647762036036984156853293482749405051706379215782024625767996604204199239858042655575156447769644733342469940464962491758196879181740442958683860120188153222622045687386550968060691333980045707578681522952010130720785366069103645756481641865768541014660604224000448808608848607142992914438243019336580286597455942208546183871629991237012627078724041815698483916930337697145596477943636313719062754662224057190310995369364817444976298713991954316505112491477110025799278176478205958831032614361098570277711286905522504386261323350696026797810604096448605140635754896533192146402989175530945145957561334345659035675075518654525640506611082619111666729303712983450765181951782352125875791130477959487243678637091, 13260127114160132039578764564277724908293717164091148143281881592450508800268944502885346275659282139962084615098549527321116911955505649119891798866789702019684393024690093331965422247341532921411724247274538089836518071897735012248880718279028139698315282234778842097294789834605571276706239190589177804771135138639650083317735678737873354475068162084129555751126946723880482765306519620594499615623179141020788167278111494656031619604249830332631535459164808166638124806843052957919064456863967475953053614347964520430672883482509352453640521720313380086324061829310129198351733197836811498655541708077300463414261809122652381872563486116022996781876662952751320598808796685963865092538114154484684417346701057121540968905340884852819266786655758589, 7726965701613058376939617426173930484905424609871511448979899585789330472291184137208473525618669017229437131718602138062693323242254540169837667647945751730728109543890184121875756549720616016417689684297714982752898170211522441794931085191911567142756874944612942983995000585648922927662513704308624388978740497618316239028274910398075357992565743563209649419566296437582035744561981287334953927069851636537379718348745797306743042426246174030053256711319421877929342022143063981126785133505358707977994735220823800241921524140116409926290245600210702333580796340264633188699655847265231481741281891892263047439742010063674785264961945504178892794083333407945969304699309469264200568906760592035714702098416830232068808480043043046899584880476365211, 180019050945153380400290419089497765220330628588910896281952550416089875088850281952204916892735263785902815673400396668990373595469072648699918494008065197996354855591310768398651316061183602708507734278231600299784123286043254063248471261126675877896352754705297219631260970186401862696837291306580096200621090959901083133979809165850290006958174043988594120292941019793669119321273860506863788556691180109910206811333775009617945993184652622929206661236756401337666271307645630166144277622050610823301758570383783302397752531144991093835433241988398747399949918853848203882961092951831645541246295873588649289531107814613167236073250185453276804880016561013769084225682634383784489652871867815664211238325551136693769474979447466046146633345857611195, 153629149463789849413429112784055293255734339122176408662359601604336509143473758509975758863274395783633189549584941125392600362702091233425733911049553699926215208790821097092121122480643207790283486114884596194662369389215802952635756543090033023067139610689568413680910122744788001731552268160061684744631583107942765508030881967516350806276166348479082293252825499156766363138008724860360262292088895234376252334258828427316419408016153682496909981178280572676774045522450227853270448821337580837554794712541359286413423248459963738684095208415746808201768526760043282181933350859027227907243501251390338333188167931974689538439823388790515993422873395205982049903304374197483641428361419371833919139638015039992779119950859870347438758668679332495, 276427336329209668688130277925589460360311327851014652110707325284581770430564994121969230515633704248812997375123175470056237355182594647858048847262042361717893313893682161435196235153101006253340527909451448103893104917041136181377802230394106849393237486928849495116195885563734324888330607632821513438897200091110205098807840437587357564885934968344589488833398453563587665373858111713149172110412979734635024012258145628247175689960363707897865274630069427102722542299814253018238192096822853168130596686909789751383470674093768125446566821380042192204089190375373896356618809538058749144194802493153530124585829617231928160073305696376878930156414497547968857648212679322981790227182840452493558367673102471438871220031633314842129410346869161197]
N = [4708767973081528023168573044926947658934563237858334014553630859725073243020070244020323437568857351830649743859959646887898299257997756638988846262162225538150844234728800901619698537585321714737408891139629868705840516091582428355548389333579393366732136328125608177487216053734023682113947465331733121489462179165899299048240920229183682356939757096088786234579408711573077204737627084462804644499357094804766876894598825249043115135941089964419043192271077333533836683714152246274269275845933219181872804910838148500474338484859566768928323323696593636427339969267716019100309031892715209683025623234849975307895464735938269345261085730940438716186759614397893026604088677569875434747734189181898326976271333880519091162243501684748772834879792466167298445248175389229863559724478950676239029563324439151410551016381722349890838522197681991628177446461063518141690992447334581300512508825465773880798288272307683989638417146518341759409532797706182846677683088799389298442913402623990449375457033755593868634385631727615347806721806133833528169502472979214964819710255598682819988670354516207520930840846409283073132470934614504680149148109547327387128, 4757198203620517143794765267604910493095795311094844413566274009869422815376931718621111117720580862471228813640782198531229515409492088342716220409459294106798101497134472448055953391458449615655883569377639584785792037490637008896514256848581385592600392551703912018079100854217522198951577317337556739332611249483750861591471361102817980105618251176982532225925868963026374151704775667344390422704242645383621060217900910676145748677959579644075866382652086161488831984079972317159657461445978388945681856038986811445908140377206321348009622114851489781036278426519737408135764885954436938515738043892580743425673981360461070462908536332822794776088234668628449143981506340546641308234562402879135337884598144313548476080080962124542821840798480021922299823316621378339539256908347988338628419046446674406990757549313633108810078738483720680863724859040219773337068945695687121911253430253587301225650819603987822575293873532089535898090592951682697252063802367371242789695773831799667985750759719425970425220081258951184137162408616858019436997238183928421723980296980798950610385592319308327154531476138800136312518846802765954214365914041476203757337, 6260271268368706894202974920946115816115188845950571520120237970780456710181625399191815712263295472756034586427599379898262163506345593709273928257662728399380574888160529638378436853600598725534540806652324850389757476281756735845783599087526351180190180139943641017569296099292328888806237289130258996981708670174820278524214983689399448597554658220262958254111796900005957872836524047027248224009678666687059095250936810852151693689372463475871131804815995086151489932749015367503707566646168543559329995430826214785289399237561801106879050821209356674239156802503644079619246307005947499697048165246090399224583386662856418159406153045112389578610112884722561317474613223969247465110876733154365833653766670591182883748950599184597459451023018923986740823422847776477251228945891945110718801722689014727114600716017461034657905080746051450682341174623694412770748416067562147608676787115664079694740229658768883676007735585302992187985545889841844207997767110661190243665453593887637904815895612475962686651476815216373738691281464231603892192258663603805169129206191963018210558191982895602850794384470480439972160449513110567887479836047302452135888, 6161793207250013570797494234756863397687080181041186816510731291567176964871299327425161851000502133616445905545531485092782385404041730710533771516272296260139106262837045978407656569083562960240430143953182872721497919817738097177263894944222857113121363337781621399861405325519661397750650874898849009802029130305463677312304078131181871898101631087128697192274897356282005646008697649963131201254871475995928275305320556086006088128239082086163782197407584036392884463747225854055014943229340033950065532544200471398723205500231850723533281903111082599734091365396955333349482559770719578251813462590706656471763646813281656772911915024807145645116212156844738463959217823508368154961196723637895297169191405377520750927947802043599975698558877410529027492345619645237927808806733871312048058455663977107878895407852707884088540180890336765740110413731459452344098461419475522191143944664261366926729675317507881727662169113782771947216802243911334262937983559135325080238705366056906997256129306810348258375225984493780977743341116832970140796350402745775226375788074753521350783230020812134140236301025901668281115159305901415422206987085370858066269, 5267100693182061105730551422489643540472923253344858672829540425125549614545517974151020398921688128633463338201696945711692006625533952520675663953435215640254400144384021788296437952295630144531875430006662659204735339513612937747300690975152254687383851907004699080078246815205272862884819962563583709162951938168651122403816704823240343148984849052071344742966140663479545160161891038795021005824785201224740312627751177962698791365953051062125124631517160554905455034441596801387892708418733289720382137134217321023480754271334411737655663911742743379367211836655413833046809287316198567758398099507836748909475684560648862129109215885785350168408133761242986824416885584016563597042318941491607601916235825203815086942024474490600481448768349379411212751270310366491544379921291543419341283687345109153982628296204543023859925826685469821151914476990441860923730919468020858122071746051689404035881537671338183844004088076685884238045583556513903826491906404174921979456819918682587206709900934241429913962679932661728908721833896616558835408359984415356236268647069278014603145980640981685074203726122245804585576864570087837482099247739294141035890, 5162462814705830591601757376531580617962980722403860234905920908299226731642697660834062549253889060413582755540683840527590402598309292144634913928493684897634026400339692714877009619925511459557913855424295023769775919308444940184747166494266238050276777931643495773847639808703736355223665406475063566148705548335364296830010828283139460292230614687838615753541726131196560029100050195754636309795046308972667554449870028896291390509825562866566753548725869548300148118248199008659299384530905921374513316080454719000877425832863571720472457086847361813854111114685439836714224053286475965744567790207708742674926310351861894865947779584948049698707673768371373918446778517383025648688912089703505285614188439850563597285583239548312224985023338206695155667114379116735062274283039053343181685187030995365075860438677740533389912977636779534737611121255353144444539805398264156597424296852236178999176280407869137812059519852854227409821361739328382172147484474598330834231253101620464739958721313307557310630658583227970770925442542614938853185074197289765329548898637710934105828092320314995861512401925698459527301008129587508663300976103582691406329, 6649140979338456571158429374761368976760897710563670809989890282564819118295968633253126877738743634574178324588347360999109654250203505446645264243862842773037458910733859532771418249905981724788494047828456297537358027611207564966158833422897801306463678091448651436675177575228180399059770500794299202538793991793715577351275797766530152153411600676871886097072242958098977594605566348348077157564485377174750284601054375434000998831418901922859174972743257061224425971554461206090504739578847831511868372195473605698051924047323926357992639844245241530482169858597053880045908507421334813726840443799059925292152941459743371594065485699848084734048258449842126422825748254943886650245834046000859421996571550628913365757741911805689672613681956053650621171318720373169110948302105966259138646285605526419760870027645621420086903821938660758287092369250162394396069903163040783688282754629702138245639816886110434223650277763762146197629203795536018850536141079818130315726472981011798788145047831400800104941467963560742030587803961011406665989707119203029072724379029255146763396458848588845250860460087705139017364841131584553084261236589840567231115, 8168899029436395364692795593454232091036895599299948532318117116761393743517363132040095717421310359886980194278574472752877597027831839269549478532824129025236038620617032161126275880117012733220663088765166386992128318605644682434157303472033114226244042491860831907943944385264807530903432209485335428051765698702236380741158022406966110626996564136995879680255584735620931684300406112940791753724686246177373719477409443805340508407271623600560048564456186718261926657788265024567080421123194446144350220988492915621488821041300967104356478792251056087399295417830012323918634732984397827312725359183799110612369154471402684865816910493101455171496774742868308775025008426308689577183723449767411860172769412831516068467423654361481150778688163873289257543387795000239433328964159788401420526701226020305803077613816241677014525695074869857889551125509606726969238902042603055324099406019845092024315378384244899067817657498781699847056755756305090888500491550951798253312111755731293758640169004727405603324877175792935993907723035063148626560320654315766808106279518275234003648568369068445294368160230173866752646135861124778765265799548196973867083, 8348630270723354493259182662280256138260984518645746593667609152172200543368791155781610034705382149116073810157083636491593342048500244849992273240870345219139548905864169823740036269685761712875185295005795011713290788619359071379858460522236775818361332781019774889153143160640289498757523950068323648270562870966738306831411512420250518077740866650218710375848351296764798825019680669672283959800438993128897746882302470029554463934996995852294557710390386205753571641443778636582466556779747198127259012343546939196316101726936179678869635657503961280742013966843015995054185322302213840241951308386430130853824474928135500515801416146914710217114055520545329040857808495435760870297028244685615913662379773001282252136567046017267524561778582225767660117427092321259032752810132072409463138045662126659710939114478573375541008788207604185460451732171130915353273180416088674263524187868200290716709009289611552439414244264307019110062959894298787028141363833933954570552640934724192185218839864496952232527292389065191847375759617741353754085474868428783331198953111049699320373291090508097919660355754676246066640628895632143964450990654344557521069, 7726831311120969667286676592403441701512343495771759595629785321550119249644571082006424753729259901152855905549575899671022335982897040803453216794947911780419686187362424073688945148258991392041323175944115695610151062237998737207532655886657783150963960487522312687070992046702312826656154203430943225796164331305527437083199579169825818279603934499581711670668575469548299481488573326324516734333715194276156576911471181662401295110905521344328843364263266129959859971118962804424704413661908545020969283095679398223297390235824761477375366945842800143476151085833896884718691661714630912968013073013104434053458640714016248264740997545992627552672186322557838280045950726482212669932488114974561483649649343351383079229160959763945558229458520499002180726691094328237258488394522243146090593391749685728759669465130144680082447002028407767776163606617586922657685747599033208438283307659679842041118085579668732756550384596900502053559212745516751792471902256165217537009215366998260822980760315269694838384961847286261164711542277930750072577589856553801522064437618672340945384244416472323053109000837918927226504900813896251975043551278638686816600, 8968987938285629240617948467051722149435886509885917763702216023345163109408008270074497543745519530151727556445965569928064735553842420658363105354603157741513670092574436931684427533004293025174123211350576325462462728173969659328044176693572836987586843534848767744838915664703795066304995144232775776719684341951288404229427737359829908086515688446968804720256450440740554026234583056194840461812571345063022497618452164244399064143015908802097217223686160923487482128401427287211150957007532604060924748188413765319265476359003246903423627697147853804755622152986104284873244936617499607798371070741456764348449390632888951118224263493105655590070674764648551070192078583578526360502851230389510368542480849419415776680448771842692080714330462141377172776639342423547593542143697721489001493956464552425938839078532555244925474302588008504589741481918230978326756267199383667581554665587203792785117687376740308864938312069141550084292037723021721526360898235687411336322596033250361165611568719666023228289044833814946966001201457127207654701760716948299453573467357365173035098058373763257492533651132315313675859682126048380654035006075378213512850, 7981300019463606853645352354110454207007963102699814810128329537083106249518020509353881747469691213962041447075534592554800201716395600169812666423547654647216056917036860743064514973260346867602517821548669448924211780932485599886400445610649739421099882097549967866880829246229787450449059971489576015715787410828345050220204978200536832411751040623033858384912320534739748796882552734773421901507215135947451320140935277892450174654890975094402518109597906730748405400748382469679816784673362045356083139155359591704108640141917041597791524174369890083212795202978903412063960807930472386855123567308465089478006084042182169516466820283101313148266686715761200797434844620433263697936837701107747168094805538318176902690905917499115693764028070596073697300767536537007725317688748133781561284802092913444702161405517458223464417714034008377178164362285049507597059288060180058818698919377790553612175874518622793698218102224051521107503886448082425743555552309815616702183003622979948216873290689171900287099186521998579816991709156690517943166036708228475309376571947151063442554173341314451731540846796394647906918189315603488625718991167109109441699, 8053949430128058736708330982906026162346773786951962707477377101777058242801007842181442746054610551608666559611029165144063561614759820757548225059588087313841573148394520309002827216589638275239334793449783092318479700059809103682436713164194645767910291168510557638317105084174050513221194586162203825546191033272816915870028264519751697411957354349165230156480027095939108261368710812419225111377372883532631725062501991104272312271255510050844502441333677751355812097260514749055329520065637868793833688413892473014232649053996112987455991518662251827123549802055887571242792799583110306730355621628302313062996259840244305807273011732866410287826874488872453781710856778871401375679814443520824603580452474855189342395110638273615179938147555840874259012907218023572652847214686130227965586647311515107958064415525381433617475969034987505420603573352140081128608334982896669199214199448709617966625060883419870514753767191294318841698194268723033013941022212971302167731491667809365275966891261708391926440281900219279073115225382752847769857432906026198605226319148466827285645932052675358429203226977659737234434640735112859550455233620742149348515, 8264014184390678459431963025444652884315751112129854103761033650412275599386660038666338159535214473011793266693168650966704085926681262381060690324388830604526720439157855283330104990205531644029394089918099069424195662916249689696331577774197690433979549390480631920943549581519819420554827810799813408453063987652445065224658234644844358306074228160797677340787978458015711304185719485869872732104605633736337011512390062859695704995352867994139390608892491518816458657963325348577277439783308813686552035153580982401500288078232305088325632693453080869510895559823355094604561324011430087954661396733141318517760564290498006961636179876067622914270758203467983997905032905498851751563622883053949650887664160492755038974752910838158810621559557184391008285665891766784390028764051693932492452433301224682101683062283643627198653837174652966208993532825144184381513325438166827346447550241245993804609103053501492425520646699735895117304029788374781093967641293198305409329697345059675232523756122154910323178134511811319030929739178393030120406758241710174023510989641269517397544687595880790143844069641729506984480100714419183377691762015678350855733, 8197614472976564826643805692387748902382231595140091921427785594469933331864324068149454235551122573770580341036414811684536613106059968213702888284610759402677704024532574516958084089986352868577017096762040885501116724262235939059151197407681729866066462454074351781506304299339989509379421657175059631661116110149217564804057413741242286095962835706908328494364207192381721058637591782950789643136832163523709426526975927906259057541081546572431625289123769530148975136874725537772157308129017570063675768362991647276152247376650975772962711727994296401371064100761465386879772102498345755204834897929399465394316365626339139266927057793990428490206909995298467482606929255737515631743683366009509811786534329422317077160491685254071369613377869754622038738489939001839103620135513064060990755038467978354969488776716385110720910809577563738347713062890775330591398926770331780091632371098886407210177616672034004946982883842065582512336197295578641216627556216579933640245117292266648820948174210370438368865813680305270544656236504768163487330733693670528547973330215600464351561237973400164120886675353013749961731731842851140559948561880478230548401, 8834800045593362902198799767369300022092739522708918588280171689107921315060623144724888627556752979723746097152635704221940182971286007100897372548535433164426273846769200240220287132915053772370477791687829680161208845697597533621787205303964637259104738026995995462617548183418397012946969405284296327254644393464208323821183010552894274496412115092034614562901058572199636008134361031066643623555792048843898093422478254031878583059691427616338060028991041221490748234116463103210913627314395598475575722058184148640647150280282107180517686443120464597184528429998726408553161359694577698878579874132614615459966187610014116851090533308075437178769898624328646728698032117444312981110766955362657506174542945555695353565990488401784607316208882111830794602810124866560344910289371341273390325016891951067302834751066290180312170378102920893423076557975854973130215888106050603347435515489954847107514170969224648254467562815265331425648036292531242450167955381484530658763535786676230345545395561448233963471448760217709519041696908041948882219445487445489093869315775219079573075079837804117998658205925582021832384518414608474368428879771984256707799]
N = sorted(N)

delta = 625*2*2 - 25*5*5*2

m = matrix(11,10)
for i in range(9):
    m[i,i] = M
    m[-2,i] = h[i]
    m[-1,i] = HP[i]
m[-2,-1] = 2^delta

ans = (m.LLL()[1])
MP = []
for i in range(9):
    MP.append(ans[i]+h[i])

D = diagonal_matrix(GF(0x10001),N+MP)
Per = (1,23,2,13,3,16,15,6,22,18,14,4,25,11,20,24,21,9,5,17,7,19,10,12,8)

P = PermutationGroupElement(Per)
PM = Matrix(GF(0x10001),P.matrix())

AA = matrix(GF(q),eval(output['AA']))
A = AA*PM^-1*D^-1

m = block_matrix(ZZ,[[q,0],[A.T,0],[b,256]])

ans = m.LLL()
最后解矩阵方程拿回flag
b = matrix(1,625,[11852, 40039, 61221, 5696, 17099, 14562, 55346, 24521, 416, 35663, 23856, 24647, 13107, 7521, 51455, 58642, 33535, 44484, 37656, 48854, 42195, 1308, 63347, 59701, 28030, 31542, 26059, 50134, 55345, 44748, 3842, 33871, 16793, 6286, 39608, 5457, 20485, 3567, 8168, 34256, 25223, 6415, 20080, 30336, 8848, 59707, 13262, 29709, 14596, 62602, 63386, 3827, 19507, 12452, 24685, 54285, 52438, 28929, 56574, 28561, 25717, 23923, 61018, 58933, 27128, 25843, 13247, 39971, 10576, 39854, 61019, 38557, 53816, 10965, 17248, 57949, 7647, 18572, 39844, 43080, 37216, 54036, 18092, 51799, 29800, 3831, 32640, 52752, 54334, 47114, 23999, 63426, 35409, 6725, 35138, 611, 6343, 32554, 47441, 51995, 20627, 34208, 59523, 15423, 60577, 8577, 56130, 47819, 14444, 56929, 38101, 9739, 29166, 28463, 12652, 22462, 35326, 13440, 59746, 1207, 43882, 24120, 27102, 52356, 31830, 15592, 44657, 48958, 32867, 8892, 46502, 21090, 52511, 32619, 22922, 48915, 21674, 64327, 51958, 46676, 12863, 10512, 16039, 30091, 59779, 34719, 14311, 50715, 29678, 44376, 29631, 56860, 48974, 20037, 26098, 5284, 27542, 47172, 43764, 18451, 3263, 25830, 2926, 28343, 58647, 16515, 15335, 58666, 29106, 1406, 33913, 37911, 15982, 34556, 10982, 27882, 27757, 29930, 38500, 33448, 38453, 9745, 18200, 41092, 42055, 9758, 52276, 17265, 19940, 11277, 21090, 6473, 45768, 24909, 24577, 20043, 57739, 64145, 42296, 57394, 35014, 7510, 27676, 33453, 50441, 12646, 56144, 27805, 40516, 3166, 4649, 15125, 3329, 61754, 31426, 62120, 64994, 49076, 40920, 52502, 27858, 44887, 33034, 18523, 20572, 48449, 17993, 31161, 38692, 46532, 43382, 31086, 52760, 58239, 20511, 63662, 34385, 64754, 31340, 7817, 7925, 62468, 14102, 8897, 57085, 21282, 31424, 23070, 16375, 5081, 59000, 62711, 1559, 10184, 26565, 18232, 49036, 28899, 24721, 48155, 39456, 22957, 48313, 14579, 35483, 20248, 4218, 15647, 29873, 43251, 18108, 5607, 16129, 46448, 30421, 46554, 4355, 48089, 39527, 14731, 33222, 18328, 12914, 30188, 59710, 1168, 15763, 28014, 16019, 62362, 33445, 52360, 26174, 25300, 46178, 58779, 9457, 47277, 57732, 22475, 24157, 65435, 36452, 1248, 64663, 10301, 56700, 10176, 8436, 13027, 14493, 16129, 54871, 64243, 36832, 64269, 25810, 60247, 14368, 26154, 17881, 20932, 39373, 51088, 51334, 54154, 32771, 57346, 4199, 59130, 34447, 53487, 15647, 3160, 65020, 19196, 62035, 45262, 65128, 62302, 57896, 62398, 24696, 37237, 52966, 41938, 61626, 53222, 47046, 22868, 3294, 40114, 49910, 2997, 16339, 24335, 8406, 29568, 51388, 13031, 20114, 20393, 38655, 17408, 56918, 8070, 56300, 37248, 32428, 3535, 56734, 53590, 34975, 25470, 63388, 32317, 33244, 58451, 57760, 19552, 5913, 35267, 58273, 33286, 9758, 18038, 13483, 18722, 15900, 65430, 64453, 20836, 35913, 63476, 21980, 2640, 174, 15632, 58250, 50263, 25277, 20557, 21974, 44194, 4401, 44431, 111, 55798, 34275, 23980, 21805, 12520, 29968, 32463, 20932, 62738, 126, 61414, 49719, 62041, 7973, 63793, 44161, 39931, 57845, 5248, 3353, 59633, 25634, 34262, 38935, 55423, 57017, 35859, 32984, 34761, 18603, 8280, 62355, 54037, 35031, 34161, 21867, 11730, 40771, 24174, 43433, 21832, 22219, 41759, 45711, 52981, 322, 48561, 23634, 43810, 51549, 12411, 30193, 43445, 62341, 30797, 32034, 43668, 18076, 42291, 58967, 2507, 3694, 34995, 43204, 55921, 28421, 32042, 32041, 29489, 20959, 3591, 57503, 46729, 6756, 4001, 27079, 21977, 41714, 27990, 32042, 41630, 188, 58107, 56671, 37021, 55834, 28330, 30198, 14634, 26376, 54094, 9778, 47259, 52172, 413, 57322, 32947, 24301, 40103, 47805, 63460, 45027, 58687, 29368, 50857, 33177, 56299, 22794, 34339, 1352, 34550, 2809, 51218, 30240, 13605, 61472, 61264, 46662, 49333, 15947, 49470, 13229, 10793, 27146, 11497, 61800, 26086, 16123, 5144, 25205, 51901, 23717, 34252, 31111, 19235, 20281, 12791, 4478, 44855, 15024, 32110, 29904, 24536, 44187, 64477, 14582, 6203, 36710, 19553, 51294, 35794, 32941, 28169, 33228, 39747, 54759, 52243, 970, 35198, 5045, 21100, 21560, 65239, 9032, 21242, 35101, 34463, 47540, 37675, 51999, 32603, 20893, 48324, 56325, 47725, 30794, 26058, 58492, 37103, 26744, 36667, 57968, 4879, 18033, 44946, 35929, 15560, 37254, 16685, 42421, 54565, 53191, 47432, 23308, 30977, 8870, 50576, 61308, 38765, 52591, 59677, 36136, 26062, 37722, 36608, 34034, 51084, 39613, 57142, 5221, 35690, 37847, 30269, 30642, 34530, 41738, 53860, 62063])

b -= matrix(GF(q),ans[25][:-1])

b = matrix(GF(q),b)
s = ((A.T).solve_left(b))
num = 0
for i in s.list()[::-1]:
    num *= q
    num += int(i)
print(num)

from Crypto.Util.number import *
print(long_to_bytes(num))from sage.all import *
from Crypto.Util.number import long_to_bytes
from sympy import nextprime
from re import findall
from subprocess import check_output
from re import findall
from operator import xor

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

S = eval(Old['S'])
p = eval(Old['p'])

S = [(108032701991161449851369002312715580973354179025631833045125920330341444336132442627369167910196499846245375, 536708156806056194339800940453431360309948744802961091477684592805557756940577780671965778135111037727024460, 1092908539163523128210211825513206434685729471033351288310817570413536030332936913121881436496682004163218561, 319681218899114691143952029933390929281094479463796376994923082695907785812861868813064052001648547956430773, 1491469717762965437203234107675304739260134332073261473787166051408478205091597260393509384628194825690384017, 1373831114788217760848815706926510177900812033455370113335228787592380681943495789200016044894484593753473793, 721749134747261598156945357302901463050568624661297095403296472280731478071009708971832640575096673851818368, 1860163764050401633727513573627217696972941984286848985572281249857942774623702194570023403287105671073489060, 154984136256332584966107344852839904503587225305261779832283480159849061688311452179481908517673432437277241, 1561939838062660892618339034341951346106257548745672265144871883988280932734601893314037783804475701266891293, 1196621210864420273010964492926788183563258771458649486943239707342155163532184200078478415282614629395227800, 418140199208035988378436961769638766691045254816780694434194995467625611261074562013654661647238861824195187, 1566865563381296633840183260419394895718650714211270127110339192873464656390177925048966057251100807853472205, 591765854512223923173381833993118081655482569860165937279009553758243886824330666933325098097909951941773363, 1621194715625482277240801603470708569317091835690367023874070253760241984371512903868391207817859394152312002, 1853919209784660031160850930352771886269300975251430020793116172679096829612113956371814479169815876124349500), (429873231732555141667240718587687999822857219084121172009626130310358943388885080601718909981680593606929592, 696661257924439276997527001346014167032958774864009281004980339623413640279240542438501016146643735870840200, 705077116321796552136313163950148514272481595449062490800965253320667803690854999857493736016740764844951855, 36759636718531135702894811812498288161339459911344005228982773190594494346457316668225373274587742986714394, 199617109272238821758248859791496856102696174698246601793036123989271809739396262465329953679772767556175349, 748305044943665754868843090133175750486758697161694063451745527234017037314999816420606532108167584070014650, 128713556531371763123849284738409764132111189857502611935232398816796618991882300550609541403882964822025197, 720294314730287284918332403206366390340674935575928437196947060809525523697555946855032892796717502508756244, 772169734387893586465583421665818938650077225148817036618409173104456878749345815499342643475174237365342088, 485704538257264318281616202446430879022758621467258744613654741872135241670088891039125785177734123506788864, 1049386623703990774779796004447122771056640068769982963039740391255206084894449612397763605343929886627187755, 1353791534940584582018886955223018991871124918503240637355081780112975543362795028582394093562125315687397117, 96922325977204245215966615509244830479352553017235612165102140203380652402877156933626056845508236232145474, 1491547721205063194329451603221117324835280653935458186449353861087354977686600897202090908965745312062496462, 657985609407219294871212287937819792392394243075603163798767913815753294714053803551989285171175046026021292, 1321750505787806228413096336073233274921046205768894526421731637298008087552230154604733661782305913950019758), (1086778637488893363555155897651776469669479648114718713027748026839195873829973285681739101838980868002956926, 1603798106276423628680411507040686545422004273861779510586832810301991479137460804045160999460099332509348272, 1032596573594908905682883741312054579360541498136380107452641965336593376163298589305748612869488444382282785, 1722871599310215842537874903061856170822910917071612533538758545930106429737859314184812107888570570514436817, 888612741358369537511403754406447724251960233741122239049680647261856619404416530595695189652109281384865551, 272210091239236373983366324215208566923182631266812430374542000868950822203456368709019668399773194130115582, 998340433312163849536880381773142598561110062084017535938298827399228054526060914037893418142610051549344149, 416561209542736085163087421985348135859148177916787887874024056410059456662972557534961467733006653686852270, 12588651533966392617982800355146650879738320880541134139166541021872185894667746916875855764202920352998332, 239155589045658762407997613376641052079067501577649334701928033885172818297939378539262342760726229932149102, 1712700772384296868424330714519998133456916631419429384710641521922451158914619767158484746435503528247198201, 973460793536380374905536216000279457254227413270258748292701993424187048976790644495166672795707977339193401, 298374738199736157379773918814268251577739944514215745671393904924422066180617518790938312830200625034492336, 1084149657600176924628380982516941510886461179594063721146617624251927480674370653365654346812040758416587254, 1455486290142480470333195218741425003901972373269012398794854208385742131684661811551770676387271330305840033, 1317616016751494143133911076475028074618881097289669566979706802061473591757960790365356311174253283568545171), (511902046345644666272587656834397557926585465865594799110299385517243337669760460710245197553437169107076465, 1308330383856237915365466642984283736169698388215802844201751246880103558237647553782829473002257961428836670, 1155713813790080552487939803696106101790310975411071299829183870773444388451785801500623912616242544692680962, 1224908750816908679021939739243701563153232819921843770261166611815141376759933697069591681336679313105729046, 452063111929995491255412240376860357091791634348346543674689097860541694702190428064670811147941474189515940, 243905199413971842010848437083883170120387967869945489727874891785274619523120687843469628111008333520281173, 218012047981557163160906385736965875971834228229268545141409957804110200175228120318440102572613964108852241, 72449390352553126882641989616711201258083728722073811669248333042484356858555217373026830154484599675673166, 1744077638109996915648335389542463821997796324708102976212623303084662144503419047177392858024029202496884056, 1562406863302128494306184675628052746736729226148455257287537831013528914148133192444813931611184513898761964, 1370809565011874548553736664131319308120113144756404775592948258246558844114463308790143707574202284352297700, 619582693502976159201142244983464537147959560539005191107859790886253434688472547727851180959778494649468347, 1439935211405443869676158269127460181688799184642555475680575584652080501734744148715596139324976221138373651, 90545837187619363498470568359275825840618056784074308739892174914423452949587594590059370188451502082946781, 482428410735918416738432316622337711063850733413329084474254412765173029163913604186737203649136909991911512, 565434332235923074300308595897761005070298372508007151970717410598099167866385478749744466175454834261310565), (104491799965715411013561142125662618371589863368220043903880063313450364721340353778253423882215372628063760, 995180834506623008467226233521869342403315180509957213686517153423463062453889353398616389051090749137685843, 829565021944997397018498002084161459259275942202921212249684154592702614408845709428138511390580330061002946, 534327621921588874889149990448038480344105599605667358128347364437354685222101199440058722509498308377029012, 1132330464934751558500840836525167035985136508412935213102713347379055094835345081148822225633094652420795588, 450074048099726665802238274851908045566712843397793274051290281351600335456664818882443154184755479919306880, 799650301333724197381856809928105802660976183437036834013098030038374988250871838187978763436682367937424064, 186144160986287531641216966101956370994842371362686292130413967390643062283174363969086648192162770707299860, 908534860213206841686157605935550514698866576053159893786895113561156202467655121726907189182979000098180930, 45172777025563801245002587177051647086647015775396329903238685443215301743159050121404543533110450927794409, 764812910167477106544110492707407657402757978897081341870134647618267941562053074583099500973988509251503866, 725981463002339136952211983895345042866512126776025275961573441253428056712570870615698244996644709842695281, 835069084199672363874718204938215438544707590888115425961659825606911679990035477671978178973889650313585055, 1191875778351256270634615082284082976487567969444268263184598475937048145998543269062890189570330392643703428, 83818590739829464348451185348616535829221962242907104691853650713849624215858867979607119022934848835272741, 845663971836096838373625947207777962185246822459741259152503695147222855185127535612579592810063372388393425), (730080740708716696869611500305945729582831639692674576181815669256588053495445644654846273425696381106798213, 1211401865625606862892141164094862255157602687290011401877324564094913451780788011572602838694851127273686199, 761750678069382705088989341593202296445602247339072406661067951708499074600129843633749860027539961169263821, 958488935282214627573417363369674085278816875474745585966084121728154471973830854061042022718110987983758533, 1000154070884484290117374350945928521584252400077614217868317402688302271277639661314255973413082836976423525, 452737780943126759615159828372843517970855322695027226969144987933644903011529013014573924533431359051256850, 5805599200676249107157522629732437488517848218120336534559572461215244230092132165434652875158210784360605, 1069648823350032633271251526144211153517485574227702676510205431642788090278206667447057508392521720178991564, 464345016404000464145764099641622835761022772300106935701609296071422986154529936480523330102784677377267972, 887532013540448997976095141800168404616145524208067918411064213199200246544405630618505727647904031437367765, 764896944683051632934376964111352690545726493595561980325842532869416551338993800555386022016655600198592863, 834595492951168051763345064768685082923666710575447603461271875560636579185091403924607285606904089495798238, 97747066740378772563805036049036560981941178276358675793741851520890271416061851970734762331332677029558286, 1291639614271453651479090561671509420789047119165785858217334853499388375967049382736266913449874753320474210, 801271538360332225899343978692624588068282915247341176248413743892071353524747855777605347936971072256796883, 583118453726128867307239318601314573717226612564585476755251111771273736693625440352334611064633212563236599), (1007558687762692623401107502108785671552540294554027553075253821535448496219183688214829259558409405603001724, 82954089525210775107785196754975536343868930175076975506233700714273434584908468192257652423060749000141288, 427447460947692981480247356494758073766902779792449397588581408107838459193575936867213556781504157624146419, 1374117754996529221098536377009433889631952516241548318835190450059797631046672640835049895872866758924481496, 156038208432623159135025608204515658053054306527311311313875093413737186414935362808963926062607056191492625, 1515640320653109406794405070206667431846552825063179966889387609909437205938636205039178430345232101643703029, 1001238386683833647397450794067318370920199592087688426532041695022589977781759577351271154279661457711401139, 9286812100870995351874739983837536749531703373251036760857092007083527341690165710076770799982026349469295, 781398522411624239036136435439321625771428352649403511374119891867804110627699867915291152830172439999673301, 288390340485689855297713282913031890061650435198757756679240034152731783902546010542111152853837802947107198, 1282499438978850273310621141487984553225042108684339648738689012516484353852213933474138478066589426905792640, 1206882588472439544838766692591222446845991327532088581599851103973276440986865610584267969223571059209838017, 716745202356877068654799969764658910268422168331996123562556456205494558399089053935448159249370428497961068, 986593095310489014203641425333005980037776378229232672361107883934927730326718162983564623505526232068548290, 103772617718005675720056677269973171337468439536802857689497610845701001446000293596756576084101670871872394, 579163101347014044284264738999794759737770512095227857962630915400460939984272909004056647376161945305737747), (288435034175969956020092056225392604045743897118720404871671986231084818165458292729640648522613169661689467, 842274139270535842409744945935128951705359842639982830775234202022927766509101371734465485773595508746113280, 700418817778098786277078342411520118692346350422606462723911114006419955720829707854379756502697131673319406, 569340337737117832121418471593902796598875993869214230094417664010492029193566188439149404136072598861993782, 311402606048606137904298548604483824215396754817621627161525397920627489469424683846450586021906438112211863, 387556851872999917791805837107172465053410831946704411441234136279016670150248420130484443911023416474044825, 926757025438911433753408433626135280565795754689622472147862347099349687223800534911582014085258437224209910, 1200730550518343100475397485248562827037665594135578219083390443869303562262076428424675489345048272331540918, 853763541787064913980724960667413489272081221293636460056478608052421032518647566798408815952868230194038338, 101239479653925653679074333030959394747942224986065362367651805089673854173857409456735028763240747273162552, 47121618175135904684072490541732295428491460965542084558472179206885868302518875995103252249901230211543525, 982857581226299143840954166901835590289581958403367749920630419874452320611289908335828280671343750955279622, 811158165015249537987500368246254094251025296798974323499510891442047224515941233490537351722658420472211406, 190329661527190452974427725241771623761097473044383743958766087362063693259351495833117766854793893313562091, 50142672419825251936694820690428751885608034385161146860936149367718248528534064819383444639850833791987235, 303074295943054006201261314482928767581154579713194119273091027835447157940166620065183762076400863876771618), (1079372098255337688887136508726900390205048294920188450514628679918679463674406107209346812192726950726526095, 1185407402236867425841849519771446165946457212261250741849109704048981912211308244902430988525473241626691376, 841449701483451008458666118133003457345663684791358742412512477100467235117244326687250726234511967835213312, 947580146274192515572496516072653825873017616320635389497290350126027652146744723140627689652187761111324722, 119701810379427632902947235248083296107591243190851146608219622795996254840540272877119978122901453247704831, 1640347806216480803403265325130213955203137215028089484587105315192029771752510728839945151370945087147585891, 132249802108051544701535447313025681301951421902989862817119883237200082396640574742757738128092983379391192, 222015024534828263520557570979535921258670062891839524631837193227865004386250245701652729081402110107343213, 574045525239164646488552167939702566130627137278663509529342693657266762662320399075679168964197800875153680, 9484269602968566121096790600370029517627994135450856762373752676667516556085799114664479005324973494415028, 1233903272461676350245321015676982196376541150525344451565454505261564207710591321827100801836574162863320101, 1148801053084576503181167454811439762743688828522853724573620157831506900806010782322188583027710897929400855, 1215932391694160648245705883928262594648092322383337933840246087760359598672361289173906269225985279432329413, 1256312697161815430876406109440773985803220898059915842809050363551861707962446265001460104545875429415188571, 872437290854895473828669647489120707661030662446214686039744557281742237010820123691242130056373279816418223, 1152504352689745273833849365904838499734041820598612058887413417408375952316351943382602922195063490977108643), (710963262741981151820936850518208399242203827946566243778081082652103950765186323857775548839335091162334870, 1456629029412002617034972369163460599977456975519008830537020404598366361266406883048353122402136998033965378, 16210930934876839488825850002875991819998003905202118064600427478988072592144130697157997625511415256307363, 270428172771482397506264701557858536676609324837517143183553201495149542640445267791184678417415736435998954, 849877849071009557937204357275192288430487696593090949890966075681654171368216057356945570659434491278721274, 552620920720515058560474932264018680445939377267909570543604994142303109067032086804888256059644299353469259, 1172127755569012152057329884978219429036349809157746825385122333254835103162162825165494896169153369293261353, 411671306380066471819720700550244415062425059661769246453503317934644249097679366952285018648871841314934569, 402751953198228508151317654119142703515415046161021988593791144762527354103153471097112572211022718546278586, 766801594113742202593740150497848890462669867082716753718908389103589627909820578043565509568785779049218055, 797931710812718040702146757192489993108919934337204902859533844054220052514095634360789107051511556938992653, 256266683996681594597141537434560889801561902972841661123996099001842861984074656394526155375881352817334296, 1418258257142479430747867834021373209498823909476696372006454504116466387484456504969162467214870003218548093, 404210566834668025438526175366143398913809348454169783995888818764258941987118278616050245839417646478639395, 1124315278703311203910253162758503257319860043824222656290539806527988308952238570582388061003539053283572317, 31271013457852406387457908247212294447150322908910202024391938488810830594827404698941451758903033151739305), (548040572051344376515276589131924583544500173392618971080814926510006336050708851946164444215551993653085559, 625548909252967533735849839010612868036138065774462061438762751772756816905614389595526904873401107330945781, 1691072562255106837879679641865899852020852750546650376805631545200564107660856702442704801403013254039741569, 1202012272195706005158418331650181482011843322779113997244205689517798278846032040147415770067172225826668913, 150921370600945669819511437694954238255973349434792437308411767994329401311792429847861423651135286847713713, 1081961677217384177165919288637329442102000700465921211931830210416642976436505857583147668075896913252875900, 38632177474960713645129923487571475415432359356662267792821760890850300033591793689594738256015530177371155, 1938890600587173893505401800316209462990331410030406162509017807707491700220029026718794390924558159879325929, 1229683571480518162665771834260511788435892562017987248959417363680402504200735302566356076064181245050609719, 1413469344912570390840315618128490201700779301153932364796221898469284008600385792913106541878951550172812412, 1603029001236324174565529401277703840486413251539616667351366375992862845333710947994522282396247706689372612, 1312758180969033170349160258170632626914169138097284308377628285441990421588369514659056847472785376422032509, 420630504359244172568640650703118406520051803679165798526263777300947905179710846980565379197700977880435719, 1585809275814789433535721083967397645766740283392075276186763802353434721723652579350998943546412586002101517, 589210671463132192681719552822630237990180990772437934057045440386799228059672695104509559337510094293921851, 930311739285308931463277260997251754864363249024137932070462953287695059475197620094345118725029808434080647), (1467336759171283069626565411462398975366496846832073813368207088887535151209170863516635004538662162471343762, 977074540452559328447962038595860262505507375287943059556072116746789487913192871746080153669811094853532543, 248650173456825688417957774461661449303260122768178786152237705032396522955301949686829800599729957124936881, 1575141265084365943986079682243623659177381136848989044089310647747968289751919614920688971461354420388159314, 787447705570464488319993501786605650852712556006717975039783792984896866011280674498846348134268287187830884, 661441381812931924846748272167364237789611518544035906523025481686525617167205320161832280314277716928159938, 713730377306644084040092474766578448161880233899851837176624863065798544631483002502432026196641108684529802, 678127349747227597169480575382795227664094828375789580467264872090685308013465629197529880718542771111962085, 713346890417527875247397732148633974225980066787252539001278528256033329879214523269733008776540235645258616, 247766390946758644831951312737583234549767619079720848362262835109239728499038516392540238454397695238919141, 222705566395366047399107473153762271285577494629225535376316438586692339782315068484531721893605469117790911, 1167884170034239946155932241100371322938666487622727711102849910832028974675686714637275598120136818289661580, 932355528178259401857913753619901059996671717365121827133186058111555002840548732397926137817560930059114770, 1002746708088820961204612547451117005094490428961711590997242233612795804195894564433549670531755192704377784, 1679333740390330063990893123547127749235201034112770813357092856319834835071400803617023235189669738802029304, 392242968045894054394410450448222234277751637234090312939171392505401592465971560873369509814497556456004427), (992468551424268052973878019321034098395629270356898670428754992273976085327043949634823897407999881749733525, 1451715409910944943601462101816705970560866315969026142750871006351008564752030350792755878689749793232050135, 1157009611084371602570908328606510003229611538486635093673400888168806076758399348412361589040924760249605165, 973495747254748476179115555073571696121985220451730406501150178959729503505597527610925614459285006121361402, 658639350805308777150470408771425787492359455148463053354655386025849573731791445060202388386991444927738961, 1971053413102762878789808762083387327923437569500667206884595783469944908304113399563798234198010177066652742, 2115317009351535055976145874152453249874377928041776362924821587295001750589961370153217409957345893981016872, 2234391928340953996585129136832544559226500428847567089886903639518503721330552899247101854148266339819317188, 95072622447945887900832352837970706552989337874284483457123454853555569418515739360750605423996449645105107, 1875846203425953685568066514593452384199151872393675498259844146377412020045792635132008533335688986283672883, 1810914367567014038914603180161768355184164085528312813795257698944266962072856602341302516572423400651692332, 199467426284808218867281478238942162630473707920489559716102969301577891302451826382304815567177368764269462, 1702858806121853895873612873027468484445637308444414982865712291274495592467886617988854786928674988921911946, 974805688584434752190621523541453157436916884469405725317513726173004242595140529349594953961249312833707385, 1563386402665143107620951148197814309632711706132670874925320046005197489375705725978209339748911734754574512, 9176208496797520354591828022203217543780592247378582726844977716549360683455502116572757173493442942031259), (233445330763035713906480406558126679912369584387609168775775009002471869774809156648369750200202982292450110, 1368815767827926042586853692745612271551227815728536321062147470922660524586014022932653135440512072849734316, 384817387960742369820850831236493763489057262900417346331312192757646380527152649103439831363756430268212632, 397496835668788385513140511380523318193705211763259441405319027544230424059467351506182237622329904982387715, 698110549303594315292020493881564774109817641862010152125384093754339939993582331419363730859850611879969915, 1605164779311866241282121191148498603150640021145381378570376215574622721447700807491428199428586193250231478, 183289800466565443527759722034380747076340683994766781001250154775016249854621154061869569618175611639903701, 1150055471085650022911275723850717353026238077245380241936809820048468325748232815290091481729807017284552381, 620603888284975571831631670369627892585626390577575455138594479292012594683550062832525870724842983985770747, 1141328685248613112603867626739876650489649831411725855910037151420885700357073101388703693467739668094282156, 624960745989505135902341328405609018059617712001038139854396706552761169916956343895696631019491737540425263, 563529618847514880940393862944843314371586107587203186648893576096997599582868166110130990825643297466007343, 303984049882076688174095718097426318142423827941965036899905826287812216266056955154997043369442371230205564, 1078658398740303308773443996075991099257452827614150807223915130507432012180318161902329283469259552998132456, 537873127629863133215961576717191616451542237544837768039490490426253210893390806083040946873190554913432278, 169827329251258085772690777190607029224657639816497950869244582534669264355479002364217211861513540611966251), (1096245533475537361190288774520023066028944190947416838212035157548679351561405521968403358714145944584630399, 1279522123404803133336059116798495103535564541817111467998685969195461307732488357939481563472485600907763277, 1621837589082192223743462826999866153643367040938611577504635652882478237855735236683796485402281552828564582, 313242446386229290517631456915969842064339663908557260803068874835492915635010632958561104764179416843832161, 578485247743964493116232317100459206200994787373794324513012647234668115712570705116452853082031543244068838, 219236836922423209713975639747607435338261033480938547612396078378825597472824554607631157060224948270436605, 979376137173103622620811921408735178993536617946054941969002748851996870693909895946038600886242442551160010, 1658962387074248584465660456576639004572633758113833020219450181488960527172176749430939869777912514216215008, 918251986210568868284757564587914989414930967922138557622606681330218265588255276030855013898182774363764198, 416145177416426209139713794767532287475150472389752288032134927843857792069932225643904301155189056410493405, 1346241144466810519932765660177492393372766698799833323172412119406803241967611867883756378782484642242570189, 386044859254038630462329030959102689573511312525928529436140682252354194273696092297158967704938034048108529, 1484764098293658918774711805629994556483924451761564995022607799099721232009570720017552575816071384460602164, 1038730041745536343360704248505932016034663062624529750511404210052634999557834948325392848734950387651599858, 840891087158618754558051176285252692949387956006228734495878738266601769957106869402114856213091762226629917, 154290307227368077749870332568887647430659666317555291698382581129904308224189689828380085709625178546228569), (957542186457140429878719718043221941900755820226325043983141960244787673981451575491224713734494596866261378, 724047722558649330730843109648231137501160718812738945124027170000449368988489179074784908592741358980048275, 859691367287711190756246276405852338601741033988752600016986903642679515575127575700961271435459772059797413, 700326697100002173963353478913834231346709568898840509699454481415437420831870839656574933271416282890802499, 1212799233481683655114268450576868631340238725268953631719891739166990447791141389709487362430025981929525475, 434223116592471574825271824097577518464718630519588487323509231423950783528915761191895287228657263954146704, 217358723385922851738144743498951415510775556931588600580907447804579013546360116371411758271211755732813673, 1298302755143305654862242351853763864348853855493677603188749853805882418947261680899385729883193441043359755, 1068567433966576654450031707464914827557285166837067988549886717564803805511104947509349083926244852733075655, 387252452536150691159164650119964238247624960830148325826046315786865241210396695679059829317531866257898261, 508839717431096857213637104691635167536835851969398382071457470260649594681556257203954946581750028844005177, 1206518168075280470635211428031620060153968523722913415228454624000108732714232864597004081584662635882607853, 648865561108057369649107548455893267620716326822663875048533849791081284682513605169317071254138817423411253, 328899686789173295020724462964824410189118431101862924515424446992402687451336506312251501354303725597785390, 328255320088054790647176014272991149866112991817392189633550739280062827106546437881018772832904512686978965, 106174800100391915811859026646635920353821529620342998961153251213838054034659090497687918002957863429970430)]
p = [1865995351449738305568020175407782211399961865380593201418385016005093079577037578689379305647217584283793443, 1697242394344178603938736175613701840668178871025357188746023984007769445558252186408395718968869377260650881, 2022468188670479218398009972496559844211210519349164350277452667428806390007291454178121579812497234805510519, 1834829294267612129864230457016540640249954796220974248612636878892248451710372726854088698756567786846212703, 1405518966688306890692028628042659763908744036265874596824103451217948291402053599048649577166902926927583703, 1306908379818841354811802528108647022225114028771004539878749636527088666316005228226849317157868863492789557, 1616789308818449288058724288899930420024001530178051122904515573455195995874365002006013181396637101496249781, 1253980640197082323669506507875908153359037006012151867601133670891700927532100671469629678831658698780894267, 1903682307023943435426747954611546184832717459394865637878168715826293943923848159869800611686232172365018581, 1456734579850607615224565915938092349853802772768941452254929266785318676489306434153019311316107310595518281, 2086165420905105719392664388281307744562262795619197207857331245823719830703952955965374642455778791010644509, 1726023515056798169515795231206459220148735483137609272433351313501296592963022379572602085340729076332028431, 2321143867752465622995689244649230653121108609695672723739436709976291791473903654863830072020811159448364217, 1654702076906300292576294228173753061411836852146848089290417136859589687837314338726356779964670865195828343, 1907313129296467305635718505435422104472615990939772968829964204948404573958217594528354537082412412899627617, 1320309629971476331896561625690122232816350401607709796615097327024821433804124798985230849347309403103099677]

T = [crt([0] * i + [1] + [0] * (16 - i - 1), p) for i in range(16)]
A = sum([list(t * vector(s)) for t, s in zip(T, S)], [])
M = block_matrix(
    ZZ,
    [
        [vector([prod(p)]), vector([0] * 16 * 16)],
        [matrix(A).T, matrix.identity(16 * 16)],
    ],
)
K = 2**3840
M[:, 1:] *= K
ans = flatter(M)

更新一下：后面看到了其他师傅更详细的WP SCTF2024-Crypto - 先知社区

题目给出了多个数据我们只提取主要的几个数据

#AA,D,Per已知
P = PermutationGroupElement(Per)
PM = Matrix(GF(0x10001),P.matrix())
AA = A*D*PM

我们通过已知量就可以求出AA,D,PM然后就可以顺势求出A的值了

t=PM.solve_left(AA)
A=D.solve_left(t)

接下来观察与flag相关的Young函数

A = Matrix(GF(q), m, n, lambda i, j: randint(0, q - 1))
e = vector(choices(range(2^8), k=m), GF(q))*Matrix(ZZ,PermutationGroupElement(SymmetricGroup(m).random_element()).matrix())
b = (A*s) + e

这里的b和A我们都知道了，e是一个2^8下的随机误差，那么就可以转化成一个lwe的问题了。这里e还是较大的，但是A是一个625*25的矩阵，数据量多，可以尝试求解，这里直接求cvp即可。由于用上全部数据求LLL较慢，所以我爆破尝试了几组数据，发现在325情况下能够求出结果。

注意到这里求出结果后要做一个65537进制的转化，而不是常规的直接转byte

sum=0
q = 65537
sum=0
for i in range(len(t)):
    sum+=t[i]*(q**(i))
print(long_to_bytes(sum))

exp:

m = 325
n = 25
q = 65537
A_values = A[:m,:n]
b_values = b[:m]
A = matrix(ZZ, m + n, m)
for i in range(m):
    A[i, i] = q
for x in range(m):
    for y in range(n):
        A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

print("Ingredients: {}".format(ingredients))

from Crypto.Util.number import *
t=(58903, 2963, 39256, 25173, 62086, 5284, 45419, 10132, 50811, 41636, 42833, 8227, 63647, 10096, 28276, 29628, 54509, 9776, 44228, 39961, 48996, 60060, 43678, 34392, 21307)
print(len(t))
sum=0
q = 65537
sum=0
for i in range(len(t)):
    sum+=t[i]*(q**(i))
print(long_to_bytes(sum))