题目给了八组如下的等式：
sum_k = \sum_{i=0}^{128}{a_ix_k^i}
并且给出八组xk的值以及sumk的值，要求我们还原全部ai后就可以继续获得AES的密钥，从而获取flag。
而注意到ai均为64比特数量级，因此可以考虑用这些等式构造如下格：
\left(\begin{matrix}
1 & 1 & ... &1&1& & \\
x_0& x_1 & &x_7&&1 & \\
x_0^2&x_1^2&&x_7^2&&&1\\
... & & & &&&&... \\
x_0^{126} &x_1^{126} &&x_7^{126} && &&&1 \\
x_0^{127} &x_1^{127} &&x_7^{127} && &&&&1 \\
-sum_0 &-sum_1 &&-sum_7 && & &&&&1\\
\end{matrix}\right)
这个格具有如下线性关系：
(a_0,a_1,a_2,...a_{128},1)
\left(\begin{matrix}
1 & 1 & ... &1&1& & \\
x_0& x_1 & &x_7&&1 & \\
x_0^2&x_1^2&&x_7^2&&&1\\
... & & & &&&&... \\
x_0^{126} &x_1^{126} &&x_7^{126} && &&&1 \\
x_0^{127} &x_1^{127} &&x_7^{127} && &&&&1 \\
-sum_0 &-sum_1 &&-sum_7 && & &&&&1\\
\end{matrix}\right)
=
(0,0,0,0,0,0,0,0,a_0,a_1,a_2,...a_{128},1)
然后为了保证前面八列规约出0，并且最后的向量数量级相当，因此给前八列配上大系数，并给单位矩阵的最后一元配2^64即可LLL规约出目标向量。
得到所有ai后就可以求解secret，进一步AES恢复flag。
exp：
from Crypto.Util.number import * from Crypto.Cipher import AES from hashlib import sha256 DEGREE = 128 SHARES_FOR_YOU = 8 shares = [(41458, 3015894889650529600470920314593280408459518223054415623846810748413393737686521849609926975694824777687791824408686652245102687392987299828716863372946074882798754477101786150262288970710451710086966378817944448615584285684364802621112755627795146504720812935041851556318832824799502759754100408717888912062197676588256634343721633045179136302533777168978134770315363985448879229514802330846792965525004570768212871252658334277172395338054448791891165981203069346039654617938169527772805687564575525262812469960675835101499054296722994451502140787064163668418661661374437567033971648550576296023422536253955229), (3389, 188433716494377932944071544153838579057591833387651830021721770473524507947811754295899393634645349682360212761145039355690817927625249659010181081209481357850193656763556243022791637306094953982811471415645267589939465925098159204147714779617946431727015863707468081949286110249296858079354949234074465541940264775783884708819566758872542606519408358277173683256608326688673226933790117016596834640875497643330432185114931410656582728964222203181026468387428893233826461), (20016, 100434774699078525844435127144579870564983915777345068724291926367405061427748836490810414860997895358378538088786283372231649911113841061354335739776409724471256377867811133591349442950556374825868587940833009529662869081130218551306459690738900795035660420986807973542512081415453215211908130387754214098414826747340962722685373241806099462750595976574593799013733614097923338311883793416643213898201680852118540438376386415411317989072583126108177482838299109479175882214603698768498421016054035672774286507312986602290254323930575001551875601243671354491241420409219), (50683, 444545881882748849210617532697661279371689521082184772844723908765173319859389018743414369945234307906596253496624659734919646710483514374218993496994560985318096082923429834553341897367168830049334302307406087637232329348570485341223211629167329394484624055745054495405880099706580380696671879365741197827080224977821589102425678989782880274304484630899425664722718972847034030888019348402685383311095030884356731112886316823960378572796288532824588478234949384868912708000223119984161992105752059185137674711077940232530298853451166664700609238496874366152042676602089571801873748042888046623717879084695143810047335029), (6445, 101461065764578261241074518788237888467081270902741849861528201922043223477790661159690684156056890167304291810116447916457265705130707166062372766839626095333813681671546097679623755546322833727082145873422243641505450049118758544298328784536759107951763715458884889255549767465897671061295486677353893450789955616926292534325337544782386120469581214993770910137353221116457111551538222138388416162630076391624447865248920466274175229034129561913505977209131490066291917549232913771218316393849495621818397), (1359, 301175604076484656987097022479686300460199620068959954988990822483114048418823291831080744590394713639405681060973359346474547015206086229256524657214311815578895906855833813636970640902962286472992468394831014254279137613828904924898823470285520515090889491445149243620044782726415898188702226878029241518020146726699446397961112596830223444821094650508662477147134721631935528182772284099429814417490160457082241680661), (45286, 244867719210730952183489456726726432791149629831242968845409984537752132549250274779516590253042559196452609852176114909791657154092483479876795482861784431886143414585698773882088948703730268947925790809436449512089696895048994874003651088538416399435467483409931121063976149037130454114161175715871108284419975118570732022104749321213013756795645219060997019373915339235627535694458093194617642834806820772479160496966470147893963746139947337914575231526069667124822677688977724313174612816604463495630041075005651663546036363128325535621487658461744362098985183050127661470315454320073092665472364666768205258769), (5649, 4766101906865350375503575239791521167258753430948472304582908507542293595346756303331383584550516424087839316050412570112796817549423179461056531056102741963677007097061600281918678364910813585444151640384802648969082273001142879806475184857246441212406056540028447374033197873299250076862108042582790928405869475508762352345569281589853917902601519294573327847401601789315980414998055948162169170771240383220643819333682845459742335249254576151835966500230706707674854493184181354958093926469960861)] c = b'G$\xf5\x9e\xa9\xb1e\xb5\x86w\xdfz\xbeP\xecJ\xb8wT<<\x84\xc5v\xb4\x02Z\xa4\xed\x8fB\x00[\xc0\x02\xf9\xc0x\x16\xf9\xa4\x02\xb8\xbb' nonce = b'\x8f\xa5z\xb4mZ\x97\xe9' #part1 get poly K = 2^512 L = Matrix(ZZ,DEGREE+2,SHARES_FOR_YOU+DEGREE+2) for i in range(SHARES_FOR_YOU): for j in range(DEGREE+1): L[j,i] = K * (shares[i][0] ** j) L[-1,i] = -K * shares[i][1] for i in range(DEGREE+1): L[i,i+8] = 1 L[-1,-1] = 2^64 res = L.LLL() #part2 get flag poly = res[0][8:-1] def polyeval(poly, x): return sum([a * x**i for i, a in enumerate(poly)]) secret = polyeval(poly, 0x48763) key = sha256(str(secret).encode()).digest()[:16] cipher = AES.new(key, AES.MODE_CTR,nonce=nonce) print(cipher.decrypt(c))