周分享2：背包密码体制

背包问题

设$n$元组由正整数$a_i$组成$A=(a_1,…,a_n)$，一已知的正整数$s$为$A$中部分元素的和，背包问题是在$A$中寻找所有的$a_i$使得和为$s$，$A$为背包向量，$s$为背包容积：

在现实生活中，背包问题的实例：

我们有一个能承重$s$的背包，现在我们有$n$个物品，每个物品都有一定的质量，问哪些物品放到背包里能可以把这个背包装满。

import random

list = []
s = 0
for _ in range(20):
    i = random.randint(100, 2000)
    list.append(i)
    temp = random.randint(0, 1)
    s += i*temp

print(list)
print(s)

为了寻找符合条件的组使得和为$s$，可以求出$A$的所有的非空子集（$2^n-1$个），分别求和比较一下即可找到：

import random

# encode
list = []
s = 0
for _ in range(20):
    i = random.randint(100, 2000)
    list.append(i)
    temp = random.randint(0, 1)
    s += i*temp

print(list)
print(s)

# decode
def subsets(nums):
    def dfs(index, subset):
        if subset:
            result.append(subset)
        for i in range(index, len(nums)):
            dfs(i+1, subset+[nums[i]])
    result = []
    dfs(0, [])
    return result

all = subsets(list)
for i in all:
    sum = 0	
    for j in i:
        sum += j
    if sum == s:
        print(i)
        break

但是随着$A$中元素的增大，这种方法消耗的时间也会大到无法破解，实际应用中$n$的数值一般至少为$200$，所以难以使用这种方法进行破解。

背包密码

知道背包问题之后，根据这种思想构造单向函数$f(x)$：$A$中所有$a_i$的和。我们将要发送的消息转为二进制表示，之后写成列向量形式：
$$
1011011001\Rightarrow\begin{pmatrix}
1,0,1,1,0,1,1,0,0,1
\end{pmatrix}^T
$$
这样可以定义函数，$B_x$为消息二进制表示的列向量：
$$
f(x)=A\cdot B_x
$$
向量运算后得到的结果就是加密后的密文。

已知$A$和$B_x$时求解$f(x)$比较容易，但是反过来提供$f(x)$和$A$求解$B_x$就非常困难。对于$A$元素数量较大的背包密码，几乎不可能完成解密，需要找一些特殊情况，比如当$A$比较特殊时。

超递增背包向量

$A$为超递增，指的是这个向量任何一个元素的值一定大于位于这个向量前面所有的元素的和：
$$
a_j>\sum^{j-1}_{i=1}a_i(j=2,…,n)
$$

在超递增序列中，满足：$a_{i+1}\ge 2a_i$

贪婪算法

贪婪算法是一种常用的算法思想，是一种在每一步选择中都采取在当前状态下最好或最优（即局部最优）的选择，从而希望结果是全局最好或最优（即全局最优）的算法。

贪心算法通常用来解决最优化问题，比如最小生成树、最短路径、背包问题和调度问题等。它的基本思想可以用如下步骤总结：

1. 将求解问题分成若干子问题。
2. 对每个子问题求解，得到子问题的局部最优解。
3. 把子问题的解组合起来，得到原问题的解。

在存在超递增背包向量的背包密码加密中可以使用贪婪算法的思想进行解密：

首先对于超递增背包向量最后一个（最大）元素，如果我们得到的$f(x)$比最后一个元素大，那么就说明这个元素一定被加进了$f(x)$中，因为除了最后一个元素其他所有元素的加和都不会超过最后一个元素，所以最后一个元素一定参与了运算。

如果大于，将$f(x)$减去最后一个元素，继续用同样的方法比较倒数第二个元素，以此类推，直到最后比较第一个是否等于最后一轮的比较值。

在每一轮的比较中，如果发现这个数参与了运算，那么就记为$1$，否则记为$0$，将每一轮比较所得的结果组合起来，得到一串二元序列，这串序列就是要求的$B_x$。

代码实现

[MoeCTF 2022]MiniMiniBackPack

from gmpy2 import *
from Crypto.Util.number import *
import random
from FLAG import flag


def gen_key(size):
    s = 1000
    key = []
    for _ in range(size):
        a = random.randint(s + 1, 2 * s)
        assert a > sum(key)
        key.append(a)
        s += a
    return key


m = bytes_to_long(flag)
L = len(bin(m)[2:])
key = gen_key(L)
c = 0

for i in range(L):
    c += key[i]**(m & 1)
    m >>= 1

print(key)
print(c)

#[1928, 4648, 12352, 24010, 58760, 148406, 441469, 906294, 2347544, 4145527, 13246047, 33012060, 104677731, 233784625, 398671830, 1138569375, 3847891246, 7151230548, 17442630021, 46416620988, 118857237060, 363519789685, 661956375011, 1712300152639, 4761949150147, 8964540458636, 24746310311237, 62452210349278, 150016895989040, 453927852027278, 948923770773559, 3275343477577565, 5756783232753127, 13616706687879089, 26402320025439836, 91814578040763059, 211796919962932717, 385545413311588646, 742071895214889791, 2137385737378343660, 5820500440463297078, 15401185997444609852, 49206779920875282228, 101148479344021765606, 205390946600728256099, 593695571211967641654, 1163476540184124239753, 3920275177926640702128, 11188401781366603668803, 26452211702098700985776, 56612547941955968739356, 176511950177344415872304, 350456159524844834233165, 932655004294881661656249, 3077731648705646793828507, 9127653332576335535543235, 14107124912327219069005253, 53639235705342264540097281, 139903414487199921597126219, 377113327325865137005647964, 797007439689940464465071770, 2456373221352926158802602905, 4997725491122440484756502995, 17601885978368777637676626066, 27945705300453872028061217316, 70259455336271034962808380541, 241339934663279791843376677893, 565927167417896365819102921696, 1498269591024734505946670540129, 4476165672138335294342834148717, 8246962867693878472370951037335, 29609522845816295639745215494800, 71952214344473760246502727717474, 169361817288205588754741757159731, 390045301314759178244461824288458, 1337540279161737220902909199776611, 3221480198479784802709388960779700, 9670513515504338974817616478456700, 16261746247432868145400788404115430, 53594268392537203440232335914792279, 142627442102890550431018293710429426, 249683635647920776857130562696997561, 689878480570146636843962995034183967, 1647889244922264517646376201060969417, 4362391204795633804803911898013660682, 11983025462449787764688227594361812707, 19474005190319410527122673327870913310, 40950423948271412394664153066384954054, 139255978428478610787399242087880835737, 382133188700471370531564036246745271608, 618340037056166043673108074267387394368, 1728641328632513907826054966389623526131, 4246454964077064700888723109771772689322, 7526932088676669848792644586429545161503, 14761773428394206759829134632198244970685, 42336665776969730227150513015344171877811, 73191053942159553542196382411683917861300, 211549032502894704558541919050681697675397, 554709644259380577558971870420849574372151, 1251152425154260246544953154540513290303621, 2818798972367329802956936052623797403793942, 7638358444068983298092603686815486790113890, 24695143882440275994689721479314417528417480, 45729327569890326278523663568847218262894959, 129925286147414817076637512089880305727457533, 357058960265822950281886346091988882031910760, 870811282376277097902073516532006850342152858, 2399129617319427629796691807338852665469337085, 7522497498897836117435156411281203259743818186, 17703808279261898891912155690137638994014567408, 39174398341780347981624886777838524967209728446, 71626422074785376430650030090797947505033373583, 189453667691364649027951065496599754814571374684, 437295033677960022667168340703719574179513440159, 1105022320374390979035499970036715293235993540826, 2482140894382786914874701298953446381142900730227, 7941406921570365260066022237661009338911386179194, 13688077798315662160188528865690475378175919829521, 40118424472696130315297350323559766967889857978364, 105189379969045772302352882060687514329245824860122, 199293659238948607716187263853532082285127398693261, 499536111913922039437392654679505181047127518386152, 1265716378918935998920835568757397506132677689873802, 4251975766094131691018482661130820129953060977929504, 11152957210935036994690757763894857926461579995709364, 29243034751011001056721898400833781278921232465896703, 83127804731558215656517415813913013712630964732885793, 197287313991484123623412111326147421339126168589781103, 580348074469542880297800575176456597744257638809118170, 952848219059546044449261356813174361415872857630315510, 2114745453546299027601967135831843941629758587200332803, 6732303576367127091793491258707612535996916865106486930, 17969751578033370972927234837249484835783104974373526668, 50353964851880252824761483078317672020552394668185625845, 114792749147200000567884552573247130055515068451479473326, 344881289580954366545252182642967036273037618565165401985, 1028830458186445450162354520820201527695218769577051320473, 2074905233540761021629273629118215092544205899770047449244, 6827824489946353955926387525605200460781082737913381690336, 13024891552715019198360589788142658101822141014082307429749, 25961005268769363699702206141880105110265708699262059458918, 75403822308341240881775753922079349096463802345797378834029, 237384123451169596772029918832412849807327730438354057322622, 712646240930595428776240903619042913605109976371239636231758, 1858677703618066892165605509033944664007520745899837556768895, 4139395606166311238767981220233801698454319610253778363314838, 11051661045091733320416016319660914967058929654228453865287281, 29811585925705783247773137027702029276636378622129036803066195, 90685056735716951430085719312184849024248295771954003433442472, 157500945846011120649342030924242308092488581060888955520117740, 372901626023221848769914983494185928870895559258054416488096811, 768231028240804910809905945806694160784354754863882766743917789, 2779285901235347349512412519384436770411460171816095983145397440, 6374104945628711471675855561257403169698347988699930709009388571, 15606620797895735826222569176215400049549335070727802852935792508, 36407286542538484153926148252126040596266900628856973721204544487, 124345134443495254231144676818478910782759198180390061540449975329, 247113740493284619019931820393865652802499920117478290621711932786, 546250851448819627474782890078865878619982888424175090054606739349, 1708592433038733956978819431107564666115535756847903016488985258178, 3469784692808773680977989909012383598601318450115335667599446101916, 10923256812598128494335226092601900716551326610194937277684839542369, 21012491338240214838754959441277560200420746284908398093641375760080, 60889459302270258776558311240916612146241213106331686794170240374762, 163976015330661921425351604828688078789049035481531041973974028089785, 289037863251569623683823097040957275672420698243074506420157297827331, 757077203699594125515581476518783513279367742304415416466493229482750, 2419895647396662523171144180707701121877346566438572088091207837906226, 7355085337963583789485765997525070376210546183075717620390510384848601, 15051216064674860618341980616144084279926804604562228123313569479773613, 27941489504573067317849352242679271094163397351402254909630669501407776, 101620497919142332166787423172023060084593540312322612628746436809445674, 226881723516906947900548874100926330355595061853588440070446478001634192, 436083549067326238210237926429619818583468595956103126733614121273925302, 1114300762650958326100809843235006795980444078921364112608090634574957344, 2067630703150668695099956606446000647289440828791043320265352802856027353, 6184858091099126482135322120120464262653454412363734887325664168742191917, 20198724557091875844715800016163838909724718285368458520056089111628596330, 31016012035612935043240048944310566375654982913771972602093586083253422398, 120517928868495613278649932692310155587627278645665690072538147101563551766, 189853493819940791022006359464978248211780374156959402302888328075135559122, 709261139869078187523368280811328692680117587337216655356117972203528916551, 1494450926662311226674274795483402016068321469408932952124223720040234068030, 4833201522454078687541173754025375255160393643329610440001807389162022858137, 13065426763007211443646416727098859879614516619696845038342383829309179073982, 31498041121702214861734489217437935540479379421202405303460486717862084301294, 59291071262486212405215961522173655254987660557013973769285757104149711757459, 137325620971003240316895273046089454057536316983680621619104742603734626157973, 322033994335205758184753941417891767592538862759074152575171260357782006734442, 820082783566832754339608163235147685713597507674476057203654315048011026367219, 2282651344288337092906883083740075053173109353137863831730238422975306417325757, 5445119536937019732153059574137765564679350539463171899410036275958492350218676, 15640432491440562916581632653853505713511238255286321934711250830601955403677071, 41106883032429969859399906487019322357415120653637758039703350990320596875155176, 103754830954744065029443848605781937050053754534445990149281507972325774765844876, 234666834709268927734887936099822319961738129376455664521947726208265410000264742, 796501101363737180381507228150305361162624877853273443755457607681031102231623307, 1624552917282803716066319956956102765638808948119862597393339135995911391379123522, 4643272637840339310515026952678388354699825180379372281574901801196876030063101974, 12698618143562269391895747140398377495554004174836256597996901873500325652914287227, 35723733467261031422647885542793080310475947027099953899906182407397300154268828906, 66579759042299327879621766658030061118334921216187867761491910504181344451238684350, 239558348723378720363003224968080360385965369779814655734270075126998161979921905000, 674426340811237207208953232785934391016215462902095720638324651170969997400637801355, 1698823780061918718547756106555041994312203433347013142428193591099315938666752495147, 3485698669992831956608280816819201625859973318902236645999324294867314338271763576226, 11913442231481393917536601792582866930393303587594985248503741285895455503031416467367, 23070531945625150855016941245865388154950147453856685413887739256847410892916751249842, 63062109298026246794043518591814177894498277952179449322185515920851203385563000039545, 201500456854818387020432137947274011145636992031847792130877996231861744196691929847748, 386293027342088096708767070123592359264038177654678967794307420131436089009234887958085, 962652147623483170628478119235555226505070396879489339105090935822447174750045231232478, 3035935960793431917350036879195567655285637476975406683996240225461808984868014791791433, 6208746117115824715018162711918248788514776556569667609833722045497831346028332955531410, 11762322147658744239353552479176647603950873433079903790516674882105043434830328826675415, 22679200582127225664793559521091332878355319644677462980823198911465583443269858630893253, 73929710933006149888049977928677968518055319247626886667227984506656971966999436923186972, 122524349818395517581134493004049791722607446965559017459380345881157453828660236992049404, 412926833511789222428174650284405691872834629858851326844087117202853421601692502254318141, 1029385129423499530322969843276842783066057615497035785381633948646265964471244991407283657, 2374019900827890887681448469648598056064267661046120767421848772396302513783495423644064007, 7129046282305997419886465925038724574815350866486395082327924571694995543004421437396685163, 15553684426659575255143733092646126163883808844830770798803864550707886694317293166976752540, 36868510946091898479948303208447807989049331965479662439764899809218618486185846045349542501, 92245655628350120221629636214996850938258802134676165059052497372214318974743615511153118145, 186463470334970062582820387784350511557982560369498424617823476509363037536450250866616200018, 572967521502291777355369990006837729815084981232789335148124013079835565379339449250907380488，1481745249132912511970258586968019679134485717661841452421417313959912906838055641721186578588, 3465571259266031075485176569236690543411907657240139447438094553546637617425088900258756309108, 8435925081032968505659480326132770316717891729208893135134645312992136104713045209348571379936, 20315655322325100095226141940419414017723560946817780337100296517956534785685937181001107745352, 43069115966613244938070771746304575880400024938295357246717079316564326270692925649165248799853, 154233412749662382894550506472683312102297703424057840129476320316144010040200771168572376219849, 352877164586305833533208196782157198192758667776588081344657867110512140773408077435261431699405, 731939874265903145518316019567169287035472945759023530855697163432627661288949769619402453516834, 2189452024672949178210645600969378516255080271308334836448144354429705327344143994347331957449853, 3896543605375761834186485166037278157701213968430616464967138263870727947226180820650265115757354, 9136364061744114854751740581900554472617621867814569413142650998411332183920873701211555172374338, 31182169589957210510416755511542482029989997938097777712995732237583051643250531461221140115798313, 76737932310662322563271317876920472434982416417386459109415811734811165935978744596464401289256365, 191657687539432627521287232027340814340762593718642860136243059179657356411665753239917046107562015, 530361069831754440835688500919172905456422674539149906219439563860239029311496751350136915275150864, 1387792997020024308183922178096461451972294935906886419345639014544739179094711431002567439046777688, 2286383934503119795216122706571707851067263586234080042542833733216757155431244141022301236049602882, 5217435832596475959525740735112831333306893965389666926215938837589313774349496690036610287629333005, 13857335145208908258169891019385567845284268412333112678215001155302498425490658878264656236992134935, 40163901018471004896425196956916864061977023091787666532481831101052032374062940939516719648018676594, 82892214529323438899501402117098988403652889186148588453800977258361448264060748670322604495661134167, 178956544188555415155972101504345380390695957167910254018903325710948594375512551321503428603501757891, 563888574268395325287659273510106617675959539240732287901035847602904779682730930207201257182213858543, 1616044303623257921514683914498983737627603891472634935907943748930280908786049272784565904600012939098, 2891229181345915888829785513242002484495784340354174828728993457272687483459059048534538302181816688976, 10207730272860940549823879515425309207636840459300447491903147067853625202918689426829904372421061677895, 17526621515916394607402562632381069779604072768221581075247386337947979364802058499395942689207299830365, 55864742839796343168209200305202648507682753148596246337408494037308856790224259497580631081634646188041, 165332196033938201434627346583990806851682965862702414330472648748014088812475559273855488926778988149883, 494729626554411141427744566730794748483202977845760867859438479405205853778032755546761473203576297889449, 773241724058457908926664671814549280391747757602041708672622636112281590651589333985868232639345426359863, 2643090721830219937871980242863893762864524580138013585975903383984399727700467749841537295988160882592554, 7602742125929529736410459828760559621377824926000865839917497433361558637433229365703421216832254559844712, 20298012813427893859751095024917906619591438637592000480476880613738608994530228331797315397345124353458048, 57138113294488937158388285440237932686091901290656714986248760196665994518443306993120321953623611701468826, 156180826248086652580528603931836069088833849466705801833826561589537926864487694377480227882717998855358198, 405091254840842081029125739284610173825182926000756067214428354197290398676973286834323853061720032954965963, 778366116109730017138034746329928058267161795656720444904686750506814152375884477590166274857108289313593118, 1796005150394618766778725965351985496132876507371048438760920669904977557456986675227521156526604287512648264, 3898444018773054695814825596014017751795964177961572987153324103751602074848254485225397417397654262390321944, 10703462078231223004197739814155717950000211259146027443753796966491790618726938276000128782966812980398530204, 18372321975824831177753464245580317968933119357879255869022769977852558056854497414886761863892673585456643891, 48317491803925955550053615386786484989034506042840366819980397407568791721238179125455458641299301269848666510, 158255568588301663954187011445643163738485858122034088577201324726783893231449209827193255340005164973552974453, 456823552578369748946561710072366945172148623875999657195033140013027572670231347304984109456384691884394301596, 707160118481884894551388234729179730915972581073118662214623842056893684770640844231508665861861467073743805665, 2706927376520605764276007802932993151885010075033345167172586198244735154579188535970342536626727165782495180134, 5524495123704893916572931697399108221354633312984253879509446961783982258828184219735409076305664075360213376822, 11902801828947547843316856179728603283371324186706149334180029898787026360919748804787239985463725865632928552507, 42817758358028425898228144386760814695029076486689089958556088081002352872886441780712721026897632438300836110665, 85341298053933033277929612803230545434450389443924565926372394273668666803233325131592974981823970679666528469082, 203545487666526735282497187348232067937848828434866343193810463204944901878674073018178572958556722616056919932826, 404490991972927610287798222030298357859147323959244483279529298622268125169109324278915340735214314234862449055448, 1015889532249910731454157235904076803563143859066636167138222193683905683535906365566683356226160720652109370999321, 2376026683785110886914732723263521678018967831673326233555377196140833492114241003132626058539164015299593970425136, 6462912523501528306439979574464826777892245783057732634021629306276087967421373795532316029843905278328516884883058, 16981441701453104471733297233747957918575727289870879189918428405182537334140409929337675754279869961515500536636176, 37605582989982272328044312175947277729400907856460324692248887357599456103017970584086153023793040540391945445989257, 91747039052675678105959960961981861389020215173307703983752122608163760292472703277085998681706298344337891404847646, 197976695213061406953734629818998754281337862490966315225432914015679415715157795368611025598068494075696354180224057, 407579734020903728451591407903624856111929215373480871243621182164970838186438777218257932637652562832905518769398262, 1192695842629740666007709455549699909835266353292608841275812622248241416280954865990629770667881078271433918923422731, 2356450454926316659685731978750584215969826513728852376452662114206102092287531644004469937748823746129670826796883901, 6606194810680818911726753398369719656427756109429906495763748359459974583720214056977960616895121295259675484772228900, 21238856384108665139068993634246013308212000660518883089302921531246892139968871926076965355331061987385136533519279525, 60431698017667972588320134967121949330864812114211557015977441929363675768812209839204671181454067749535515855713156763, 174665868422753780275604141699079697885219220210916384980421958910804651659162534153721798589901082858559767609552079345, 394230935137659132182806278870718863867754651145064639278806591391259891710009233085853984826856234290081395609225890238, 938316178783979725028510016300351906317832877618969965871296642973988528249289624189564279188734089982984293864940639663, 1690300816950917856165481180579373059665398098127346945618427499442023814975741786872721941536175836912500050716899314350, 4241040212750921734662543578806315663721700243000974307468609317605794291246764526126048318503818177838783905309400289117, 9899615703109749398438558898664002269482804539466079984631091253252047080143600618559486614511675282173378128689947106499, 19072918764217687057379877185516040357999863490449836492311841376572022870447983721729056895047026984202403660270528351362, 61457030295636043956746238914591148777316757448303861396901131680368800892725607851722251866187547310356464672462006792936, 130554685050076234706409249768453974245979757597714789262984612467812333642313018653001831006709360179701213479970689476759, 317707441009141362433020809851971219097475768762476580041791647909345575364794752462683617015215387354639266789655705355159, 766407353781281024676870262720057676902122989643223864583232810528888853102644816087185770633710024110065414129660560848818, 1378158372668635043591303404733183053913783647791091758022520799715774445178343987469574552089574912051263356050601448829569, 2849814783153826557775488037652012659704609417837692209372285071574038848736100379264094051217084360358380745456795092662367, 7761768442678261726960193678894950205212069061687767898603990098871593859918952089239031086652597614705182760193814143657094, 25797856998139398890116390239859835084629679432044893266362900315705828350899796936954893678013444560821963770721738841492762, 45230528787260219469707111504991583088449246785732739036848497764369166856369435663350796527642874763730890628636593210838634, 125595007654406839330037705158661517651788635482067500225344073216015649944944879970130124750959631685921435054581613709164822, 338747508849935686599681561847193572302329804892368313208731993174039023400358858978202514407262943107662339259004212857955666, 927842701337787263386928773903441275979399427379662460065544246411463087320044839262987027337743305220579800532826965270689250, 1974283905173053393614664395812743602970084360210384412934832566684934360366297764438728189449912704403685566054487439810857627, 6547791381850377804871914819409383329722364771877581519586671693693630274474320389311984387956647850854999536112540018330183809, 15709320907036538202306551117984227990557852089499582468594623629463507925701405510011304643762744267804282547349971254508845938, 40270138688478461945314017148044972001708543125646521974155404640273555509873235113536988809551924038925428913961013964565197607, 99168179703900580858922903603323807687115252977021819828415602208147447841271397891925410158445036111494543958823713690209285369, 269868178430265744761277563499719925184037917272176039027995896214226177897366881562687640385414521231482816048831046030643750903, 831659192392583336646613887566957000280656975320208034953861277421104038936580189145699653541798336705409469145595542460062434471, 2073476643694212471632333653958562004434818366225131771845046659755589302151344899589183197864077374128293181680576229954100550419, 4554149306780266313933686119966338774145476827044906188542821462680791576860383095025724314895890630857897398967476576259995321191, 14651118307465336327922062019691151414683570292038775511915021602908118951591926995520466221396947959539039452124967851254379010308, 32590352694473324794187157416677986187287003972605121693147144070229453983956761041980924463747749024664597601177994952136065984811, 81134631049823241301269776481475653931802229294857541846620286653857647735078830230944498091871440739749676625155855958593920070814, 185677119342066492911752180414903294080590111905381979357926969960006994207482364686831869137669282514024709390338951171955152686319, 611640161419871188028819133410469586343996954403636969815202842657504592966769167857498786484339404586484056783483882604337795700345, 1665805557476802274778809527131744615949426833045219219448282924298718975882034660815478936907356513550130652021165488275923832785881]
#2396891354790728703114360139080949406724802115971958909288237002299944566663978116795388053104330363637753770349706301118152757502162

这道题就利用了背包密码体制进行了加密，gen_key实现了生成超递增背包向量$A$这一操作：

def gen_key(size):
    s = 1000
    key = []
    for _ in range(size):
        a = random.randint(s + 1, 2 * s)
        assert a > sum(key)
        key.append(a)
        s += a
    return key

加密按照明文二进制表示进行加密：

for i in range(L):
    c += key[i]**(m & 1)
    m >>= 1

根据刚刚学习的贪婪算法，很容易即可求出flag：

list = [1928, 4648, 12352, 24010, 58760, 148406, 441469, 906294, 2347544, 4145527, 13246047, 33012060, 104677731, 233784625, 398671830, 1138569375, 3847891246, 7151230548, 17442630021, 46416620988, 118857237060, 363519789685, 661956375011, 1712300152639, 4761949150147, 8964540458636, 24746310311237, 62452210349278, 150016895989040, 453927852027278, 948923770773559, 3275343477577565, 5756783232753127, 13616706687879089, 26402320025439836, 91814578040763059, 211796919962932717, 385545413311588646, 742071895214889791, 2137385737378343660, 5820500440463297078, 15401185997444609852, 49206779920875282228, 101148479344021765606, 205390946600728256099, 593695571211967641654, 1163476540184124239753, 3920275177926640702128, 11188401781366603668803, 26452211702098700985776, 56612547941955968739356, 176511950177344415872304, 350456159524844834233165, 932655004294881661656249, 3077731648705646793828507, 9127653332576335535543235, 14107124912327219069005253, 53639235705342264540097281, 139903414487199921597126219, 377113327325865137005647964, 797007439689940464465071770, 2456373221352926158802602905, 4997725491122440484756502995, 17601885978368777637676626066, 27945705300453872028061217316, 70259455336271034962808380541, 241339934663279791843376677893, 565927167417896365819102921696, 1498269591024734505946670540129, 4476165672138335294342834148717, 8246962867693878472370951037335, 29609522845816295639745215494800, 71952214344473760246502727717474, 169361817288205588754741757159731, 390045301314759178244461824288458, 1337540279161737220902909199776611, 3221480198479784802709388960779700, 9670513515504338974817616478456700, 16261746247432868145400788404115430, 53594268392537203440232335914792279, 142627442102890550431018293710429426, 249683635647920776857130562696997561, 689878480570146636843962995034183967, 1647889244922264517646376201060969417, 4362391204795633804803911898013660682, 11983025462449787764688227594361812707, 19474005190319410527122673327870913310, 40950423948271412394664153066384954054, 139255978428478610787399242087880835737, 382133188700471370531564036246745271608, 618340037056166043673108074267387394368, 1728641328632513907826054966389623526131, 4246454964077064700888723109771772689322, 7526932088676669848792644586429545161503, 14761773428394206759829134632198244970685, 42336665776969730227150513015344171877811, 73191053942159553542196382411683917861300, 211549032502894704558541919050681697675397, 554709644259380577558971870420849574372151, 1251152425154260246544953154540513290303621, 2818798972367329802956936052623797403793942, 7638358444068983298092603686815486790113890, 24695143882440275994689721479314417528417480, 45729327569890326278523663568847218262894959, 129925286147414817076637512089880305727457533, 357058960265822950281886346091988882031910760, 870811282376277097902073516532006850342152858, 2399129617319427629796691807338852665469337085, 7522497498897836117435156411281203259743818186, 17703808279261898891912155690137638994014567408, 39174398341780347981624886777838524967209728446, 71626422074785376430650030090797947505033373583, 189453667691364649027951065496599754814571374684, 437295033677960022667168340703719574179513440159, 1105022320374390979035499970036715293235993540826, 2482140894382786914874701298953446381142900730227, 7941406921570365260066022237661009338911386179194, 13688077798315662160188528865690475378175919829521, 40118424472696130315297350323559766967889857978364, 105189379969045772302352882060687514329245824860122, 199293659238948607716187263853532082285127398693261, 499536111913922039437392654679505181047127518386152, 1265716378918935998920835568757397506132677689873802, 4251975766094131691018482661130820129953060977929504, 11152957210935036994690757763894857926461579995709364, 29243034751011001056721898400833781278921232465896703, 83127804731558215656517415813913013712630964732885793, 197287313991484123623412111326147421339126168589781103, 580348074469542880297800575176456597744257638809118170, 952848219059546044449261356813174361415872857630315510, 2114745453546299027601967135831843941629758587200332803, 6732303576367127091793491258707612535996916865106486930, 17969751578033370972927234837249484835783104974373526668, 50353964851880252824761483078317672020552394668185625845, 114792749147200000567884552573247130055515068451479473326, 344881289580954366545252182642967036273037618565165401985, 1028830458186445450162354520820201527695218769577051320473, 2074905233540761021629273629118215092544205899770047449244, 6827824489946353955926387525605200460781082737913381690336, 13024891552715019198360589788142658101822141014082307429749, 25961005268769363699702206141880105110265708699262059458918, 75403822308341240881775753922079349096463802345797378834029, 237384123451169596772029918832412849807327730438354057322622, 712646240930595428776240903619042913605109976371239636231758, 1858677703618066892165605509033944664007520745899837556768895, 4139395606166311238767981220233801698454319610253778363314838, 11051661045091733320416016319660914967058929654228453865287281, 29811585925705783247773137027702029276636378622129036803066195, 90685056735716951430085719312184849024248295771954003433442472, 157500945846011120649342030924242308092488581060888955520117740, 372901626023221848769914983494185928870895559258054416488096811, 768231028240804910809905945806694160784354754863882766743917789, 2779285901235347349512412519384436770411460171816095983145397440, 6374104945628711471675855561257403169698347988699930709009388571, 15606620797895735826222569176215400049549335070727802852935792508, 36407286542538484153926148252126040596266900628856973721204544487, 124345134443495254231144676818478910782759198180390061540449975329, 247113740493284619019931820393865652802499920117478290621711932786, 546250851448819627474782890078865878619982888424175090054606739349, 1708592433038733956978819431107564666115535756847903016488985258178, 3469784692808773680977989909012383598601318450115335667599446101916, 10923256812598128494335226092601900716551326610194937277684839542369, 21012491338240214838754959441277560200420746284908398093641375760080, 60889459302270258776558311240916612146241213106331686794170240374762, 163976015330661921425351604828688078789049035481531041973974028089785, 289037863251569623683823097040957275672420698243074506420157297827331, 757077203699594125515581476518783513279367742304415416466493229482750, 2419895647396662523171144180707701121877346566438572088091207837906226, 7355085337963583789485765997525070376210546183075717620390510384848601, 15051216064674860618341980616144084279926804604562228123313569479773613, 27941489504573067317849352242679271094163397351402254909630669501407776, 101620497919142332166787423172023060084593540312322612628746436809445674, 226881723516906947900548874100926330355595061853588440070446478001634192, 436083549067326238210237926429619818583468595956103126733614121273925302, 1114300762650958326100809843235006795980444078921364112608090634574957344, 2067630703150668695099956606446000647289440828791043320265352802856027353, 6184858091099126482135322120120464262653454412363734887325664168742191917, 20198724557091875844715800016163838909724718285368458520056089111628596330, 31016012035612935043240048944310566375654982913771972602093586083253422398, 120517928868495613278649932692310155587627278645665690072538147101563551766, 189853493819940791022006359464978248211780374156959402302888328075135559122, 709261139869078187523368280811328692680117587337216655356117972203528916551, 1494450926662311226674274795483402016068321469408932952124223720040234068030, 4833201522454078687541173754025375255160393643329610440001807389162022858137, 13065426763007211443646416727098859879614516619696845038342383829309179073982, 31498041121702214861734489217437935540479379421202405303460486717862084301294, 59291071262486212405215961522173655254987660557013973769285757104149711757459, 137325620971003240316895273046089454057536316983680621619104742603734626157973, 322033994335205758184753941417891767592538862759074152575171260357782006734442, 820082783566832754339608163235147685713597507674476057203654315048011026367219, 2282651344288337092906883083740075053173109353137863831730238422975306417325757, 5445119536937019732153059574137765564679350539463171899410036275958492350218676, 15640432491440562916581632653853505713511238255286321934711250830601955403677071, 41106883032429969859399906487019322357415120653637758039703350990320596875155176, 103754830954744065029443848605781937050053754534445990149281507972325774765844876, 234666834709268927734887936099822319961738129376455664521947726208265410000264742, 796501101363737180381507228150305361162624877853273443755457607681031102231623307, 1624552917282803716066319956956102765638808948119862597393339135995911391379123522, 4643272637840339310515026952678388354699825180379372281574901801196876030063101974, 12698618143562269391895747140398377495554004174836256597996901873500325652914287227, 35723733467261031422647885542793080310475947027099953899906182407397300154268828906, 66579759042299327879621766658030061118334921216187867761491910504181344451238684350, 239558348723378720363003224968080360385965369779814655734270075126998161979921905000, 674426340811237207208953232785934391016215462902095720638324651170969997400637801355, 1698823780061918718547756106555041994312203433347013142428193591099315938666752495147, 3485698669992831956608280816819201625859973318902236645999324294867314338271763576226, 11913442231481393917536601792582866930393303587594985248503741285895455503031416467367, 23070531945625150855016941245865388154950147453856685413887739256847410892916751249842, 63062109298026246794043518591814177894498277952179449322185515920851203385563000039545, 201500456854818387020432137947274011145636992031847792130877996231861744196691929847748, 386293027342088096708767070123592359264038177654678967794307420131436089009234887958085, 962652147623483170628478119235555226505070396879489339105090935822447174750045231232478, 3035935960793431917350036879195567655285637476975406683996240225461808984868014791791433, 6208746117115824715018162711918248788514776556569667609833722045497831346028332955531410, 11762322147658744239353552479176647603950873433079903790516674882105043434830328826675415, 22679200582127225664793559521091332878355319644677462980823198911465583443269858630893253, 73929710933006149888049977928677968518055319247626886667227984506656971966999436923186972, 122524349818395517581134493004049791722607446965559017459380345881157453828660236992049404, 412926833511789222428174650284405691872834629858851326844087117202853421601692502254318141, 1029385129423499530322969843276842783066057615497035785381633948646265964471244991407283657, 2374019900827890887681448469648598056064267661046120767421848772396302513783495423644064007, 7129046282305997419886465925038724574815350866486395082327924571694995543004421437396685163, 15553684426659575255143733092646126163883808844830770798803864550707886694317293166976752540, 36868510946091898479948303208447807989049331965479662439764899809218618486185846045349542501, 92245655628350120221629636214996850938258802134676165059052497372214318974743615511153118145, 186463470334970062582820387784350511557982560369498424617823476509363037536450250866616200018, 572967521502291777355369990006837729815084981232789335148124013079835565379339449250907380488,1481745249132912511970258586968019679134485717661841452421417313959912906838055641721186578588, 3465571259266031075485176569236690543411907657240139447438094553546637617425088900258756309108, 8435925081032968505659480326132770316717891729208893135134645312992136104713045209348571379936, 20315655322325100095226141940419414017723560946817780337100296517956534785685937181001107745352, 43069115966613244938070771746304575880400024938295357246717079316564326270692925649165248799853, 154233412749662382894550506472683312102297703424057840129476320316144010040200771168572376219849, 352877164586305833533208196782157198192758667776588081344657867110512140773408077435261431699405, 731939874265903145518316019567169287035472945759023530855697163432627661288949769619402453516834, 2189452024672949178210645600969378516255080271308334836448144354429705327344143994347331957449853, 3896543605375761834186485166037278157701213968430616464967138263870727947226180820650265115757354, 9136364061744114854751740581900554472617621867814569413142650998411332183920873701211555172374338, 31182169589957210510416755511542482029989997938097777712995732237583051643250531461221140115798313, 76737932310662322563271317876920472434982416417386459109415811734811165935978744596464401289256365, 191657687539432627521287232027340814340762593718642860136243059179657356411665753239917046107562015, 530361069831754440835688500919172905456422674539149906219439563860239029311496751350136915275150864, 1387792997020024308183922178096461451972294935906886419345639014544739179094711431002567439046777688, 2286383934503119795216122706571707851067263586234080042542833733216757155431244141022301236049602882, 5217435832596475959525740735112831333306893965389666926215938837589313774349496690036610287629333005, 13857335145208908258169891019385567845284268412333112678215001155302498425490658878264656236992134935, 40163901018471004896425196956916864061977023091787666532481831101052032374062940939516719648018676594, 82892214529323438899501402117098988403652889186148588453800977258361448264060748670322604495661134167, 178956544188555415155972101504345380390695957167910254018903325710948594375512551321503428603501757891, 563888574268395325287659273510106617675959539240732287901035847602904779682730930207201257182213858543, 1616044303623257921514683914498983737627603891472634935907943748930280908786049272784565904600012939098, 2891229181345915888829785513242002484495784340354174828728993457272687483459059048534538302181816688976, 10207730272860940549823879515425309207636840459300447491903147067853625202918689426829904372421061677895, 17526621515916394607402562632381069779604072768221581075247386337947979364802058499395942689207299830365, 55864742839796343168209200305202648507682753148596246337408494037308856790224259497580631081634646188041, 165332196033938201434627346583990806851682965862702414330472648748014088812475559273855488926778988149883, 494729626554411141427744566730794748483202977845760867859438479405205853778032755546761473203576297889449, 773241724058457908926664671814549280391747757602041708672622636112281590651589333985868232639345426359863, 2643090721830219937871980242863893762864524580138013585975903383984399727700467749841537295988160882592554, 7602742125929529736410459828760559621377824926000865839917497433361558637433229365703421216832254559844712, 20298012813427893859751095024917906619591438637592000480476880613738608994530228331797315397345124353458048, 57138113294488937158388285440237932686091901290656714986248760196665994518443306993120321953623611701468826, 156180826248086652580528603931836069088833849466705801833826561589537926864487694377480227882717998855358198, 405091254840842081029125739284610173825182926000756067214428354197290398676973286834323853061720032954965963, 778366116109730017138034746329928058267161795656720444904686750506814152375884477590166274857108289313593118, 1796005150394618766778725965351985496132876507371048438760920669904977557456986675227521156526604287512648264, 3898444018773054695814825596014017751795964177961572987153324103751602074848254485225397417397654262390321944, 10703462078231223004197739814155717950000211259146027443753796966491790618726938276000128782966812980398530204, 18372321975824831177753464245580317968933119357879255869022769977852558056854497414886761863892673585456643891, 48317491803925955550053615386786484989034506042840366819980397407568791721238179125455458641299301269848666510, 158255568588301663954187011445643163738485858122034088577201324726783893231449209827193255340005164973552974453, 456823552578369748946561710072366945172148623875999657195033140013027572670231347304984109456384691884394301596, 707160118481884894551388234729179730915972581073118662214623842056893684770640844231508665861861467073743805665, 2706927376520605764276007802932993151885010075033345167172586198244735154579188535970342536626727165782495180134, 5524495123704893916572931697399108221354633312984253879509446961783982258828184219735409076305664075360213376822, 11902801828947547843316856179728603283371324186706149334180029898787026360919748804787239985463725865632928552507, 42817758358028425898228144386760814695029076486689089958556088081002352872886441780712721026897632438300836110665, 85341298053933033277929612803230545434450389443924565926372394273668666803233325131592974981823970679666528469082, 203545487666526735282497187348232067937848828434866343193810463204944901878674073018178572958556722616056919932826, 404490991972927610287798222030298357859147323959244483279529298622268125169109324278915340735214314234862449055448, 1015889532249910731454157235904076803563143859066636167138222193683905683535906365566683356226160720652109370999321, 2376026683785110886914732723263521678018967831673326233555377196140833492114241003132626058539164015299593970425136, 6462912523501528306439979574464826777892245783057732634021629306276087967421373795532316029843905278328516884883058, 16981441701453104471733297233747957918575727289870879189918428405182537334140409929337675754279869961515500536636176, 37605582989982272328044312175947277729400907856460324692248887357599456103017970584086153023793040540391945445989257, 91747039052675678105959960961981861389020215173307703983752122608163760292472703277085998681706298344337891404847646, 197976695213061406953734629818998754281337862490966315225432914015679415715157795368611025598068494075696354180224057, 407579734020903728451591407903624856111929215373480871243621182164970838186438777218257932637652562832905518769398262, 1192695842629740666007709455549699909835266353292608841275812622248241416280954865990629770667881078271433918923422731, 2356450454926316659685731978750584215969826513728852376452662114206102092287531644004469937748823746129670826796883901, 6606194810680818911726753398369719656427756109429906495763748359459974583720214056977960616895121295259675484772228900, 21238856384108665139068993634246013308212000660518883089302921531246892139968871926076965355331061987385136533519279525, 60431698017667972588320134967121949330864812114211557015977441929363675768812209839204671181454067749535515855713156763, 174665868422753780275604141699079697885219220210916384980421958910804651659162534153721798589901082858559767609552079345, 394230935137659132182806278870718863867754651145064639278806591391259891710009233085853984826856234290081395609225890238, 938316178783979725028510016300351906317832877618969965871296642973988528249289624189564279188734089982984293864940639663, 1690300816950917856165481180579373059665398098127346945618427499442023814975741786872721941536175836912500050716899314350, 4241040212750921734662543578806315663721700243000974307468609317605794291246764526126048318503818177838783905309400289117, 9899615703109749398438558898664002269482804539466079984631091253252047080143600618559486614511675282173378128689947106499, 19072918764217687057379877185516040357999863490449836492311841376572022870447983721729056895047026984202403660270528351362, 61457030295636043956746238914591148777316757448303861396901131680368800892725607851722251866187547310356464672462006792936, 130554685050076234706409249768453974245979757597714789262984612467812333642313018653001831006709360179701213479970689476759, 317707441009141362433020809851971219097475768762476580041791647909345575364794752462683617015215387354639266789655705355159, 766407353781281024676870262720057676902122989643223864583232810528888853102644816087185770633710024110065414129660560848818, 1378158372668635043591303404733183053913783647791091758022520799715774445178343987469574552089574912051263356050601448829569, 2849814783153826557775488037652012659704609417837692209372285071574038848736100379264094051217084360358380745456795092662367, 7761768442678261726960193678894950205212069061687767898603990098871593859918952089239031086652597614705182760193814143657094, 25797856998139398890116390239859835084629679432044893266362900315705828350899796936954893678013444560821963770721738841492762, 45230528787260219469707111504991583088449246785732739036848497764369166856369435663350796527642874763730890628636593210838634, 125595007654406839330037705158661517651788635482067500225344073216015649944944879970130124750959631685921435054581613709164822, 338747508849935686599681561847193572302329804892368313208731993174039023400358858978202514407262943107662339259004212857955666, 927842701337787263386928773903441275979399427379662460065544246411463087320044839262987027337743305220579800532826965270689250, 1974283905173053393614664395812743602970084360210384412934832566684934360366297764438728189449912704403685566054487439810857627, 6547791381850377804871914819409383329722364771877581519586671693693630274474320389311984387956647850854999536112540018330183809, 15709320907036538202306551117984227990557852089499582468594623629463507925701405510011304643762744267804282547349971254508845938, 40270138688478461945314017148044972001708543125646521974155404640273555509873235113536988809551924038925428913961013964565197607, 99168179703900580858922903603323807687115252977021819828415602208147447841271397891925410158445036111494543958823713690209285369, 269868178430265744761277563499719925184037917272176039027995896214226177897366881562687640385414521231482816048831046030643750903, 831659192392583336646613887566957000280656975320208034953861277421104038936580189145699653541798336705409469145595542460062434471, 2073476643694212471632333653958562004434818366225131771845046659755589302151344899589183197864077374128293181680576229954100550419, 4554149306780266313933686119966338774145476827044906188542821462680791576860383095025724314895890630857897398967476576259995321191, 14651118307465336327922062019691151414683570292038775511915021602908118951591926995520466221396947959539039452124967851254379010308, 32590352694473324794187157416677986187287003972605121693147144070229453983956761041980924463747749024664597601177994952136065984811, 81134631049823241301269776481475653931802229294857541846620286653857647735078830230944498091871440739749676625155855958593920070814, 185677119342066492911752180414903294080590111905381979357926969960006994207482364686831869137669282514024709390338951171955152686319, 611640161419871188028819133410469586343996954403636969815202842657504592966769167857498786484339404586484056783483882604337795700345, 1665805557476802274778809527131744615949426833045219219448282924298718975882034660815478936907356513550130652021165488275923832785881]
c = 2396891354790728703114360139080949406724802115971958909288237002299944566663978116795388053104330363637753770349706301118152757502162

m=''
for i in range(len(list)-1, -1, -1):
    if c>=list[i]:
        c-=list[i]
        m+='1'
    else:
        m+='0'
print(long_to_bytes(int(m,2)))

模乘伪装

我们已经了解了背包密码，在这个基础上给了我们超递增背包向量，利用贪婪算法就可以很容易解密出明文。$A$为背包向量，$s$为背包容积，为了让背包密码不那么容易被解密，可以对$A$进行一步模乘伪装。

可以取模数$k$和乘数$t$，而且要求$gcd(k,t)=1$，使其存在乘法逆元：
$$
b_i= t\cdot a_i\bmod k(i=1,…,n)
$$
对$A$所有元素都进行这种操作，得到一个新的背包向量$B$，公式为：
$$
B=tA\bmod k
$$

$$
f(x)=B\cdot B_x
$$

组合一下，得到：
$$
c=f(x)=t\cdot A\cdot B_x\bmod k
$$
按照模运算规律可以进行解密操作，求出$AB_x$之后就可以用上面的算法继续求解明文了：
$$
AB_x=t^{-1}c\bmod k
$$

由于这里的$AB_x=t^{-1}c\bmod k$，如果$k$过小会导致模后结果过小导致无法继续用贪婪算法求$B_x$，所以通常我们要求$k>\sum^n_{i=1}a_i$。

按照这种方式生成密钥：

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

def gen_key(size):
    s = pow(2,50)
    privkey = []
    for _ in range(size):
        a = random.randint(s + 1, 2 * s)
        assert a > sum(privkey)
        privkey.append(a)
        s += a
    keysum = sum(privkey)
    k = random.randint(keysum+1,2*keysum)
    while 1:
        t = getPrime(150)
        if gmpy2.gcd(t,k)==1:
            break
    enkey = [t*i%k for i in privkey]
    return enkey

key = gen_key(50)
print(key)

J.Coster低密度攻击

简化攻击

在《格理论与密码学》118页开始，介绍了一种类似于J.Coster低密度攻击的基础版本，先介绍这个简化版本的攻击方式：

根据背包密码的算法介绍一种当背包维数较小时可以使用的基于格密码的攻击方式，先回顾一下背包加密的原理（这里在加密上没有采用超递增背包向量）：
$$
\sum^{n}{i=1}e_ia_i=s
$$
构造一系列的向量$\overrightarrow{b_1},…,\overrightarrow{b_{n+1}}$：
$$
\begin{cases}\overrightarrow b_1=(2,0,…,0,a_1)\\overrightarrow b_2=(0,2,…,0,a_2)\…\\overrightarrow b_n=(0,0,…,2,a_n)\\overrightarrow b{n+1}=(1,1,…,1,s)\end{cases}
$$

构造格基：
$$
B=\begin{bmatrix}\overrightarrow b_1 \\overrightarrow b_2\…\\overrightarrow b_n\\overrightarrow b_{n+1}
\end{bmatrix}=\begin{bmatrix}2 & 0 &…& 0 & a_1\0 & 2 &…& 0 & a_2\…\0 & 0 &…& 2 & a_n\1 & 1 &…& 1 & s\\end{bmatrix}
$$
我们最终需要得到的是这个背包加密的解，设为$\overrightarrow e=(e_1,…,e_n)$，在格$L$中存在向量：
$$
\begin{align}
\overrightarrow t & = (e_1,…,e_n,-1)\cdot B \
& = e_1\overrightarrow b_1+e_2\overrightarrow b_2+…+e_n\overrightarrow b_n-\overrightarrow b_{n+1} \
& = (2e_1-1,2e_2-1,…,2e_n-1,0)
\end{align}
$$
由于$e$的取值为$0$或者$1$，所以向量$\overrightarrow t$的元素除了最后一个$0$只有$±1$。求这个向量的长度发现一定为$\sqrt n$，$n$是这个格的维数，所以向量的长度很小，可以使用LLL算法或其他格底约简算法来解决SVP得到最短向量。

J.Coster攻击

J.Coster在这个基础上对算法做了优化。进行解密时，我们同样构造一系列的向量$\overrightarrow{b_1},…,\overrightarrow{b_{n+1}}$：
$$
\begin{cases}\overrightarrow b_1=(1,0,…,0,Na_1)\\overrightarrow b_2=(0,1,…,0,Na_2)\…\\overrightarrow b_n=(0,0,…,1,Na_n)\\overrightarrow b_{n+1}=(\frac 12,\frac 12,…,\frac 12,Ns)\end{cases}
$$

这里的$N$为随便取的大数，规定为：
$$
N>\frac 12\sqrt{n}
$$

同样的，这里的格$L$是由向量$\overrightarrow{b_1},…,\overrightarrow{b_{n+1}}$张成的，J.coster等人提出，当密度$d＜0.9408$时，存在格$L$中最短的向量，同时，能确定这个最短向量$\overrightarrow e$的元素值：

当Lattice中任意选取$k$个非零向量，由它们张成的子格的大小即为$L(Λk)$。密度$d$等于该子格的体积开$k$次方，即$d = L(Λk)^{\frac 1k}$

这个式子中，$k$表示选取的非零向量的个数，$L(Λk)$表示该子格的$n$维体积。简单来说，就是选取任意$k$个非零向量所张成的子格占整个Lattice的比例，比例越小，密度越小，整个Lattice越紧密。

$$
\begin{align}
\overrightarrow t & = (e_1’,…,e_n’,-1)\cdot B \
& = e_1\overrightarrow b_1+e_2\overrightarrow b_2+…+e_n\overrightarrow b_n-\overrightarrow b_{n+1} \
& = (e_1-\frac12,e_2-\frac12,…,e_n-\frac12,0)
\end{align}
$$

通常使用LLL算法或其他格底约简算法来解决SVP得到最短向量，当维数足够大（例如大于400）时，这种方法就不适用了。

J.Coster优化了什么？

高斯启发式（Gaussian heurstic）：$L$为$n$维格，高斯所期望的最短长度是：
$$
\sigma(L)\approx\sqrt{\frac{n}{2\pi e}}(det\ L)^{\frac 1 n}
$$
高斯期望越大，表示从该格中选择的向量大多数情况下都较为接近于格基向量，也就意味着该格中的基向量之间的线性相关性较高，格的密度较大。这里我们在最后一列同时乘上随机大常数$N$，矩阵的行列式值也增大了原来的$N$倍，最短向量的高斯期望相应增加$N^{\frac 1{n+1}}$倍，更容易找出$t$。

此外，在论文中，J.Coster将对角线元素全部设为$1$，为了符合最终求解的向量，的最后一行元素全部设为$\frac 12$，这里这样操作的原因是因为在有关高斯消元的格基规约算法过程中，需要将对角线元素化为$1$，这样可以进一步简化计算。

例题1

import random
from collections import namedtuple
import gmpy2
from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytes

FLAG = b'crypto{??????????????????????????}'
PrivateKey = namedtuple("PrivateKey", ['b', 'r', 'q'])

def gen_private_key(size):
    s = 10000
    b = []
    for _ in range(size):
        ai = random.randint(s + 1, 2 * s)
        assert ai > sum(b)
        b.append(ai)
        s += ai
    while True:
        q = random.randint(2 * s, 32 * s)
        if isPrime(q):
            break
    r = random.randint(s, q)
    assert q > sum(b)
    assert gmpy2.gcd(q,r) == 1
    return PrivateKey(b, r, q)


def gen_public_key(private_key: PrivateKey):
    a = []
    for x in private_key.b:
        a.append((private_key.r * x) % private_key.q)
    return a


def encrypt(msg, public_key):
    assert len(msg) * 8 <= len(public_key)
    ct = 0
    msg = bytes_to_long(msg)
    for bi in public_key:
        ct += (msg & 1) * bi
        msg >>= 1
    return ct


def decrypt(ct, private_key: PrivateKey):
    ct = inverse(private_key.r, private_key.q) * ct % private_key.q
    msg = 0
    for i in range(len(private_key.b) - 1, -1, -1):
         if ct >= private_key.b[i]:
             msg |= 1 << i
             ct -= private_key.b[i]
    return long_to_bytes(msg)


private_key = gen_private_key(len(FLAG) * 8)
public_key = gen_public_key(private_key)
encrypted = encrypt(FLAG, public_key)
decrypted = decrypt(encrypted, private_key)
assert decrypted == FLAG

print(f'Public key: {public_key}')
print(f'Encrypted Flag: {encrypted}')

这道题用到了超递增背包向量，但是如果只看加密函数：

def encrypt(msg, public_key):
    assert len(msg) * 8 <= len(public_key)
    ct = 0
    msg = bytes_to_long(msg)
    for bi in public_key:
        ct += (msg & 1) * bi
        msg >>= 1
    return ct

这里的public_key已经是模乘伪装后的新背包向量，我们并不知道这题里的模数和乘数，所以不能直接通过计算得到flag。由于最后我们求的是二进制位下的msg，可以直接把这个public_key就直接看做原始的背包向量，不去管模乘伪装这个操作，对其进行J.Coster低密度攻击。

按照上面的理论构造代码进行解密：

from Crypto.Util.number import *
import gmpy2, random

pubkey=[260288377891444370372615148009023640057294926547602419331406531383682223097787288755377467188515435381259752760746, 322734358011758862401399370931929863052553602421714393280581187496537763321855751120439457234561080720455397490349, 88092359256403564783665281993130133541226601877969436905267415353041909757324746080398461245281826552421872983184, 601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032, 193814643850628739958152744041743058858484088269609293429408490294552345005365776962194365813796130165113184925621, 51510606914703888409341761261103125433754505248101513818740574350196563260563818621033222936301769697693287778876, 502702742677974540308798846750017003106263447846689040491266463798703222616320168069962523670400796196343460832764, 86989835783586738140883150201327374176124588410464188692884973334241681514702306716383785095564084499563152815246, 515511378187957676256419959601984383408150348796281656976955880729383340611785836962788715725367023923811376366815, 119845178983025037005174732553931706284024826223176718982111213579707091766057320315419827781508690979405126062061, 207867794910968434026003881920029657224591376925067493713968219177352819759854486838459675245909787840416982457750, 239399986603216503029402544900610984881160101923294396792665204486222975420081300661354603175384772323551980155480, 306665236132315336961576566094908486196981556971172170145299174389720334940261512384837950321772782983903454058725, 558130280550827068212352576387713811027468233905173944680355562037815257403446113128895937326412940859588204361963, 123471925832174980344066571541132411467266736109103860421447462536930482316849470378251137263190870093702164003085, 146089706629012142384661350988216882483919264673129621404831339166566056469572087759748854086023354002641923689390, 446097892684389219719742914373867457099954499449824602532333181169038249081395758983133906564840000962001976506057, 204029934276059225352901134714823317920576872465404508059719045291560482057171052793698580294637069578017200124432, 412333373143000457741307988470055504576675151299345387733692618218275177027643785881042018546460452418506341967356, 171418413940299360322712423004114364681865276057786947919043883366302567169869592290151559269290446563185553350080, 401593473337411114258578268223784182795068785564101722335215736591292301602077751376477881087346810602041717163104, 204003688543820354337113938494979311981574571424756883928855286926734578790400322291262042466654212377708831289347, 555612926496986208337317871061684502803594375654879680702581403987248292734014139717756900004905653768133795128973, 462785612281910846822645629160953231999037081137615204334672445418078665808070086646804794186256411131615189487813, 77961961618173276050791733447969083544152711482614563228085622136316525792569658878271751219358260960116292497570, 517789370221435419776588087490678991824021927945387533283088388790482913301281733115458601414668206432512998904516, 281870328340314395150658482932699114581743200279996227099530744754750289102031518563761975024621347281374162044877, 60204977937304337797770029325498234132893935850995809547662640467737007197647697381430963693698522962733473746281, 395936787836195675178388359277761575381601972138693830435288611414489963379399027975388601714741876831895709497105, 90921357930302550361827901642067284191268695594120415817202534786924330392421221829361546010764453051928814876700, 238523907687908075601117120608130752369082206676107364350347208286323115036939777325067473364465438898353765093766, 277515010021988996116595000889051160811249034599876556819610707794016612800585201793339332495839495779526504613846, 187215937497318890199135284983515062319988136636108170852591598862524363777870331888216170582220867500042557737272, 411220029331367081136918789112083235781237730079305782620378994961505282090962448446931628731751970521853108685376, 433613620456520979627974441205441942311133790647897226320388205340695256818608765746266662314499649013982035729731, 509613591091334719216567967380183602959933686617275815879939870258332674755345348802452058256788513837941126219238, 352708166022264045150842358964512080203788453464883319778517822047480718640858804837886057264514786742694419419735, 486272357335492500753956372299255798603575392697018451800774427752724312455328655650777691830508441976819499348269, 1291533249748053824342851185451970324561531056195308125673915619130780992270420765078102812914222570167615953050, 520707501920546816250915326019351261090208813534492143136485743644939372232638461802625700978801768541842624647274, 272359456788721692618768612190222453304838934916628492701462591276450281926223118982602858211688086607842351391495, 119534191144397164327417397593964021477488683311215644770010641745736480039094209273092223959694752862193314087240, 394945131470603614379767959704654538029557537489316246092982427107641617479545488843535929537498546432123287486437, 395979428475608101765230328218274625986674115712051764903732593018454264017781340199795540039285257513438842708672, 322101629493887220159199019582810892418957941946300752245249462093036697035162212557261470168522953435341905295650, 60610073299031334532969727880668989046838926047395613981473675505442500833244137863225398782029541439420403686372, 492582431835005621441922899995666806499437611069193099072247918597047415020628078410849119945608854080040163699375, 356290614124448077864884136922409291617128370298210212357882465167338600485728936925448944675136056707929560080237, 469737185578879122378016959759297464132272432425745272107998534197014940235018335349886398896979254122985841196030, 522871107234918024128768136315123497251902274681110489386594944387181296826024289163431880961506314580935567743910, 407151723612481391724375429193917289623669496278028982297086458062111012958436324350527302865535766565677711383191, 597354385774970715448797740483856119139152021834911852144490298736330354118482480147237280491305029710326837274157, 541106433608213985607913120402276000940203625086988929757276286018099336445558864548353610869729642196223750468493, 417269959280528548156948994397262973057821055108288565091113745409730174626359955737489143948177504667498654245449, 165844467199853002181647516786815801413939363188955720855463610698066730208657222822269457713666541555820608908443, 54875733171006797537647859403084623422036246809497621662400918381496284440644503330411668895858884933248328986102, 465819050441857934210906305127374377291850450707906416261994960542649394393702032587209990932960399224341143990297, 369322923825463715724411404444452360125845865658673947242361968271863944079047696087621731311243573179527276498509, 553158781749591211954659671173145767949897795287325677938373702443265138456771264711232588438786042792968904732769, 409812013938165700887519758386718364160025926340003407045361393371862966914817952304595560620453598830906305966865, 494654868138757552768371639418237489264099471894419220273147503624077564865563661914136003656825657044284503346448, 583613295252460993144403074130901622751986348055784728175987246652496523293580989652454868505577305787293683850652, 45623098408168398769971239387495928980835555721564847009059790575158770295430426790200773274288087331109699336204, 39196430635656777174378129146834600960125068266405306877726260536750371354188413207203531511343645151492477471286, 269811462520469960288594953357779332541515563494806499705455036716689694055741096626927182558039773813984145657639, 56129158162087034209035841739296133948708529713411817898928727109770418208078239244331640522507423413446203417794, 524210107239750288249530336771864024916995632570549267972428294539507299820629133801771958736839361325798918246415, 74499040113803277306263886217659673645883223840279171192334357737741618882160648968176974754905084576184804774369, 537566085689080717108870646705458338163437075433046077845999622035879463636776663759447985884960181167857417860517, 67053890181708018909161683393261532526993578729770554741021482840348299866927821016301415949708659944497709907470, 226687291544149270579995169198961617407190234578516732237756117257869929434434889879973211444301745820066870869034, 30119130560797352224094299766590747178156378314088092947830899847927767559391822485618397327733723834195435500170, 273554685078063587415670757725663508130498751998110442807136494763920302805098071555958936900406570453984774374060, 87980277743580170573607118853300224477595233902389343863665172738347967268089655736029345194767280704236057718111, 415325115863346791298232938393411393462777451386243842830553121689594926353646948497680883539360608323603975987452, 291860381996369849963997875749710331697722876276851205203280910491894467229365951220031470367159168511107680106262, 554653569462940342418063467925252548314485118886100002832290030505991378878498660088540140703141291011055029173137, 323189774384600834625013268084915768916855209746568551595158521873406091567687194674213765428238599317205811518692, 271805885895959097314720980134407607645324820417975238169874050425279962478579515969226563851125481000349196674810, 273580504244152469063405670227951980303621824057876058884978331188257821496852334599050020207990127348359965113465, 89994080154200685717636930068317931325931168723237899144166312528962957042842197915530047017893088501681215899095, 179903529806043505032581494908566846659773117049401056767669943330229935007822437549131470977810261112485254094386, 337553339737054880017288314951575451797426862530219763936855885416298554494199226261714888518914541341927073075939, 55576723594346882914517616915509260915444308762551400560217462518909289055446940809390878002725822401595827206530, 16748220768196858904499918524709172735166549515085689048938405549141121222201553686060172878474455615920723669801, 317380564633191615800168658676142557493413060315417096622564923156521630376263849705099633192226251101432134441153, 533990888376667129575141849433166253104032964155895368357797314378260092470904627861359175864364684662961150582207, 51339665999563119517609216115086272052501396280925354694804471629521639434841281422984348587180771099209184749005, 598751671521816401429095343374521592165563401213195481604556405443389323390172923217639290327197434030974530635632, 502516418942980462174586089858060912235797554801782186782319843655355616321036648106166017773986280053024012403712, 96757697084956246010025820107260538706827163135748809142998937362457169471061108292297066769079020843197361323396, 160715027762704553320571142674023737670353756130518440136900430091151963142004047232920245715827837173811719927140, 279138292123840748082780689543574043699162822819208361733228093396335579794292477744981338016264347327181324984710, 76445842054689324523514421681098261857514827631364695255959418519245612571199123499205752729124353901548286671941, 383675319414133753635121914615218464358220814208747712016103562476157464944897131756675168140846189629485664787044, 260741648290568813857849033448155840373964568801980310694295413631289231242930901519918814851819352903132884286000, 572815144956474380133620797676157654285774633299428534205241845335783095326631133195133798583360396067031309578073, 326258465939147178368353573060965288327891986807699582822092415027094204965326681853802159504539722937811913340954, 270266570242986488258809014590807152136633692716132669770748395523214017062557603428657196661342410476403164567952, 594635668324174018778140793057815156885870465660609865234586849536688338135131804764199647040009222634146148815637, 112066852946512058163194024984815176069074331367673763590415760757313750687675218022751871678411881684718198988959, 72643140251973593561700085821570131390914743121754868577502110904091989089708201436984242838820806097191225214858, 418558767829526524235103555737958351573183096833081038769308995724925326439890724874671213539641031754157727776067, 196559288823369030489094238610617412012659194878611686482089456487889879135369906410569754176462601644487717691079, 484475844260869041475828428835126624027291693283800645559775410528136122290210564467730445814182429120097372738911, 397895531572254423225385975618860549078025992059379971480526615942245245283818149065605766495091059477544617632303, 173098235745543952336517747078283517802667869630628062474315240281111485771833849083340162673485620557610425012773, 395438744730241817782361196255681827924847041028664896503460681041226871979986416514203189980456170013127549062319, 470021990867207717347003710359490169212637212255796418181420825247262094876084196634243149241752002339736588912053, 116393009019558569654503508922282193810180596603376432764270301486325221610807518426481578453602546466299515294456, 312679236344738874814229979243462639486594453393064312671149009880980836289564409215088541509970023077739205203468, 125633612607015147027292740679836345332097512816636698981581758992992116056276272361001165705597842757882238693825, 550545747650576990464265884382499274254872311986381675090751886824037811235625095205217845451891396561893492715391, 582344947379262203945082609921047126789902458640974947174265099323728700596079597139164883619347159500887293859913, 597445807393853093495564866081359122814348105478914638258595339515168987499771664924728981250079847198831836930965, 203086100710322798737771097067197649738932976573837729229038404179992238381339090779534246758253939763462200026384, 366083021996787911206272856169665720981308167177143125303074466648545813452157612764258146407782634619278092168081, 568425067761875823198893591966757461338470700675615033946429149483970138055665377562238998722395767377075284081587, 292063178202410186631443519138674436645163233411161937085629856088259050827382985093506892763617302007759121037731, 572237520943575841301998365238940412928982617335768155394691567092595694943290938278464533099223273214233507106207, 130730938892686892107630262721901246969052318133502728671984157629171554435251506312878040499761922665301495030981, 185117108148352276973404708807613996548096583954940273525781406848525491758486946236965943611210198389159091280333, 37060990092986925132287820152354618271473589014825595897838753632315007172710154561879917551705194656825456571032, 403396730776194870459199627544122636010870768257463359235766775533882938128146112838489577777497432203020030499998, 390519053219213422305599109947414047895590808796368085342860468917268018310638864392199371679272174634278410878307, 128444781947873592602609418783055715736876557725608932301613294446934930933474014020041434831899064316552264614235, 543291373538613455155809248493830432520680330961337677793905220928838352322514565851452650441518480234729892153780, 488514444383813071753894478409325136755661751625837651637348989332739608743318097848609715931362718450900659714726, 345584582429475420526208382863826459005483455209655712636957752389218040279848223862500232738960994712140028026289, 93010878843154734421543561265196548806562081923037074596459052686633775723171466088126269822057315393084026072218, 12533412965882925987419497258660569237455714460582608620237638858642686843645624645184949324869641399446820464020, 562770032030414047557952904910126027215456025343530350248616818594366525600180778011275466074764589844321872364272, 128451705070871056157396910591766296038989235798264982434769256144115712608648937222298167066517556774062311420353, 490278961434267039693706795888817653385586689501848271165345121922956317504140732421546020494675482464550410472502, 212287543946551782522399704940695532581109453008804375002654843122502975490312129477869621998080277682674199046031, 351228167329138957128592454766411142609836239330479331051630155591459798299725613134325016512314887321869487481161, 364056580106158102895694571253671943571916920885795142960090311722444269241247963009814588199874030295862636577768, 323410613174912128865174768949092780979646178505039555025194364419990442219941948707117457621400459111231556621585, 555979459475319018276106133189578589964687373772995549423813902773304274184448885651570001083614054140692063026580, 471645896888183848879918063770091917659270906648819201901346651975957177950753583099047587304484006413716362087065, 595746107902898270905714635379070716651708771264047581902664532594897071557252807014533004074458867603957329534516, 557816517693603351719661411054144374250247040672226934534604151399902780319198098821629853612396635344596388943480, 75653615683769023911143698869320584951015514055697266638646507368530841035631560833198288977975782471517557394092, 386729218862361591185009654369415880766336899946663823664818477204172007165198875809899277634660190797185025579614, 393108265477944240661308455550612796769200470498502703905073280606596277788078742986164286625262059483908055127428, 365065802583204450004435661912506592532468753723399406740663534070289404492293680764078659588454240436160849321237, 343474792575856700080726394177083134771079426798042359193966109700850531408037245425173307797050676647933775237484, 449270583610225180914452784540333562631570453995885992409935055758994173533991695282410200635020830187612444056607, 152477148608000973940085532267319492932629609199964217167273279315109403426434432473053141371160594251975646390787, 215758046810520029171417357963508549726865838830930981174495643955719506571398771447950049727234258305885220507020, 388644732079570479249894814593945177309689613386566508292336098907992239994635374799070003303374928382563877494312, 33174396496627497383579687586254392056231321534282758587681567913835717050445163816449882425899904436708697640574, 293328356964375951072242072976851267186828242468018707810599907336525314670450502681522283876131924077746023996643, 292804486280753504026674757794166015519590385505528937148184945726179320137391480944836180610675717906694042510411, 278315915715399524055936806996907092937794467054749462150463756152176847617395557111508306851465386462011262385630, 103884040577296119486012754822466682224025370872916939490159319500421058932999421365377738193002421767097172706341, 111463652129659874006915288174831654634146152513640366449316440114829594116719772451443937868409442532699879776869, 475152124260969797265060453354454799124845717445357239027249597786029156307488697633998763174770332805926500738683, 220597335944113643138040910019263318251616203954548724660953303915089233301354511542662225751359573592406567125779, 460838912228809947843094986154780694841314087685379351551107763714127613789323858795003275958350186756130179585099, 140183105024444619512158726537661171898184380568070161231133567610679885584873426652521827961950911404383912561621, 100258312363732149931656549158547430770829888011033153048299126820116382987576385251423248018523377569893042593237, 405290867185420593972711092047858403431415058957648108848290712855486205273135789994549738296802436972506132007215, 256955277068974586752505570703153051582682851398012077625721880852140628262494489158976679841716540706155916871083, 598549159802958710401362839481280273681933957841944662088149512518476573000011803427513695903373248355980692446393, 308263288681016807641714404434630877489176754884164049322636274036076916608089721011418189274379096133290778967977, 8342859679410179631729508842147337278025979845268212054683951869690623917413242667876438120214556608223950514653, 439895086294728342454449126955941890844828534912064877350830376651948083146591737071488196253116258629344717466258, 91881226123407259536921548434174382841001791568169293198769940131230256611806601058471105885254628422499512141440, 377266324363766263400630205724731218877243980277025204567255708828742612895175112462476548764041808998472515741645, 116673062533491873681185131034931580572262852751033929144868000941380674942800523209276875356733463592351603448680, 57238242567269156027816815706946539463493497634492900168501163766058930300567388616552782194562204025116893421410, 589774086517371498643669747060802896861503240906569357013148621028285639980785543690656162836694887880501379427719, 299125626128142030020988742420785075132372751191528474146303145649473683269241675130370288768899920531289674244113, 304688395547666111898109663337992917557352968749730125549180444196974698222351897080702952045364871753888027443342, 482739851676824100473920409347215848398789318900117561465297399614115666738614477259195415015272146741220074932513, 223546862652113236935862556158177901803806229739994958195958127700830125319767534179348037800919714328649801362322, 150425375689725206871177727482717625428944121456212788472446922564113718518867636855506280578641904259888006038685, 143374483079122348274771015162872747263883105211675941440480524305910827744168931572051691220561136775398957657059, 128633351158033453796356108560970241527889904619011394383277988372280437398843373552825146090070247278923404428730, 249625701621261544438183108711205773478938560640571200325127252485779481701078452759513943692466279038851599018511, 330098489762871879773681019559732262466172018773272582308614672671671001199307865518506835519360693927579848132122, 97272570979206528424127336981516817168566955222510512261839537633559389914877185855268875504270285494647179225542, 74718841026645027941391238796126141775030441881552798010185595153873780524478674202965665888738730228577064111032, 59009205910055868684561742529451214311094377006520731342399475542159755492342086349692903126315766192176134558364, 147954106872023713951463145691216475084430006306060416221364896834795769425749212897622105818492094458111589403860, 555992830271936179812799550002813412539390844307434015514327261249472823762801208645240806724751727789206958497458, 459223438688559571249116685914649450095540121668933258507609746609794374539448063463326591749261191192370815662117, 571393209200912648822312183637054598815269397678580613768957089116765483865121162495918269935152288322187647411253, 177286186824084038346767370297094817293812392957721642873053028629715330336525966361030541938870465423944241324109, 587491267113142201933590855412985429253948652679543672927232780837039223665539177593879438262959884768626979925026, 121073719992748558849282996502703446279240313956823650619682240860630373634948798695523514085879310433388769297911, 326992821821879354165502695961028240084978294787383957718963930070776372845305415470613976088436935751047043512627, 55897462658973985554837453480984923331777372313619418297379632868358904708526448610515770876401568010074036247, 474281517111080897542557845865286041097457650249727914745876496139882777461227076272058949306156001543709356614827, 40880447006931568560802817837347288973549001731224760995212446282117046967004745589464560120352241602331262757637, 199377582253379978414081552664345738394226248383486423477706857549702059554694037264958719644482986837756496613246, 67583806809325529684782118654476643411516600285151896093983454855502714712133346956141976654071062935812737453191, 452546341988439193982297214011678766258506490290911066090290647614068455151806621409756646430532117713333419814200, 63154079944843452528208874183624055953361990336542165468695871390964383215223885775202331596927466794955939855669, 334551033942583568474606741839213957101383590286251155186668543235920975897931743928357631453433934808796703330473, 437000125133660712403788025992205090698484430907657894066272071296035483375078474260228687865444802416063967634962, 79996507523856267942889507576300340014719316733731500178081582238768493408405645914333660158893963260211116177267, 136957270824318341027124989034235585855646981093281453761145461440890955503793684517186875995202144027265329969201, 280204753198588906275980318398478729285287961542920285529979812275266316580102545873587416433404212703776245726478, 537734235993878341769434982550042490365981751251428660237179942734374485415922424357453321846937022328664895920607, 498357256878949571854248804622370932859926894994690120526235824883083753765132401863605500892090016764206939698756, 593183658694608014094449104249771865876595121367209656250471158771632486392533730913932393504513988512194994235126, 471525047958971655208534107052287853913949987926476676197514310320411235020283503103705707957701802098089852040455, 515550195522086342769232739520750768345601850976320014312405876943691700378141377151414091085616391824613041356222, 229784654767967355149909497709811119368560654037206880944035229827691011815016913131119422451043820980926353941725, 217169654015051285238559403576147518221573574303291047729813710960725792892550445720464605476174663800328177597453, 445865555254101127829958642102675927687168710569707725467286103803938348116926832834254624089519482737855028080263, 83946997792088073746354410376458121354546477090285151121896293987266118404260723878401677521317330022928683440101, 472119354862263268431251633432424976904384210603399093568806291862332048310282050100842204125396472101319620313029, 46843467515693389983627938872598324284244171067988563260495985345821466093790361374194115630948136965603015643581, 277302589126799360982750111603442360555051934636756171066424884732490616874962892980005637968336486277371298105284, 37796860324947087933757452089444569583341754367174335457777874936449439863762482510080776848131952814291888228252, 329201662631483519275850208043421059140347420462580260818216051307977255139454956805683010032538225008290753339066, 410958260744814455637908317160979333881545314073457621559204623145344687279791103290567233048673594441768330391568, 391184069150039601440639067557184862816991051523817132396666190555512106382919904848895224325098711230221328168893, 341778180155955688649827271577690269253924367106359453768062062983194302766144996692233530585116870343939549344048, 482885184891891026832543019680624112333051960746415331234199075553060933581630480706330420552017650892318225421994, 227417029879602291913898154454350465334192275455983368980997243946371067766121862949125088496933933053493304375082, 131891059077173823480681683274809296700667012054595015489329798567668841455882278540434006611778254351469315756836, 103977685400575936876007245351080422734569291709540152622222483086840011211808484758839889045266405362833100572217, 430039690420862864710328860317916251552162738538460131045295388990486621940999260820629946807283129550503791042360, 336054039341779369078755981618338727567421739252984379060088264565052065080902800664605952509539644185937023210384, 414650487301520195860820485747902373712957920758077572646321108690388934071745453432265035539090489903222596288408, 589576193361941267176015154197092338077060428665767302320550323024382985851379047593411265195718688560873123744185, 218382333622730104159935425552756841820388948639519923842495333910150980936866251625988964615764772159578862214025, 2542356543181698813075957157401385706512468063673241076844194782908937880847391489213422972872487843717747974071, 19012712934576590810330358701965194246607393288484627129050567402003333386833300009773236871643918870071025370112, 261459449945270346696260426170010104493420330959761424072408598127181246567262293489464049721489266230568086023687, 393057872763078249377870634042993942252544393136978340205701555086856991894130814830449765311294161681995357980571, 31706670785655144489258744219717253455873175486088498446357251628824725653898017817866303775262383346847940227722, 352845629675989592022318947558037109666715372268243939061740352176833050420783754677666411876876865226448815643420, 579523499570692157776642365278787278074363193157128877724940050501652213832135926670258239249988403301949338255538, 534781322034571849183222718240938369181782069830117215874801137890227720544463940037268498986061166881241864175911, 293947547828174245724554745263997068016996177889470503383528004805559670712802640725469343616840367100443153534752, 20256488447976344493484944853334005566670073013412177398480406734598723283264289836587474269370253077015786359305, 475307340957345844876811923970449788514706891727480716267956523131203845997503382023500463149439850432076379159007, 9532193777031501443256432870520743234491840911054244783623102207162388499144070592024440812057106927678514406207, 30376455906399256126534181227692885553266283699913099449205248506625206632827693466133644861846223565145288661633, 310323302397755654510284518631138079981439265632852684852876254116989091445393487579911757256043570018377230904180, 407387187512823516321154849212634322952876110252179375736935664859854509488826142049903683991617538259494461983206, 211765773488300500716796064525502573590145731868562963063378748592341237756767589777342751660513980880169703658019, 118119996850569812443799306306875048213209686043987665925365129711742300844060014347898233682054000714610165352429, 456288037921986114882644161559494182818651772335241262800783776696209877706906644069180867207555069937013686421247, 321798425169971169912343295962697085577508076571119888196289113181080013814133443673221049860354996979915353284172, 324976521789232911848337505841284978746361536915903971011255451438673522500730537005137182463678372897314198988595, 395621759076694189110473461483468243816716472466025836871653502259071450104902960119128530517955567830675053452079, 539300517585750216948117617165146582589224695990488749904551961039061424290129525221984586819908097960720708938354, 29279302128607422250205549520059282069518559284219582605487413142781822276106373289432262133635053599391124926385, 554047387889265384869858916477442181952403597250555948392949469296673941793381852004501421929101000148453680659392, 117780825424837288494479009381221759361151487239443821133102414888864152904732196195473813006762420646998382258677, 513764579681988270425418630365712613073908798769959690739998792846173650211508078458011456784363312999085649615413, 421686906289957894155024887354760839265000904451245772175308131137467275202489561700021659858819873604538650489994, 420037832423259525388141394520857134457021929872555809167052539034540217718781279113965175987358081438109891771580, 36451605745112040602804954235939462081346791770310181663631699054048414835838956409055640948581948016033003511333, 65866443469866248828119099994518897685990064406903627156894902667947376070679854260383038634727146436274230980496, 27676413701492447763964945205769602759768347623741189980278225943728587187940271050634054217590942659542302722334, 500312789935788689187812810985806111797362028998353677843819125485045576943472901976055579663665267905809820905862, 520064354401353505774803720281331074080600746212325401527048530022713769008774050816490541356142354757805595273068, 495854656037423684061417113244964481431602915324717605570975073575414392233479237472936965636133612283412033946051, 91739870792230359210043046401786959190045929124141709653873699398574077579395785555200462734509728806350612588545, 484531754577892922131892661653620989224382080321025512011181426678442547912964573223048519566085582623517825865418, 112714684344084391078866980839255594355187885339701715768009153551270432322826715969989728340963213693095849427668, 404429204723786534299525333122163342588586991421902466839808468487493896330979873416105908841447535426923681220957, 92404742424217640040375362532444172359091402942418950195520660310216430170054358290537973281349284862065214755739, 224043393969043013532511880223075809120842856165608086692928112430171548569493398551019081676395857489451126409940, 4305919427803364191555497499680058924116536587126751817219863902878291078989381194676206640960307162723876513248]

c = 45690752833299626276860565848930183308016946786375859806294346622745082512511847698896914843023558560509878243217521

n = len(pubkey)
N = random.randint(0.5 * gmpy2.iroot(n, 2)[0] + 1, 2 * (0.5 * gmpy2.iroot(n, 2)[0]))
B = matrix(QQ, n + 1, n + 1)
for i in range(n):
    B[i, i] = 1
    B[n, i] = 1 / 2
    B[i, n] = pubkey[i] * N
B[n, n] = N * c
B = B.LLL()
for i in range(n + 1):
    res = B.row(i).list()[:-1]
    temp = 1
    for m in res:
        if m != 1 / 2 and m != -1 / 2:
            temp = 0
            break
    if temp:
        flag = ""
        for m in res:
            if m == -1 / 2:
                flag += "1"
            else:
                flag += "0"

print(long_to_bytes(int(flag[::-1], 2)))

这代码里有几个需要注意的地方，前大半部分都是根据上述低密度攻击原理直接构造格即可，在判断flag部分：

if temp:
    flag = ""
    for m in res:
        if m == -1 / 2:
            flag += "1"
        else:
            flag += "0"

由于最终解出的最短向量可能会带负号，所以不确定两个元素$\frac 12$和$-\frac 12$是否是真正的$e’_i$，所以需要判断一下哪一个代表1哪一个代表0。

此外，在加密阶段采用的是逆序逐位加密，所以最终解出的flag需要逆序回去：

def encrypt(msg, public_key):
    assert len(msg) * 8 <= len(public_key)
    ct = 0
    msg = bytes_to_long(msg)
    for bi in public_key:
        ct += (msg & 1) * bi
        msg >>= 1
    return ct

使用简化版本的代码如下：

from Crypto.Util.number import *
import gmpy2, random

pubkey=[260288377891444370372615148009023640057294926547602419331406531383682223097787288755377467188515435381259752760746, 322734358011758862401399370931929863052553602421714393280581187496537763321855751120439457234561080720455397490349, 88092359256403564783665281993130133541226601877969436905267415353041909757324746080398461245281826552421872983184, 601684701300110945921036937572461050140352984401874675917155063594305583314408001377505387079690115000992094388032, 193814643850628739958152744041743058858484088269609293429408490294552345005365776962194365813796130165113184925621, 51510606914703888409341761261103125433754505248101513818740574350196563260563818621033222936301769697693287778876, 502702742677974540308798846750017003106263447846689040491266463798703222616320168069962523670400796196343460832764, 86989835783586738140883150201327374176124588410464188692884973334241681514702306716383785095564084499563152815246, 515511378187957676256419959601984383408150348796281656976955880729383340611785836962788715725367023923811376366815, 119845178983025037005174732553931706284024826223176718982111213579707091766057320315419827781508690979405126062061, 207867794910968434026003881920029657224591376925067493713968219177352819759854486838459675245909787840416982457750, 239399986603216503029402544900610984881160101923294396792665204486222975420081300661354603175384772323551980155480, 306665236132315336961576566094908486196981556971172170145299174389720334940261512384837950321772782983903454058725, 558130280550827068212352576387713811027468233905173944680355562037815257403446113128895937326412940859588204361963, 123471925832174980344066571541132411467266736109103860421447462536930482316849470378251137263190870093702164003085, 146089706629012142384661350988216882483919264673129621404831339166566056469572087759748854086023354002641923689390, 446097892684389219719742914373867457099954499449824602532333181169038249081395758983133906564840000962001976506057, 204029934276059225352901134714823317920576872465404508059719045291560482057171052793698580294637069578017200124432, 412333373143000457741307988470055504576675151299345387733692618218275177027643785881042018546460452418506341967356, 171418413940299360322712423004114364681865276057786947919043883366302567169869592290151559269290446563185553350080, 401593473337411114258578268223784182795068785564101722335215736591292301602077751376477881087346810602041717163104, 204003688543820354337113938494979311981574571424756883928855286926734578790400322291262042466654212377708831289347, 555612926496986208337317871061684502803594375654879680702581403987248292734014139717756900004905653768133795128973, 462785612281910846822645629160953231999037081137615204334672445418078665808070086646804794186256411131615189487813, 77961961618173276050791733447969083544152711482614563228085622136316525792569658878271751219358260960116292497570, 517789370221435419776588087490678991824021927945387533283088388790482913301281733115458601414668206432512998904516, 281870328340314395150658482932699114581743200279996227099530744754750289102031518563761975024621347281374162044877, 60204977937304337797770029325498234132893935850995809547662640467737007197647697381430963693698522962733473746281, 395936787836195675178388359277761575381601972138693830435288611414489963379399027975388601714741876831895709497105, 90921357930302550361827901642067284191268695594120415817202534786924330392421221829361546010764453051928814876700, 238523907687908075601117120608130752369082206676107364350347208286323115036939777325067473364465438898353765093766, 277515010021988996116595000889051160811249034599876556819610707794016612800585201793339332495839495779526504613846, 187215937497318890199135284983515062319988136636108170852591598862524363777870331888216170582220867500042557737272, 411220029331367081136918789112083235781237730079305782620378994961505282090962448446931628731751970521853108685376, 433613620456520979627974441205441942311133790647897226320388205340695256818608765746266662314499649013982035729731, 509613591091334719216567967380183602959933686617275815879939870258332674755345348802452058256788513837941126219238, 352708166022264045150842358964512080203788453464883319778517822047480718640858804837886057264514786742694419419735, 486272357335492500753956372299255798603575392697018451800774427752724312455328655650777691830508441976819499348269, 1291533249748053824342851185451970324561531056195308125673915619130780992270420765078102812914222570167615953050, 520707501920546816250915326019351261090208813534492143136485743644939372232638461802625700978801768541842624647274, 272359456788721692618768612190222453304838934916628492701462591276450281926223118982602858211688086607842351391495, 119534191144397164327417397593964021477488683311215644770010641745736480039094209273092223959694752862193314087240, 394945131470603614379767959704654538029557537489316246092982427107641617479545488843535929537498546432123287486437, 395979428475608101765230328218274625986674115712051764903732593018454264017781340199795540039285257513438842708672, 322101629493887220159199019582810892418957941946300752245249462093036697035162212557261470168522953435341905295650, 60610073299031334532969727880668989046838926047395613981473675505442500833244137863225398782029541439420403686372, 492582431835005621441922899995666806499437611069193099072247918597047415020628078410849119945608854080040163699375, 356290614124448077864884136922409291617128370298210212357882465167338600485728936925448944675136056707929560080237, 469737185578879122378016959759297464132272432425745272107998534197014940235018335349886398896979254122985841196030, 522871107234918024128768136315123497251902274681110489386594944387181296826024289163431880961506314580935567743910, 407151723612481391724375429193917289623669496278028982297086458062111012958436324350527302865535766565677711383191, 597354385774970715448797740483856119139152021834911852144490298736330354118482480147237280491305029710326837274157, 541106433608213985607913120402276000940203625086988929757276286018099336445558864548353610869729642196223750468493, 417269959280528548156948994397262973057821055108288565091113745409730174626359955737489143948177504667498654245449, 165844467199853002181647516786815801413939363188955720855463610698066730208657222822269457713666541555820608908443, 54875733171006797537647859403084623422036246809497621662400918381496284440644503330411668895858884933248328986102, 465819050441857934210906305127374377291850450707906416261994960542649394393702032587209990932960399224341143990297, 369322923825463715724411404444452360125845865658673947242361968271863944079047696087621731311243573179527276498509, 553158781749591211954659671173145767949897795287325677938373702443265138456771264711232588438786042792968904732769, 409812013938165700887519758386718364160025926340003407045361393371862966914817952304595560620453598830906305966865, 494654868138757552768371639418237489264099471894419220273147503624077564865563661914136003656825657044284503346448, 583613295252460993144403074130901622751986348055784728175987246652496523293580989652454868505577305787293683850652, 45623098408168398769971239387495928980835555721564847009059790575158770295430426790200773274288087331109699336204, 39196430635656777174378129146834600960125068266405306877726260536750371354188413207203531511343645151492477471286, 269811462520469960288594953357779332541515563494806499705455036716689694055741096626927182558039773813984145657639, 56129158162087034209035841739296133948708529713411817898928727109770418208078239244331640522507423413446203417794, 524210107239750288249530336771864024916995632570549267972428294539507299820629133801771958736839361325798918246415, 74499040113803277306263886217659673645883223840279171192334357737741618882160648968176974754905084576184804774369, 537566085689080717108870646705458338163437075433046077845999622035879463636776663759447985884960181167857417860517, 67053890181708018909161683393261532526993578729770554741021482840348299866927821016301415949708659944497709907470, 226687291544149270579995169198961617407190234578516732237756117257869929434434889879973211444301745820066870869034, 30119130560797352224094299766590747178156378314088092947830899847927767559391822485618397327733723834195435500170, 273554685078063587415670757725663508130498751998110442807136494763920302805098071555958936900406570453984774374060, 87980277743580170573607118853300224477595233902389343863665172738347967268089655736029345194767280704236057718111, 415325115863346791298232938393411393462777451386243842830553121689594926353646948497680883539360608323603975987452, 291860381996369849963997875749710331697722876276851205203280910491894467229365951220031470367159168511107680106262, 554653569462940342418063467925252548314485118886100002832290030505991378878498660088540140703141291011055029173137, 323189774384600834625013268084915768916855209746568551595158521873406091567687194674213765428238599317205811518692, 271805885895959097314720980134407607645324820417975238169874050425279962478579515969226563851125481000349196674810, 273580504244152469063405670227951980303621824057876058884978331188257821496852334599050020207990127348359965113465, 89994080154200685717636930068317931325931168723237899144166312528962957042842197915530047017893088501681215899095, 179903529806043505032581494908566846659773117049401056767669943330229935007822437549131470977810261112485254094386, 337553339737054880017288314951575451797426862530219763936855885416298554494199226261714888518914541341927073075939, 55576723594346882914517616915509260915444308762551400560217462518909289055446940809390878002725822401595827206530, 16748220768196858904499918524709172735166549515085689048938405549141121222201553686060172878474455615920723669801, 317380564633191615800168658676142557493413060315417096622564923156521630376263849705099633192226251101432134441153, 533990888376667129575141849433166253104032964155895368357797314378260092470904627861359175864364684662961150582207, 51339665999563119517609216115086272052501396280925354694804471629521639434841281422984348587180771099209184749005, 598751671521816401429095343374521592165563401213195481604556405443389323390172923217639290327197434030974530635632, 502516418942980462174586089858060912235797554801782186782319843655355616321036648106166017773986280053024012403712, 96757697084956246010025820107260538706827163135748809142998937362457169471061108292297066769079020843197361323396, 160715027762704553320571142674023737670353756130518440136900430091151963142004047232920245715827837173811719927140, 279138292123840748082780689543574043699162822819208361733228093396335579794292477744981338016264347327181324984710, 76445842054689324523514421681098261857514827631364695255959418519245612571199123499205752729124353901548286671941, 383675319414133753635121914615218464358220814208747712016103562476157464944897131756675168140846189629485664787044, 260741648290568813857849033448155840373964568801980310694295413631289231242930901519918814851819352903132884286000, 572815144956474380133620797676157654285774633299428534205241845335783095326631133195133798583360396067031309578073, 326258465939147178368353573060965288327891986807699582822092415027094204965326681853802159504539722937811913340954, 270266570242986488258809014590807152136633692716132669770748395523214017062557603428657196661342410476403164567952, 594635668324174018778140793057815156885870465660609865234586849536688338135131804764199647040009222634146148815637, 112066852946512058163194024984815176069074331367673763590415760757313750687675218022751871678411881684718198988959, 72643140251973593561700085821570131390914743121754868577502110904091989089708201436984242838820806097191225214858, 418558767829526524235103555737958351573183096833081038769308995724925326439890724874671213539641031754157727776067, 196559288823369030489094238610617412012659194878611686482089456487889879135369906410569754176462601644487717691079, 484475844260869041475828428835126624027291693283800645559775410528136122290210564467730445814182429120097372738911, 397895531572254423225385975618860549078025992059379971480526615942245245283818149065605766495091059477544617632303, 173098235745543952336517747078283517802667869630628062474315240281111485771833849083340162673485620557610425012773, 395438744730241817782361196255681827924847041028664896503460681041226871979986416514203189980456170013127549062319, 470021990867207717347003710359490169212637212255796418181420825247262094876084196634243149241752002339736588912053, 116393009019558569654503508922282193810180596603376432764270301486325221610807518426481578453602546466299515294456, 312679236344738874814229979243462639486594453393064312671149009880980836289564409215088541509970023077739205203468, 125633612607015147027292740679836345332097512816636698981581758992992116056276272361001165705597842757882238693825, 550545747650576990464265884382499274254872311986381675090751886824037811235625095205217845451891396561893492715391, 582344947379262203945082609921047126789902458640974947174265099323728700596079597139164883619347159500887293859913, 597445807393853093495564866081359122814348105478914638258595339515168987499771664924728981250079847198831836930965, 203086100710322798737771097067197649738932976573837729229038404179992238381339090779534246758253939763462200026384, 366083021996787911206272856169665720981308167177143125303074466648545813452157612764258146407782634619278092168081, 568425067761875823198893591966757461338470700675615033946429149483970138055665377562238998722395767377075284081587, 292063178202410186631443519138674436645163233411161937085629856088259050827382985093506892763617302007759121037731, 572237520943575841301998365238940412928982617335768155394691567092595694943290938278464533099223273214233507106207, 130730938892686892107630262721901246969052318133502728671984157629171554435251506312878040499761922665301495030981, 185117108148352276973404708807613996548096583954940273525781406848525491758486946236965943611210198389159091280333, 37060990092986925132287820152354618271473589014825595897838753632315007172710154561879917551705194656825456571032, 403396730776194870459199627544122636010870768257463359235766775533882938128146112838489577777497432203020030499998, 390519053219213422305599109947414047895590808796368085342860468917268018310638864392199371679272174634278410878307, 128444781947873592602609418783055715736876557725608932301613294446934930933474014020041434831899064316552264614235, 543291373538613455155809248493830432520680330961337677793905220928838352322514565851452650441518480234729892153780, 488514444383813071753894478409325136755661751625837651637348989332739608743318097848609715931362718450900659714726, 345584582429475420526208382863826459005483455209655712636957752389218040279848223862500232738960994712140028026289, 93010878843154734421543561265196548806562081923037074596459052686633775723171466088126269822057315393084026072218, 12533412965882925987419497258660569237455714460582608620237638858642686843645624645184949324869641399446820464020, 562770032030414047557952904910126027215456025343530350248616818594366525600180778011275466074764589844321872364272, 128451705070871056157396910591766296038989235798264982434769256144115712608648937222298167066517556774062311420353, 490278961434267039693706795888817653385586689501848271165345121922956317504140732421546020494675482464550410472502, 212287543946551782522399704940695532581109453008804375002654843122502975490312129477869621998080277682674199046031, 351228167329138957128592454766411142609836239330479331051630155591459798299725613134325016512314887321869487481161, 364056580106158102895694571253671943571916920885795142960090311722444269241247963009814588199874030295862636577768, 323410613174912128865174768949092780979646178505039555025194364419990442219941948707117457621400459111231556621585, 555979459475319018276106133189578589964687373772995549423813902773304274184448885651570001083614054140692063026580, 471645896888183848879918063770091917659270906648819201901346651975957177950753583099047587304484006413716362087065, 595746107902898270905714635379070716651708771264047581902664532594897071557252807014533004074458867603957329534516, 557816517693603351719661411054144374250247040672226934534604151399902780319198098821629853612396635344596388943480, 75653615683769023911143698869320584951015514055697266638646507368530841035631560833198288977975782471517557394092, 386729218862361591185009654369415880766336899946663823664818477204172007165198875809899277634660190797185025579614, 393108265477944240661308455550612796769200470498502703905073280606596277788078742986164286625262059483908055127428, 365065802583204450004435661912506592532468753723399406740663534070289404492293680764078659588454240436160849321237, 343474792575856700080726394177083134771079426798042359193966109700850531408037245425173307797050676647933775237484, 449270583610225180914452784540333562631570453995885992409935055758994173533991695282410200635020830187612444056607, 152477148608000973940085532267319492932629609199964217167273279315109403426434432473053141371160594251975646390787, 215758046810520029171417357963508549726865838830930981174495643955719506571398771447950049727234258305885220507020, 388644732079570479249894814593945177309689613386566508292336098907992239994635374799070003303374928382563877494312, 33174396496627497383579687586254392056231321534282758587681567913835717050445163816449882425899904436708697640574, 293328356964375951072242072976851267186828242468018707810599907336525314670450502681522283876131924077746023996643, 292804486280753504026674757794166015519590385505528937148184945726179320137391480944836180610675717906694042510411, 278315915715399524055936806996907092937794467054749462150463756152176847617395557111508306851465386462011262385630, 103884040577296119486012754822466682224025370872916939490159319500421058932999421365377738193002421767097172706341, 111463652129659874006915288174831654634146152513640366449316440114829594116719772451443937868409442532699879776869, 475152124260969797265060453354454799124845717445357239027249597786029156307488697633998763174770332805926500738683, 220597335944113643138040910019263318251616203954548724660953303915089233301354511542662225751359573592406567125779, 460838912228809947843094986154780694841314087685379351551107763714127613789323858795003275958350186756130179585099, 140183105024444619512158726537661171898184380568070161231133567610679885584873426652521827961950911404383912561621, 100258312363732149931656549158547430770829888011033153048299126820116382987576385251423248018523377569893042593237, 405290867185420593972711092047858403431415058957648108848290712855486205273135789994549738296802436972506132007215, 256955277068974586752505570703153051582682851398012077625721880852140628262494489158976679841716540706155916871083, 598549159802958710401362839481280273681933957841944662088149512518476573000011803427513695903373248355980692446393, 308263288681016807641714404434630877489176754884164049322636274036076916608089721011418189274379096133290778967977, 8342859679410179631729508842147337278025979845268212054683951869690623917413242667876438120214556608223950514653, 439895086294728342454449126955941890844828534912064877350830376651948083146591737071488196253116258629344717466258, 91881226123407259536921548434174382841001791568169293198769940131230256611806601058471105885254628422499512141440, 377266324363766263400630205724731218877243980277025204567255708828742612895175112462476548764041808998472515741645, 116673062533491873681185131034931580572262852751033929144868000941380674942800523209276875356733463592351603448680, 57238242567269156027816815706946539463493497634492900168501163766058930300567388616552782194562204025116893421410, 589774086517371498643669747060802896861503240906569357013148621028285639980785543690656162836694887880501379427719, 299125626128142030020988742420785075132372751191528474146303145649473683269241675130370288768899920531289674244113, 304688395547666111898109663337992917557352968749730125549180444196974698222351897080702952045364871753888027443342, 482739851676824100473920409347215848398789318900117561465297399614115666738614477259195415015272146741220074932513, 223546862652113236935862556158177901803806229739994958195958127700830125319767534179348037800919714328649801362322, 150425375689725206871177727482717625428944121456212788472446922564113718518867636855506280578641904259888006038685, 143374483079122348274771015162872747263883105211675941440480524305910827744168931572051691220561136775398957657059, 128633351158033453796356108560970241527889904619011394383277988372280437398843373552825146090070247278923404428730, 249625701621261544438183108711205773478938560640571200325127252485779481701078452759513943692466279038851599018511, 330098489762871879773681019559732262466172018773272582308614672671671001199307865518506835519360693927579848132122, 97272570979206528424127336981516817168566955222510512261839537633559389914877185855268875504270285494647179225542, 74718841026645027941391238796126141775030441881552798010185595153873780524478674202965665888738730228577064111032, 59009205910055868684561742529451214311094377006520731342399475542159755492342086349692903126315766192176134558364, 147954106872023713951463145691216475084430006306060416221364896834795769425749212897622105818492094458111589403860, 555992830271936179812799550002813412539390844307434015514327261249472823762801208645240806724751727789206958497458, 459223438688559571249116685914649450095540121668933258507609746609794374539448063463326591749261191192370815662117, 571393209200912648822312183637054598815269397678580613768957089116765483865121162495918269935152288322187647411253, 177286186824084038346767370297094817293812392957721642873053028629715330336525966361030541938870465423944241324109, 587491267113142201933590855412985429253948652679543672927232780837039223665539177593879438262959884768626979925026, 121073719992748558849282996502703446279240313956823650619682240860630373634948798695523514085879310433388769297911, 326992821821879354165502695961028240084978294787383957718963930070776372845305415470613976088436935751047043512627, 55897462658973985554837453480984923331777372313619418297379632868358904708526448610515770876401568010074036247, 474281517111080897542557845865286041097457650249727914745876496139882777461227076272058949306156001543709356614827, 40880447006931568560802817837347288973549001731224760995212446282117046967004745589464560120352241602331262757637, 199377582253379978414081552664345738394226248383486423477706857549702059554694037264958719644482986837756496613246, 67583806809325529684782118654476643411516600285151896093983454855502714712133346956141976654071062935812737453191, 452546341988439193982297214011678766258506490290911066090290647614068455151806621409756646430532117713333419814200, 63154079944843452528208874183624055953361990336542165468695871390964383215223885775202331596927466794955939855669, 334551033942583568474606741839213957101383590286251155186668543235920975897931743928357631453433934808796703330473, 437000125133660712403788025992205090698484430907657894066272071296035483375078474260228687865444802416063967634962, 79996507523856267942889507576300340014719316733731500178081582238768493408405645914333660158893963260211116177267, 136957270824318341027124989034235585855646981093281453761145461440890955503793684517186875995202144027265329969201, 280204753198588906275980318398478729285287961542920285529979812275266316580102545873587416433404212703776245726478, 537734235993878341769434982550042490365981751251428660237179942734374485415922424357453321846937022328664895920607, 498357256878949571854248804622370932859926894994690120526235824883083753765132401863605500892090016764206939698756, 593183658694608014094449104249771865876595121367209656250471158771632486392533730913932393504513988512194994235126, 471525047958971655208534107052287853913949987926476676197514310320411235020283503103705707957701802098089852040455, 515550195522086342769232739520750768345601850976320014312405876943691700378141377151414091085616391824613041356222, 229784654767967355149909497709811119368560654037206880944035229827691011815016913131119422451043820980926353941725, 217169654015051285238559403576147518221573574303291047729813710960725792892550445720464605476174663800328177597453, 445865555254101127829958642102675927687168710569707725467286103803938348116926832834254624089519482737855028080263, 83946997792088073746354410376458121354546477090285151121896293987266118404260723878401677521317330022928683440101, 472119354862263268431251633432424976904384210603399093568806291862332048310282050100842204125396472101319620313029, 46843467515693389983627938872598324284244171067988563260495985345821466093790361374194115630948136965603015643581, 277302589126799360982750111603442360555051934636756171066424884732490616874962892980005637968336486277371298105284, 37796860324947087933757452089444569583341754367174335457777874936449439863762482510080776848131952814291888228252, 329201662631483519275850208043421059140347420462580260818216051307977255139454956805683010032538225008290753339066, 410958260744814455637908317160979333881545314073457621559204623145344687279791103290567233048673594441768330391568, 391184069150039601440639067557184862816991051523817132396666190555512106382919904848895224325098711230221328168893, 341778180155955688649827271577690269253924367106359453768062062983194302766144996692233530585116870343939549344048, 482885184891891026832543019680624112333051960746415331234199075553060933581630480706330420552017650892318225421994, 227417029879602291913898154454350465334192275455983368980997243946371067766121862949125088496933933053493304375082, 131891059077173823480681683274809296700667012054595015489329798567668841455882278540434006611778254351469315756836, 103977685400575936876007245351080422734569291709540152622222483086840011211808484758839889045266405362833100572217, 430039690420862864710328860317916251552162738538460131045295388990486621940999260820629946807283129550503791042360, 336054039341779369078755981618338727567421739252984379060088264565052065080902800664605952509539644185937023210384, 414650487301520195860820485747902373712957920758077572646321108690388934071745453432265035539090489903222596288408, 589576193361941267176015154197092338077060428665767302320550323024382985851379047593411265195718688560873123744185, 218382333622730104159935425552756841820388948639519923842495333910150980936866251625988964615764772159578862214025, 2542356543181698813075957157401385706512468063673241076844194782908937880847391489213422972872487843717747974071, 19012712934576590810330358701965194246607393288484627129050567402003333386833300009773236871643918870071025370112, 261459449945270346696260426170010104493420330959761424072408598127181246567262293489464049721489266230568086023687, 393057872763078249377870634042993942252544393136978340205701555086856991894130814830449765311294161681995357980571, 31706670785655144489258744219717253455873175486088498446357251628824725653898017817866303775262383346847940227722, 352845629675989592022318947558037109666715372268243939061740352176833050420783754677666411876876865226448815643420, 579523499570692157776642365278787278074363193157128877724940050501652213832135926670258239249988403301949338255538, 534781322034571849183222718240938369181782069830117215874801137890227720544463940037268498986061166881241864175911, 293947547828174245724554745263997068016996177889470503383528004805559670712802640725469343616840367100443153534752, 20256488447976344493484944853334005566670073013412177398480406734598723283264289836587474269370253077015786359305, 475307340957345844876811923970449788514706891727480716267956523131203845997503382023500463149439850432076379159007, 9532193777031501443256432870520743234491840911054244783623102207162388499144070592024440812057106927678514406207, 30376455906399256126534181227692885553266283699913099449205248506625206632827693466133644861846223565145288661633, 310323302397755654510284518631138079981439265632852684852876254116989091445393487579911757256043570018377230904180, 407387187512823516321154849212634322952876110252179375736935664859854509488826142049903683991617538259494461983206, 211765773488300500716796064525502573590145731868562963063378748592341237756767589777342751660513980880169703658019, 118119996850569812443799306306875048213209686043987665925365129711742300844060014347898233682054000714610165352429, 456288037921986114882644161559494182818651772335241262800783776696209877706906644069180867207555069937013686421247, 321798425169971169912343295962697085577508076571119888196289113181080013814133443673221049860354996979915353284172, 324976521789232911848337505841284978746361536915903971011255451438673522500730537005137182463678372897314198988595, 395621759076694189110473461483468243816716472466025836871653502259071450104902960119128530517955567830675053452079, 539300517585750216948117617165146582589224695990488749904551961039061424290129525221984586819908097960720708938354, 29279302128607422250205549520059282069518559284219582605487413142781822276106373289432262133635053599391124926385, 554047387889265384869858916477442181952403597250555948392949469296673941793381852004501421929101000148453680659392, 117780825424837288494479009381221759361151487239443821133102414888864152904732196195473813006762420646998382258677, 513764579681988270425418630365712613073908798769959690739998792846173650211508078458011456784363312999085649615413, 421686906289957894155024887354760839265000904451245772175308131137467275202489561700021659858819873604538650489994, 420037832423259525388141394520857134457021929872555809167052539034540217718781279113965175987358081438109891771580, 36451605745112040602804954235939462081346791770310181663631699054048414835838956409055640948581948016033003511333, 65866443469866248828119099994518897685990064406903627156894902667947376070679854260383038634727146436274230980496, 27676413701492447763964945205769602759768347623741189980278225943728587187940271050634054217590942659542302722334, 500312789935788689187812810985806111797362028998353677843819125485045576943472901976055579663665267905809820905862, 520064354401353505774803720281331074080600746212325401527048530022713769008774050816490541356142354757805595273068, 495854656037423684061417113244964481431602915324717605570975073575414392233479237472936965636133612283412033946051, 91739870792230359210043046401786959190045929124141709653873699398574077579395785555200462734509728806350612588545, 484531754577892922131892661653620989224382080321025512011181426678442547912964573223048519566085582623517825865418, 112714684344084391078866980839255594355187885339701715768009153551270432322826715969989728340963213693095849427668, 404429204723786534299525333122163342588586991421902466839808468487493896330979873416105908841447535426923681220957, 92404742424217640040375362532444172359091402942418950195520660310216430170054358290537973281349284862065214755739, 224043393969043013532511880223075809120842856165608086692928112430171548569493398551019081676395857489451126409940, 4305919427803364191555497499680058924116536587126751817219863902878291078989381194676206640960307162723876513248]

c = 45690752833299626276860565848930183308016946786375859806294346622745082512511847698896914843023558560509878243217521

n = len(pubkey)
B = matrix(ZZ, n + 1, n + 1)
for i in range(n):
    B[i, i] = 2
    B[n, i] = 1
    B[i, n] = pubkey[i]
B[n, n] = c
B = B.LLL()
for i in range(n + 1):
    res = B.row(i).list()[:-1]
    temp = 1
    for m in res:
        if m != 1 and m != -1:
            temp = 0
            break
    if temp == 1:
        flag = ""
        for m in res:
            if m == -1:
                flag += "1"
            else:
                flag += "0"

print(long_to_bytes(int(flag[::-1], 2)))

例题2

[MoeCTF 2022]knapsack

from random import randint
from Crypto.Util.number import bytes_to_long, long_to_bytes, GCD, inverse
from secret import flag


def bitlength(n):  # 判断消息长度
    length = len(bin(bytes_to_long(n))[2:])
    return length


def makeKey(n):  # 生成超递增序列，得到私钥、公钥
    length = len(n)
    privKey = [randint(1, 65536**length)]
    sum = privKey[0]
    for i in range(1, length):
        privKey.append(randint(sum * 255 + 1, 65536 ** (length + i)))
        sum += privKey[i]
    q = 255 * randint(privKey[length - 1] + 1, 2 * privKey[length - 1])
    r = randint(1, q)
    while GCD(r, q) != 1:
        r = randint(1, q)
    pubKey = [r * w % q for w in privKey]  # 将超递增序列变为非超递增序列，作为公钥
    return privKey, q, r, pubKey


def encrypt(msg, pubKey):  # 用公钥加密消息
    cipher = 0
    i = 0
    for bit in msg:
        cipher += bit * pubKey[i]
        i += 1
    return cipher


def decrypt(cipher, privKey, q, r):  # 用私钥求得超递增序列并解密
    d = inverse(r, q)
    msg = cipher * d % q
    res = b""
    n = len(privKey)
    for i in range(n - 1, -1, -1):
        temp = 0
        if msg >= privKey[i]:
            while msg >= privKey[i]:
                temp = temp + 1
                msg -= privKey[i]
            res = bytes([temp]) + res
        else:
            res = bytes([0]) + res
    return res


privKey, q, r, pubKey = makeKey(flag)
cipher = encrypt(flag, pubKey)
f = open("pubKey.txt", "w")
f.write(str(pubKey))
f.close()
f = open("cipher.txt", "w")
f.write(str(cipher))
f.close()
print(decrypt(encrypt(flag, pubKey), privKey, q, r))
assert decrypt(encrypt(flag, pubKey), privKey, q, r) == flag

这个题目也可以使用同样的思路进行破解，但是在加密过程中做了一些修改：

def encrypt(msg, pubKey):  # 用公钥加密消息
    cipher = 0
    i = 0
    for bit in msg:
        cipher += bit * pubKey[i]
        i += 1
    return cipher

这里的加密是将每一位的密钥乘了flag每一个字符的ASCII值，不是熟悉的$0$和$1$了。

想试试同样的方法，先看看之前的格基怎么修改：
$$
B=\begin{bmatrix}\overrightarrow b_1 \\overrightarrow b_2\…\\overrightarrow b_n\\overrightarrow b_{n+1}
\end{bmatrix}=\begin{bmatrix}2 & 0 &…& 0 & a_1\0 & 2 &…& 0 & a_2\…\0 & 0 &…& 2 & a_n\1 & 1 &…& 1 & s\\end{bmatrix}
$$
我们构造这个格的目的是为了能在格中存在：
$$
\begin{align}
\overrightarrow t & = (e_1,…,e_n,-1)\cdot B \
& = e_1\overrightarrow b_1+e_2\overrightarrow b_2+…+e_n\overrightarrow b_n-\overrightarrow b_{n+1} \
& = (2e_1-1,2e_2-1,…,2e_n-1,0)
\end{align}
$$
这里的$\overrightarrow e$元素不再是$0$和$1$了，而是ASCII值，之前这样运算得到$\overrightarrow t$的原因是相减后只出现$±1$，产生最短向量。因为这里我们要得到的$\overrightarrow e$是ASCII值，尝试得到这种形式的较小的行向量：
$$
\overrightarrow t=(e_1,e_2,…,e_n,0)
$$
修改一下原来的格基：
$$
B=\begin{bmatrix}\overrightarrow b_1 \\overrightarrow b_2\…\\overrightarrow b_n\\overrightarrow b_{n+1}
\end{bmatrix}=\begin{bmatrix}1 & 0 &…& 0 & a_1\0 & 1 &…& 0 & a_2\…\0 & 0 &…& 1 & a_n\0 & 0 &…& 0 & s\\end{bmatrix}
$$
依旧是使用LLL计算最短向量：

M=[8639902583677674310880931793028177280541434011292290504202065853840987502967193292082744312615700434593144813157877283996511132107220470301049233647133408049028266415548603044821875100911736779016733764651538561081471760073024901013269329030282540268057926893298880605006783804814169640893918174416684396473085843437738560093104518378524427428449369031845530695254533729875357632791209728472396631069254545688073527219830, 16412795671399200780410369416718200126247920664621109172347415680005387903489020995450209711828570735415943889363228088231729204296365628434015660102046415392160980472272559259705186844881452797719608700810640858964540124307963570631307965212179112567625375169247224532541645290209536697657292517320097861498807160219866672156203488965096062697707956833540149569006121676793811420684019155246005879602727894940460106460425, 1002483078449652086908127901165742700721575695431977944228135611564705696962544084765706920800603400348407970043674673111909948831677555786509139726134228930151292393556003965787320346201469741608940033259208434513230462286500445047749412928990508135782414968218031136356601029216877376563453734566125800306022631214791796995657970239075130824719419551039046131552320134110768030600558391775291997167887552475043961982479, 2238951719129102684908508004589371017508128103247447515477314623396874326632900138922634752384371309915247686376088188378411136513128697780426310438781294619639028237392912133929126286576611773410531662546965371159839695457500259703379712133530424987700108668317058486891872074268472615506849525949557819649248663298510166491366824248526632970988729421252090737838283604158996925358054184183912031175441649168801364477497, 5634843816732445026126467098373466021485769627903521660842347695720253281030482413552009914416263510962518645905534351024856098851613741584157560289954680322367708989388356896291579138242423737071936969416183795417059233168737593374557100712180960324956368186029307481493787661489262846069411165605826200576757012590288649575515313112890878467873797655979953750167348022896037285417957167761342222784479775154484055454300, 9186610770346409723100374171388664935178707704940676612563986340255427150913228007547473624373722376412452006509593871272640178049654772086095028603022475485769195013987324300619058730137213629241547292874688026607272301254060765768412491266856867815505612614998943264567979641302858974943094758843838673682824294909500855339786155131092900834359374160001259207411314769180927212657053081774058447428598226306560920557103, 20086923313584400496691602764043099251746628122644779399842432220366854165950153096939613947370676658491693142658541069764999486380151371297168776865169982649753241182524436613459151210953276528861607793419032177588079933942873702274888793149133043040881921816738144320494857431431348403935934220691400258374550028362585563810770890511960106477474196749665991783492371663595335417853709562030925255330540927197410589197346, 16344638306391326377686133680466529244247158645077173788183670515669569922257628136592428719458630174158247262608062501473710159252996556402841773688479781261071952868217032789112171578864311013133034166125522508960509753908661140291243310989744814838516658654858087285501428760026897645388510723360904014743591560741892432193065079183777716928931428528657537811530112798506687040813493577134938597056885544404165334440417, 2612829152363810360381140114448267548309487113451765642875771138774557011657898432249330366979748000196797448616557121603054240633550483300886876115997009072175661113374511516053173148943538562172144361976376460500609759755722891157667525246977951372954709581129289399522608993482768996162810200357621658110354562179066558050350148834136898974813148680250028733112017355078329753267780915289394014243208598474729032384564, 19064240755529577125292283074595989361230925740751604828791433834485710855856801533155956923513647433086102471927289219051556692578080054437968339223710189223092053257138547582773966036253443266822181812437558595870339679800887565183836282812813501470568462858382546100456455622835475204306486289729917538078517665215080886364990781487301918217104266484901312499340347150623781762028474648151175735340611348792151618766861, 3702565937757268048976391733125277066442618380743768416638899741455818391864276934809663789147326816784849214974228391513975011092043466189181524135072744668991818700123641118048186561731463987428008289526424894229838318750539451785156527758792285754054388512341416769819020768917817009268720412709209493639300206208469077070001276757631341988430056132551557700579907926834862070107929804804811568088452140366936341777345, 11502581665457615587254363930374727534860957412318365767186339391962456747857398825121846821211261108113447361990519412493867120624842707484788658261017505214188933491782380457717248447441244784000616729072274616859314952832500266181433915883265604874701734571473682998617103861022495595430816700108408197717973513190148901952092370293707843130828467727037293783684148539875615050978469354573967054299566840777623355696582, 10073083484226771776559359501269382896512475376861352563707048944846887937508361476948371289888897049589767849211355238137412974054578287303103882003280146530845186837491695691790335230428734898979480016209102240902149523701595231852831084035640546876424433409207622149923419358639246084622889479686948602188084403074936426671633324202401473825907348902812619313043234644293320117923314933945154795101196969895143521199483, 18992409093137046378732842744306503603860785524225852139724096390190053840935906726926035874997131679911084133508187235324077341016070148447808448470772128318056137717495126904574038547394615807743718419710808943840981025768473805273816544440631835254252102209159686821504850348775772310988837820388009691813555637320221225893184839014117064201469792554472415820296766165441072313200265279873167507641917097468147741179316, 12008203894395308866804419286918131211163695386800382803649167279012655799569753801988115828424417187344919188165247175430808022391086771474851545255339167112615263516693822036949280138705995693945006477452686019283850377188419366812168825267599287239756656176060444742334708935226087327402356564944368424241454091730626764098428899236088185072241508877992009374541429500266147060644167717198271648252572069852366770066941, 4038832885441543178685778998777010366178385846540652554740976864087276470059402915973964964623701441198410064422128360212066090056314261540125817743157487504771683739028804039509503547125770628097134761153720275162291365442343531369529592717402946253265532741567152583164953954964898610320442871432658088455178094417777512351495473972183676615716829056159421852585171139955117355872271110823592402383029525931751267792629, 19670194103573995335546778884365243181264524353822662897934014963532181109426494031783122562547168306646340318701174006591358124967291240381472860805618047808677531825042365670594937665873102378022268329092094697067984029740301822623602184731823873558795434660094128877563657141012814479754588351209580370149201870079338556937517586419874603443731575388938047952534772975732556105736933783615623583780757885995121940503338, 448587250547880364312998824100142781832002491807797554233277109625321555526950425023215743109760909527612986436313497543133603769113094218925472945334223939771684911674114594383329812680099071618542069490401164113149299269806494788678936049434267166672312670105320059285800764845917405038243022972683567686862055442132133699091060023879225704166728623235301057086116134392930454897470872517830183804157659700625445889830, 10930161231241723347656392354185186093279947414736961273749133046917264525983266922573827501912949183911557744485967859327719400057117437345731516339396700486673896394578991271601789139805337761538463364911028532947314087595485794633342964066494181066852782300122468958298766435768883484054954993425768743684068334128908076033268101822190508581559994522635605495674677985961570352022867982948658497701704571958572471959037, 8912625957861947176692856854564685913647250060559881612290601882706188054788510505473405766899729572895845562443591906130010557402952386484482517393552180643811875543260186615419673392566496124447912269542460226666482647910551668827648093182498966897648613164572222270243359702963101177490336287533554365928047224202986800381789195759761436787301775857956490336462761874360038594427862527456596260884381704781454223633779, 2306551289216069191130454513919221829895901755421732012054334929893242554080663470365833623647910595823559794161380381203244457273338204281828065815403836409342993408047475650247775548054870518506855112285782988053629107469383261669351486184529190835182475578503456288807168306057143062378581633799682759776120760924076418979302287358897599267369532373529226015751378954828919709070562305354324298101375251784620884529050, 4255339440978927655211913099708439239541744749715858205450532296135993491711072531673546488130525220452788120740747243665720666392815530093014478271039742032112194171931906319993753445172382189426854066713529003995100528854075591430543823563496149091625019122021620407298536429119275536878732816760877148779834810333996516623906435500182034146675214175983106767418866525349482073016790959017939121229158782423051437153215, 9873893139520117327959006627839041532640596084122498183275311439807583416537326867898240112497398037831103133225780536794667751621338906594306093907094491162973280124466357134326208711961138712559043474881854410281347249860558412201637927695809309506382983697195652836773807770471078146063769391274295604089026631661057995193996447578694999955394342030970191038699379802329038272700169720344712485611198818958034826301237, 4765089917604817672113377465925141955529222421516223531063923657154702433478270434880545390917216534893263025759911541042026110573924335888049100333952299835341171480017258706209901577677469866704411013270064823075970967687971507570610839591584275076452847872481076324238205066797040752210320592563122318631044755701635637739646416025765614160810641418286841779812770371444583299208365194975180768006212895673072116522386, 6112224947687945480280239711320637787918908433138683424770734756570826229243307796646495301320885785370269249822669591195293264920047304899609677414526321546201923169183273630074677571673196655278790073365810828842079110549121344560176457524241399552011885247148188807289668163473493287160336470378903648449586092642655607573691920693404111756416187219108551575656506522734845257486376035264495521946081148938719828033544, 195388411930456292659004793034783822168552894119815825793239515251988057168890947473241809393054966668062312553975721264016843250888334146134794233076452609281861146295329070151936139818953601652277333969475084082043879066015009690415217938561659533862830515140741722462773302261048996453107340978194386484615281173964478851257661832707168812221430391245333553374969697275213417090199524308016415986232808953337791233555, 1244720792234771369080092658020249943250558558858543228087410218998345534662117779763183654722069027909843499722901164419943926229796467885376166352837320116084647482129514330031374427777713274658505472735592998618829380710477875259621314494025610959270630909513767438377166574595122721020642680480636508393782145457915510494406492704624711370382819548311152206515088909451187140041316879980487624305109667331613444702397, 17420521136158610155456592286731848541982479314642855401677490675166753515234198487007423812022874870146225072931804869494964153944097179858754058711975536064958198128181259089930184414024073207404745484941865020376185583612084575830698697473861393413223317543665696780708006419160734997175211056844409117770896148029948413413830070992404759100435183372428243532877202421584255843340950511372816896926816072148853459897597, 706903708472011058848699822306335654841601117402541259992980291382595513869156934281756720925440180372041334909766487263157124536984532709278378467802794655209393786719712770166975275570907988257884089016583036566222245762906544594817287350363157701978129672388011595734906479201562800232080436561292648589995413689187423799267922779667354879432847963481081819133273312642100271608294867632390722051556035070483171016618, 13588117928036525396131036929216722140727623626773457297456804642287761920269285941755714752389926502053635244735082938908723844163590227890370507021161665584070634134943166185409041414310104540858882424783436357851264149321701932666540464732095496709151056094385506784810633450577104530541976191745761226361392054647950122452702677055536328206478865891505902190711023934956429659436170984452323755148142827783946983689170, 13035612161448099569620637080527976769991099967659035134135726157510271293484224205316460392491491142810512547489719500384339641597134042306613279002050232752593558311676343579221779534892019944116141753798217189420843176613961166129335180457416469246554334190776482345258322812060613256769751208473952032112714346919765236132411088975889482598477817665407310561133545838921580753339246754910148949146829091161220277523800, 5061468190653798738267114315103277995240484866758940466674688031109170357205008555147400605884432466490013550324043153140916286904706720594942806466313925952519739861008671389738724448491617803723488014434597761423015360791986220671348427679576702646137192962379221866734759953356438405870464423279037434471697115717040170596343588013833231257338815360451128669119488799203334539631159855944659628348586189260831916846349, 310519211081224360436038529767369886079208063233638857045321280938913013264485831500988519083286823510448024911412774486006384354093058665586412478745091555621093880910291350060806527846380258780481452221805321697545098807534406639559969270790330318763674434212070131506363658570473180232691446781542261978745471405470147422634838558227017494138965139937056188221867200916092073501864711946128579149564779783995131812764, 7765454929386860718098457667571027065776365809087712130247806423210057380994819419379356255913567513855445325193098721224960552359712259673134202556374845746328084939006183410638772980553376342740123581295433206004604779839814416843588103144731533226288767681739309033321761816241055963854560413354103299523850186399263379947122808750960631330918177463573091711382789330104148605172305241880223088742424771925359262276961, 21279920209240501229319113350331584665790430778846094897524930483118106031814634260802903045495829850399437278182329574699963138929930179421992737117248479197193414157068700951767757037252093980620859984584071460503299890187279597588828028508209377280155232780973353085622102108867131114851476798667397114731024315266211677829660093151838411660005343321511262290101904600206044359113839043382769572874124915349587253828026, 9404384361847700092017917497360922914422495675694955197107944898045656929107075851201447292136561925215747086463268855004949841022671138446351748131867439799577663701934862965438385718226937668810306608404586652755516424859810792109427278538957262669803852485387086606698225561320268174451728686271748237597096162506211489602963953896833644360026423773017344347726848234574166701592970696201428964781400031197865618239089, 11473536515781570615295467590180776005414036990843757506218537332857260548916287699656257748679485492923976380438772031340714031903195664536413478729735501964060575660816573010818951724268030300190364858009842520160469005602716000106343559079229134105037981332746560515786853914884397058119553354501751785487490141582378799261378484951808914485153056302334467726453053631816737123137188339174736559611576619507335456442065, 6658209986765214576523603095408925684859819107411400320441704339845709232148546095393111386992961430272770760133826876144536472235021040569911199220002850001682157274254019940107808579210365324279421587725318046615758025182034807320964209281952211101801085038313213267840401921768361130482812244634047647201542664623820862660431801687169272410840936474148169852200351846151154823648248871251508145387214557197530965990966, 3662147743842078783350403504385983360536988791880409841594842856902008843747184249906408091065206792255852486983899949749040441757153766073770174862371596437255143770762330535544930819336506298143363720373654482508230603611719528450050592020391695607369389318359724713540160798965029351305356511671756157832414716675860595439627182073770194023818550160188620097391401855031574633727321506854349395990238905940067612856696, 7933293379259371913947753225829182973440327166821331624782742813667530306183685142511569661517697089303221887502895505020874247160719683710997562072608556098407772048528722269678632972762531765385931704290441640393166153819226767175593692496736619644331844236704817294952000150386014066539732697524646127418982668700056812006011572693231332529972933598812433064570022253850176804351568177341485541235602653505364414768080, 14070615118184600860551882213714094275919094443487489248696755809883503918195587018270172984608205938888536939875430264012942369576596527716679396096608215568698430682346516654899828724942187624877959402757540416078645260766852866647428645421972345262477895972147694258806702534022844164408377042363711608742060536759496086945857809612633396792905136739597255654549008843569173238058444402641970915726989105904551420858546, 15342946815132442226042116907050674991277073193801523392169239948932666433020608630679091801966034372511342999029292508497887755004306581018004584285609282795773152090001950867971092852778256889890353738132730167551173577706777310439847369540286505119147781133148801979251138693701919045904692041106260141920375686688488149802396671219316061485675475896415179620183729993314843987100325425615893137781286754296462178178342, 3740152297282187181815345820098735405456007044475540504111210108524926232502982744404912884880365972432141621724673777802787744807157725980349110691844313336431011685019041193074796249612246618677944456394104745372829079160559888495080142311688681340347875401650358392693131033779246448214818537452437421066622719432500713770985665015229700477055550680052280279789072242114276313112192777540668840785267601183144210396020, 10185332676507104923693600244914563536350322909616212746220121432434723035761182080872998830142207437310309114085510373952850103117757585120341980926754941337344093553857422551961676140723291586487782410700709958292644147040988012341985875728853255609738370894663167840784046951024718142033286281019071858182773531406479425092563184020268791578909132566309388794626911391615731256258486251046314500831039355225743436984975]
S=28856686525748125802152914172483571798453880654624111179873716369801238646447969551927508246737816822527579725991046201801262381722186539084044859241033407568422008911415092147086235301286167536726137372507078079415577358704181165698320539751269992479349480281465975374187246799267369957964807679383646749609694064517591097971225234359495013928292239934008888234863117359059334395043146949808360202225171337210959511092044766
n = len(M)
L = matrix(ZZ,n+1,n+1)

for row, x in enumerate(M):
	L[row, row] = 1
	L[row, n] = x
L[n, n] = S
print(L.LLL())

先得到格基规约后的返回值：

[        -78         -83         -83         -67         -84         -70        -123         -99         -97         -97         -56         -54         -99         -49         -48         -45         -56         -56        -102         -55         -45         -52        -100        -101        -102         -45         -98         -55         -48         -49         -45         -99         -51         -99         -54         -56        -101         -50        -102         -54         -49         -54         -52        -125           0]
[  511963049 -1748972930   135443271  2141007241   168530726   654055876    12033012   940827915   212025781   123698623   901985382 -1370207622 -1242878842   771265447  1400071016 -2295297045  2435435232 -1191282815  -559966601  -224936431  -503940793 -1022674762  -701146352  1280804464  1170964410  1984050670 -2642144538    58949730  -639159447  -313872536  -298054432 -1741706388  -417405365 -1059473417    27710042  -508983578   805060301  2041567307  1633578349   -46293414  1161603100 -1487428666   233440641   163658364   -13965165]
[ 1799795051  -559814141   667489261  1122512231 -1439469011  1725862497    -3609309   128069845   814156249   -94421225  1208688765 -1674673509 -2394195299   848978613 -2932188048 -1118874138  1466712308 -1342064996  1399707305  1555455609  1295654193  -413114412   119354612  1568704356 -1543455297   -83018100   981868662  -502286930   969512221 -2130585701   975927892 -2427429347  1404335522 -1800290309   176608607  2401202999    63850619   464957007   -80531874    -9532245   247906840  -776115704  -284915479   -53277598  -480190592]
[-1108578898  -881420109  -269372600   955719836  3198294835  -221454797  1183707809   643494132  -105797755  1281777353  -310810203  1068904914   943220033  -780837733  -219276913 -1033739506 -1028537854   823731491  -197816510 -1930508114 -1105439344 -3278765599 -2933982834  2661026807  1582996385  2774972689  -865250784  1182761433 -2506632198  1313119968  1707802610  -402919319 -2001609195  -898100237  -827148061 -1406314128 -1039114147  1558662543  1580084462 -1002302832 -1172859943  -920902447   -45059691  -143358783  -502515063]
[ -861948353  -550803339  -721566137   833436243  -608692156 -1688001377  -417496518 -2085755493    42933155   493117043  2319612723  -289855014   144581736   107545078  3120316397   339199842  1083622323  1090175509  -901450724 -2353956294 -3589728361  1176529435  -242835623 -1526574687  2488782917   340382112  -809500075 -3081278917   237685545   241083091   786774656   221590149  2108124563  -802964330   783925026   662931959  2225503029   124098304    65201407  -855732520   836130807   685642267  1806997835     -159819  -208498030]
[-1553904821    34428182   758586880    40950057  1465692150 -1672308751 -1030001125  -551011856  1797063162   356289360 -2586995321   203399849   -12512997   -99577511  1882527366  -971897577  1607759914  3581519399   -31058482 -3219963608 -3176093842   844137006  -916909799   -14017359   117407725   702320220   311135849  -214848444 -2230921465  1921560207   574024405  -564172783   100440362 -1059662202   516840533  -417050197 -1155707939   481436933  1954575224   867805981  2716839217  -606520615    68855185   100235417  1016225285]
[ 2943040420 -1271019369  2057286282  2282121318   582089958  2977589711    95381841  -522151836 -1875220867 -1111131997  1972653457 -1401781248 -3813481213  1285878139   560991061  -388301131   965012472  -275539522  -618513549  1136053913  -462171058 -1262061469  1885087164  -486367505   354549480  1282222789  -998009576  2922085579  1075230906 -1610609273 -1853645017 -1425998271  -370587649   119765087 -1406530300  1056284235   573224505   461261394 -1248058569  2077443144 -2629719759  -206824950    75909581   -54951585  1156905601]
[ -923370409   -16107247  -652091516 -2831899101  1256501272   -67060596  1491431511  -147165085   661750224    64989899  1197578084  -320995725  2416142990  -619611252 -1845752194    94546149   810948158  -712994402   497420348  -532956981 -3090354977  2394987086 -1862337920 -1576381196 -1823565002 -1502067687 -1535727449  -881254021  2872751734  1230395397  -436778599  -903644803   350068074   551151062  1723158414   715945167  -993503255   530074519   209065118   588691607  2551343438  1113399433  1502133394   410027444  1189477204]
[ 1287795235 -2319574251   429114414  -107822122 -1246764438  2742439084   -77768139  -557014105   557922743  2672284439  1845467513  2098508007  -115296393 -1086040863 -1011454341   552442460   -66312270 -2129892108  2424173850  -776083380 -1878789342  2419002180  -267044555 -2121627388  -107578048  -892111510  -776914073  -901251808  2929338518  -391166389   975626008 -2541722054  1425157708  -137056044   757729442  1386878288  -896432799 -2367479065 -1876978460   704339344   300334204   934375726  1414709998   213085774  -640513403]
[ 2240021488  -296009056   749070261 -2160871407   963522044  -481070608     7654101  -565821911  1270159990  1706655611 -1023970782  -152609206 -2102791807  1168198939  -755473369   683474691   495122978  -205803463  1296709956 -1028930655 -1417901021  2016373399   304854986 -1834266774 -1899948195   677793376  -233484259   929255793   855652188 -1376150070   785567932 -3464751181   545496599   447393536  1654232154   -86866997  -312157277 -3147463805  1116374277  2881221305   932818579  -481114520  1635891372   180438873  -471531177]
[ 3608596134   898135189  -852863197 -2786212551 -1393791253  1789481304   852370548  -753256023  -116000416  -246016729   889381979  -263975218 -1882605724   528688308  -429514545  -364013044   416242977  1552536076   924687338 -1821102231 -1617602688   549834874  1770856366 -2610150185 -2907549897 -1289253696  -191711751  1637704515  2260689944  -995726947  -289954346 -1197167362  1035572642  -466005165  1565186716  1838795002  -347405487 -2790016918   804488538  2815966662  1382532199   732993682     -679360   644086351  -360423393]
[-1455756131   881317816   250615567  2863033898 -1391514908 -2034346575   222078796 -1091883907   897833890 -2173765553 -1592377035  -202497995  -662140076  1902753925 -2828660124 -1756184835  1749196488   198110791   567635031  -774889454  -136596638  1066273010 -1552505491  2692129609   585138928   137603891  3444937179  -353264003 -2098056658  1030010502  3082770789 -2311440725   966727488 -2381536454  -779507687  1145764469     3219480  3030543003   424884477 -1866375924   365859419  1472268058  1035786471  -291557251    85025832]
[  -82835514    24573329  2085947618 -1896109736   564399085   -47359134   412724966 -1072611438   112271799   510323590  2173115972  -517303174  3025293513  -500566332 -1099027967  1704198897 -2240349140 -1270602753  -215638437  1822687403     5885907   102914134 -1673666667 -2726185024  1447755141   650815637  -455474431 -2640487968  2194087458  -150288320  1507759660  1530131425  1328068278  -521639159    68670543  1041868455  1324417858   253723919 -2092871111  -909021389  -940717855 -1330850848  -603298890  -360259039  1674111005]
[ -977830735   607967024     5815567   116328706  1671672712 -3280615778 -1747542613  -453816258 -1406360374 -1115765527 -2157287005   476276066 -1999416523  1896839926 -1666968673   915881178  2551791758  2081226083   107911582  1151197422 -3066324453  -148449326   953897606   -29352212 -2080372802   886553585  2030732418  1385788505   -60043136  -617136365  -420173997   -76029757  1224141563  1642566210   496498557  1117219878   803774696  -251042039  -458507884  1847345675 -1063396447  2026328439   728438473   -39462800  1466555532]
[ 1504675433   175702350 -2119448229 -1864311341  -811229843  -779944181  2369319209  -431542475   889755204   472334557  2626071259  -524144848   497707053   851461929 -1630426871 -1029091423  -312483618 -2443298797  -144558993   634920223  1705206500   694287517  -965571428   857881397   304472883   205460144   305935526   742555833  2241167779   618438161  -180949939 -2659163033   605324514 -2081126261   825720705 -1451194706  -840841334  -645142482  1910077432 -1865198706  1622033017   509542644 -1136080572   529755257 -2348923822]
[-1238770187 -1486513448 -2163278240  -748003890  1402032564  -108873310   178731519  1108515130  1633153542   467495308  3304262125   856057641  1747419156  -680092375 -1191546589   422693072  2035709142   -99516784  -909768986  -921572074 -2404623782 -3190551075 -2393520010    85570747   987015552   639473409  1365575179 -1042262879  1429260445   661079139   618268474   223481443  1289854833 -1230973994  1199840361  -107380427  -462979932   589171027  -706069583 -1380876247  -771001370  1570283546  -641039411    14140923 -1493851447]
[ -479138370 -1074986220  -867430893  -124164339  1489898118   698170675  -897664747  2867816731  1281182992   552083728 -1374448385   170180441  2851150074 -2709824498  1698055658 -1895269640  2540570692    11058043 -1890300752   747492522  -454668814 -1508125984 -1654353267  -509577963  -351706206   156921505 -2319374686 -1279323537  1348598816  -346750154   448885595    85906021  -538185896  1611293655  1776972540 -1318291799   -93512447   984939612 -1036118168  -205743882  2711041279 -1532634236   222972029   314996873  1982711853]
[-2358870317   793044033 -1922231786   122110434   913487577  -604167784  -830541625   280746612 -1643692069   971521663   405528906 -1644010457  3911490801 -2515049320    43334369  2307767358  -245877084 -1058839067  -468752064  1473654201  -664579397 -1106736261 -1586725385  1242019105 -2294940649   655495752   443827488 -1580383291  1022566356 -1323285922   345252434  2423179323  -245376556  3474142639   409858157   783145315  -824532283  1014057368 -1115653068 -1228130501   445639379  -438330349  1504200966  -171730902   276613838]
[-3405074843  1105350641 -1650002550  1554948831  -669913036 -2296139469 -1596260069  -258422626   437839944 -1137214970  -969131060  2280203364  4371003748  1228749280  -505364533  1774814301  -335961929 -1094449402   195765567  -409847934   543252175    59225588 -1496985548   679221806   716317499  1994278240  2722970512 -1609199454  -435320505   677978426   169376921  1648890607   231428928  -274871210   229564255 -1785751429   545500166   241143367   775619013 -1752953246 -1993123257   118224073  -879938665  -829347558   -98743494]
[ 1477267439  1831933639  -794252041  -592186929   269884574  -196712283  2655632378  -510858197  -459927374  -592870680   559637633  -768597952 -2344996681  2503280743 -1989324202   332607884  1054338481   298165552   911161035 -1390606925    40520511  3676503504   413812385   434075955 -1532419693 -2332084334  -875534144  -146950797   669290345  -258311840 -3624976198 -2439179335  1110520938 -2078417447  -584376940   351085442  -274512018 -2431757590  2298063929  1050794692  2324369480  1159283666    79585453   512480873  -326383806]
[  207117246  -104202763  -180751285 -1519119464   -57724124   983813931  -474760681  -809790807   -78714443   118030026  -977700215   646514396  1131705502 -1254576027   452903483 -2744796046   662165927   884124911  1074372700   -85951208  -880483335  2859063974 -1104158549  -965458427 -3005927985 -1166414179  -572488265  -481502023  2994126466   165643771  1692556930 -1045567477  -306612105  -782472848  1991284420  2252355153  1125293895 -1257242583   326588068  2418446844  2418251559  -612381278  -273732891   393821569  1238810374]
[-2196752904   485711041 -1563044086    30796292  -311411067  -606983506   703049280  1126557129  1239775822  -464325340  1547127254 -1830695538  1359305185  -821709430  2754466099   770267330   279527511  1308337841 -1199683648  -859075749  2235777027 -1298758954 -2033854608    32869541  2107162549   547016736 -1750919839 -3571265587  -803916521   467720699  -800218255  3233706180   242566843 -1110004049   693046423  -449047824  2673304987  -559142799  -110167945 -1354650049  -782463117   674839556  -818962073  -920613067 -1114879938]
[ 2009952502    95960594   922575997 -1630906241   949535282   752105956   813663533  1591066902  2109818864 -1010112281  -924939334   336857111  -349949489  -102681143  -145377581 -1172456416   294538376 -1999955534  -640252763 -1222405024 -1450768618   264914049 -2239932344  -858967766 -1794882526   185435741   278443111  3356041580  -803317398  2209405210  1634322767 -1329573747 -2216982510  1039841148  -844413255  -998068263 -1562377246   768814392  1839056197  1639156529   228606110 -1516494873   479128314   371947737  -152347266]
[  420133364 -1439799742   774557558  3152438036   175598042   706262940 -1686543919  -687572668   158023511  -640940606   119518913 -3235061093 -1187009041   449895576  1363894752  -478709889  2589488295   669844472 -2444189822  1374561061   -48966749   145019692   922083745  3101389135   788880242   468987084  2819044271  2051310360  -793256056   239827695   -45375889 -1473238630   258382510 -1992183975 -1103916129  -645105904 -1602971425  2544748055 -2187511059  1343984603    65859082   974919663   511104997  -516397355 -1433086585]
[-2010558553  1390704150 -1475407357    82461292  2237402849  -577257815  1293645570  -418356897 -3346693400  -931305445  1941957930   604893172  1165878253  -926261917   643043923  -206477664   449527995  1042351350 -1068941177 -1602234131 -3334794898 -1114037369  -349243021 -1615785055  -606480830   679610481    25241511  -357110969 -1052157189   732119389   892130878  2361157983   704571676   665275889 -1572444261  2730462962  -652362049  1973293474 -1009093815  -196805976   894126626   401268322  2122373224   952647348  1807443976]
[  699877849  -357600660   145986818   700528911  -617509032   276820800   707853271  1278669838 -2578904038  -817996648   884458373 -3141554555  -226607815  -929976908  1111807522  -928901768   818610749 -3055925123  -369871895   961373644  2305420089  1935105313  1009869571   594429755 -2053166104  1175187710 -2113033662   672280102   283880731 -1479208993 -1662947739  -309206226   360511258  1372434235  -691847904  -203395800  1443716119  -428663299  -592535767  1783835770  1282969170  -577523746  1777292208   693913653  -940723685]
[-1695009387  -255058258  -224843529   239859444   214114243 -3593127050 -1143308421 -1054696180  2291354014 -1417514691 -1728549755   658706327  1808482652   426218611  1548389561  1045943922  -680666213  1378118961   680939958  2080443865  1105607824  -343303664 -1043010527  -177301730   664603973  -282123387   660487675 -3469831595   342109877  2002425153   353839282  2385451501   879492367  -309493405   528124584 -1065839571  1097871403  2178199440   541222148 -1638869246  -525715296 -1190794066 -2197103180  -830151599  1795227480]
[ -464898971 -1641717760  1250269091   119801106  1182117591   107696976   444415097  -468228659  1291464914  -174757981  2432218280   -76238124 -2166323877   466063204   655889149   384767841 -1340865135  -348611008   210634680  -329752184 -1265289094   394353449   528765812   234924884  -626870456 -1075829979   398922789  1556551105   887835459   555308886 -2468011590  -297531041 -1997687373  1114315033  -905254090 -1658771691 -1118456156  1885545874   -25089318  1543894038  -301621920   300762503 -1799405573   966043507  -914910216]
[-1184636793 -2435483806  2937891589   280876863  1468381541  -466145761   764033298  -694139223  -136617784   408856467   210227976   396761474 -2220400628  -716947915  1835764464   128657715  -268226293  3554370347   -45152212 -1592142530 -3633270241 -3861979754 -1352984635  -941679861   547920950  1520821223  -694350958  -845913982 -1325631452  1174635304  1506193350  1236402208  -777703698 -1651496516    33183644  2441825226  1764145077  2376496810  1113167555  1019216501  -349956077   -83789839 -2995783782   822900636  1152979573]
[ -975160155   466090397 -2392903118   101698005 -4151731612 -2269260902 -1961480073 -3158532661 -1513018009  1323638302 -2244350305  1931473748   421400684  1373853969   954410988  1701446723   866385391 -1497539390  1708573421   127847663  1483633680  2393980475  1804808798   -87409404  -601182640  1350196305   121883549 -2478825993  2250569117  -346680713  2430454909   -98292925  1700633113  -283962183  2407655826   179824577  1569153064 -1642443605  1266176884  -100696224  -201716853  1676401531  2831756820  -817586322 -1901900334]
[  807825912  -364673536   506498270 -1442775675 -2020480544   222944449 -2261067330  1426856522  -264869495  -277265655 -1646668843  -433414690    64737504   559000015  -294811408 -2393734771  3062760899 -2790481021  1342739607  1667149231  2669802165  -532678668  1220918392   200269222 -1037442988  1157833591  -251581865   829967948   256542388 -2178220571   436653521 -1356966348   264659808  -572033597   636556766  -129687586  -380214332  -275542652   749149960  -636189159  4634839262 -1036371997   648937033  1228402282   533692164]
[  500222543   574996183 -1143244041  -173158227  2508462471  -673933541  1297590499   173139105 -3542994995 -2195146073   868397217 -1525681194  1213109821  -623046131   180403569  -108045239   711269324   111093638   157838634  -378386915   496013832 -1884814225  -328694669   133313004 -1124161688  -213828808 -2840392655   -62059223  3119531538  -711968296 -1794937232  1032450243 -2126275297  1703878108   989990391 -1679264106  1385357532  -193335692  2235318070  -384399225  -330263518  1689659915   702417772   249856222  1401204562]
[-1409902564   345757986   752752530 -1762797310   722548611   871462987   306129381  -798450459   886111072   963307593   783423643  3424989642  2107960766 -1804579981 -2420932877 -1816684135  -902667735 -1572497278  2211234818  -151593601  1064064952   319907534  -848387934   877944986  1595113562  -299522316  1168007845   239233963  1031247977  -841872545  1549028800 -2422038981  -588245179 -1261270430   723795628   691423736  -183140754  -737009263 -2218121231 -1253684535  -719900558   600705699  -225117971  -759940705  -513443613]
[  -46706322   963318856 -1448805681   820962481  -293535758   323174882  1432344747  2011383254 -1063340596 -1452859020  1577567576  -351358631  2406625628  -128727838 -3585525191 -3785058949   494852003 -2016524093   255958586   264464248   411779620   192944828   533217357  2407714692 -2180194653  -480254978 -1831990574  -899575657   376171465  -941048876   985705357  -972197335 -1438925735   989031831  1309308676   659537551  -832199555  5005899259   107136881 -1524264135  1521414860 -1257478997    -9041177  -479258470  2477445416]
[-1477387540  1340722769   838818695 -1848045343 -1217417971  -150430807  1042595864  -747532529  2262383812   422425201 -2392921144    50834284  -843761353  -268917385 -2560950075   744802961 -1836597042   -74407720   261932138    54636899  2583082275    77809609  -311372057  1966422684   -32309797  -904015762  1000299294  -311387093 -3055943675   712438291  2540277952   213295843 -2111102086   527274536   991795126 -1316853296   676128630 -1154644427   -21057823  1336305653 -1103767565 -1013649427  1271899383  -476892618 -2682447648]
[ 1408226565   244237654  1687363333   514919128 -1145067857   771686679  -332200324  2275834116 -1441008013  2103366596 -2382606605   217737939  -884204308  1076718532 -1064095371 -1458505308  1291471591   909396864  2107337485  1185318254   697886230 -1067235294 -1099647758  -598269224 -1021474988   420991778 -2094487244  1450199758   528055174 -3029588416  1018547970 -1905622031 -1673323362  -532835026  -302003207   863218937  -283601955  -949323941  -241600308  1967033751  1255681095  -335056546   464563500   501780148  1222930096]
[ -370033560  -478863640 -1364967451   365996951  -248496730 -2329330245  -986235772  -968089186  -277060507 -1681149326  2145852237  -264617927 -1945210699  -485912833  1799094953 -1453000559  1220798744   827462376  -350295305   687430652  -665117340   190588068   598325730  2001274310  -182414795  -258440254  2757880740 -1851482368  1069180176    13539278   237074542  -467612813  2420441687 -1357845871   300954239 -2125943071   853219094   650109366  1868196225  -500206273   571488044  -273913290  1781422418   402909687   180528788]
[-2262855547   806757897 -1423697837 -2929106478  1604137385  -378778323  -702878304   761622292  -381196203    11699580  1848038201  -811296090  1558547388 -2084952723  1933470155  -220554735 -1483349178 -1060376026 -1134850660 -1518969711 -1728342911   765004196  1282479159    11092813 -1852663491 -2797109752 -2186958421 -1873218607   327313992  1750233976   -47254510  2366375420   141075834  1165128220  1096932454  -284671787  1200423691   611159389  1704337474  2254041811  1313933328   953491747  1232094623  -610119409 -1518105695]
[ 2405779194 -1338333731   753759381  1602425985   953774771  2104329534   -82464496  3068331426 -1355998380  -740127106  -429863913   116899374   101231278  -841127178  2585147191   618557686   126145160   948897307 -3196320593   765500286 -1506796310 -1880218858   891992219 -1022122693  1462869990  1363804740 -2323621764  1477237791 -1081346667  -977508210  -346919661   463529419  -618967556  1529580744   117050854 -2805515283   295773114  -229386970   711531921   -20593720 -2513196328 -1473118741  -842627888  -566960865   354196389]
[  -30806494   -69981978 -2306849646  1275206637 -1743381024   -96316097    32830984 -1020845052  -250540489 -1524921622  2371454419  -251969078  -356516475   783375030  -363336214  1642102097   999655216 -1732218951 -1246680002   583205165    75141533  1572629941  -815621341   325669184  1722979685   637156275  1228637914  -699408647  -490244933  1111079870 -1816154267   748184101  1963449717   -24759583 -1504402561 -1175925302  2388405312   941904419 -1341549884 -2029724038  -432167106  2051912288  1947068505  -283260534  -942505102]
[   10114733   122746990   382931242  -849454246  1365971472   799965488  -775759795  1897762705   715122596  2660709421   540760664  1954725415   987106532  -260927729 -2921650865 -1001341657  -989744053 -2859754375  1260186368  -795766150  -348637240 -1707783329 -1831516210  2484165556 -2232271611   690780553 -4003627884  -556672897  -542864428 -1494674536  -462164632   959977021 -1515874444  1132372518  -129489337  -910140470 -1041997620  -166856499  2055315939  -250060088   806540553 -1365838814  -168133956  1470321018  1201381568]
[ 2189841992   316226075  -144243099  3663707195 -2014485905   686389962 -1127229307   719952430 -1683199462  -271165714 -2916421066   172973178 -1956607619   498069049    65897905 -2792952496  2529108741   362897388   -17678207  1513603481  3367355047  -404550883   588278098  1715932750 -1886128264   781525268   640544596  1465064904  -644809454   571803077  2646942523  -662064571  -710458769    -2420838 -1598608159  1226078985  -911547225   415884084   530187131   641198447  1168925327  -104191248  -327193120 -1978938365  -898720432]
[-2415593220    93522755 -2086747483   294452367   952224260  -541548682  1942105298  -487260692  1341244212 -1580040767  1360611685   233697463  2764920118  -597420704   -72866519  2136838412 -1135760089 -1521506062   443990471 -1603522899  -118486742  2086492231  1473342426    74275482 -1403491456  -528777600   776795094  -694992205  -335481199   992516341   225002780  -571340974  -680012768  -519243135  1542147414 -1820650577   832398066   -25115010 -1771537957  -874547015 -1739054991  3319310333  1944726001 -1359766756 -1119376670]
[ -606350057 -2496934848  1075246742   832919041  -972189361 -2597694252 -2402797548   366447522   291817937  2276260696  -187387128  -247053587   292647811   636794071  2415228447  -458060169   619076934   138908485   556689451  1303760561   302004406  1177292956  1303055862  1030191193  2022632702   186656568  -268944213 -3161956248  -958424758  1449308542   112026687 -1624575213  -660439808 -1665507258   664757422  -182437899  2886749558  -689496248   568078917 -1150037599  -901533191  -549289188 -1327824658  -395415595 -2081935788]
[ 1049788516 -1157230722  2978787167   732433284   612497596    -5139774  -864894906  -614911703   364828793  -434640855  3244264559 -1579827208 -2993513766  1293678505   120215708 -1059205350   -68039661 -1452732627   504251819  3115283356  -369539900  -853911244  1995185079 -2451338595  -775520932  -306593997 -1102394350 -1201260160   913679234 -1407780318 -1272728215  -818614651  2738825364 -1019685220   306648610  1026162644  1669993631  2870413278 -1261364278  -840965909  1461358877  -380224143  -659088604  1228353650  1468129195]

发现第一行为所求的ASCII值（带了负号），转换即可：

M=[8639902583677674310880931793028177280541434011292290504202065853840987502967193292082744312615700434593144813157877283996511132107220470301049233647133408049028266415548603044821875100911736779016733764651538561081471760073024901013269329030282540268057926893298880605006783804814169640893918174416684396473085843437738560093104518378524427428449369031845530695254533729875357632791209728472396631069254545688073527219830, 16412795671399200780410369416718200126247920664621109172347415680005387903489020995450209711828570735415943889363228088231729204296365628434015660102046415392160980472272559259705186844881452797719608700810640858964540124307963570631307965212179112567625375169247224532541645290209536697657292517320097861498807160219866672156203488965096062697707956833540149569006121676793811420684019155246005879602727894940460106460425, 1002483078449652086908127901165742700721575695431977944228135611564705696962544084765706920800603400348407970043674673111909948831677555786509139726134228930151292393556003965787320346201469741608940033259208434513230462286500445047749412928990508135782414968218031136356601029216877376563453734566125800306022631214791796995657970239075130824719419551039046131552320134110768030600558391775291997167887552475043961982479, 2238951719129102684908508004589371017508128103247447515477314623396874326632900138922634752384371309915247686376088188378411136513128697780426310438781294619639028237392912133929126286576611773410531662546965371159839695457500259703379712133530424987700108668317058486891872074268472615506849525949557819649248663298510166491366824248526632970988729421252090737838283604158996925358054184183912031175441649168801364477497, 5634843816732445026126467098373466021485769627903521660842347695720253281030482413552009914416263510962518645905534351024856098851613741584157560289954680322367708989388356896291579138242423737071936969416183795417059233168737593374557100712180960324956368186029307481493787661489262846069411165605826200576757012590288649575515313112890878467873797655979953750167348022896037285417957167761342222784479775154484055454300, 9186610770346409723100374171388664935178707704940676612563986340255427150913228007547473624373722376412452006509593871272640178049654772086095028603022475485769195013987324300619058730137213629241547292874688026607272301254060765768412491266856867815505612614998943264567979641302858974943094758843838673682824294909500855339786155131092900834359374160001259207411314769180927212657053081774058447428598226306560920557103, 20086923313584400496691602764043099251746628122644779399842432220366854165950153096939613947370676658491693142658541069764999486380151371297168776865169982649753241182524436613459151210953276528861607793419032177588079933942873702274888793149133043040881921816738144320494857431431348403935934220691400258374550028362585563810770890511960106477474196749665991783492371663595335417853709562030925255330540927197410589197346, 16344638306391326377686133680466529244247158645077173788183670515669569922257628136592428719458630174158247262608062501473710159252996556402841773688479781261071952868217032789112171578864311013133034166125522508960509753908661140291243310989744814838516658654858087285501428760026897645388510723360904014743591560741892432193065079183777716928931428528657537811530112798506687040813493577134938597056885544404165334440417, 2612829152363810360381140114448267548309487113451765642875771138774557011657898432249330366979748000196797448616557121603054240633550483300886876115997009072175661113374511516053173148943538562172144361976376460500609759755722891157667525246977951372954709581129289399522608993482768996162810200357621658110354562179066558050350148834136898974813148680250028733112017355078329753267780915289394014243208598474729032384564, 19064240755529577125292283074595989361230925740751604828791433834485710855856801533155956923513647433086102471927289219051556692578080054437968339223710189223092053257138547582773966036253443266822181812437558595870339679800887565183836282812813501470568462858382546100456455622835475204306486289729917538078517665215080886364990781487301918217104266484901312499340347150623781762028474648151175735340611348792151618766861, 3702565937757268048976391733125277066442618380743768416638899741455818391864276934809663789147326816784849214974228391513975011092043466189181524135072744668991818700123641118048186561731463987428008289526424894229838318750539451785156527758792285754054388512341416769819020768917817009268720412709209493639300206208469077070001276757631341988430056132551557700579907926834862070107929804804811568088452140366936341777345, 11502581665457615587254363930374727534860957412318365767186339391962456747857398825121846821211261108113447361990519412493867120624842707484788658261017505214188933491782380457717248447441244784000616729072274616859314952832500266181433915883265604874701734571473682998617103861022495595430816700108408197717973513190148901952092370293707843130828467727037293783684148539875615050978469354573967054299566840777623355696582, 10073083484226771776559359501269382896512475376861352563707048944846887937508361476948371289888897049589767849211355238137412974054578287303103882003280146530845186837491695691790335230428734898979480016209102240902149523701595231852831084035640546876424433409207622149923419358639246084622889479686948602188084403074936426671633324202401473825907348902812619313043234644293320117923314933945154795101196969895143521199483, 18992409093137046378732842744306503603860785524225852139724096390190053840935906726926035874997131679911084133508187235324077341016070148447808448470772128318056137717495126904574038547394615807743718419710808943840981025768473805273816544440631835254252102209159686821504850348775772310988837820388009691813555637320221225893184839014117064201469792554472415820296766165441072313200265279873167507641917097468147741179316, 12008203894395308866804419286918131211163695386800382803649167279012655799569753801988115828424417187344919188165247175430808022391086771474851545255339167112615263516693822036949280138705995693945006477452686019283850377188419366812168825267599287239756656176060444742334708935226087327402356564944368424241454091730626764098428899236088185072241508877992009374541429500266147060644167717198271648252572069852366770066941, 4038832885441543178685778998777010366178385846540652554740976864087276470059402915973964964623701441198410064422128360212066090056314261540125817743157487504771683739028804039509503547125770628097134761153720275162291365442343531369529592717402946253265532741567152583164953954964898610320442871432658088455178094417777512351495473972183676615716829056159421852585171139955117355872271110823592402383029525931751267792629, 19670194103573995335546778884365243181264524353822662897934014963532181109426494031783122562547168306646340318701174006591358124967291240381472860805618047808677531825042365670594937665873102378022268329092094697067984029740301822623602184731823873558795434660094128877563657141012814479754588351209580370149201870079338556937517586419874603443731575388938047952534772975732556105736933783615623583780757885995121940503338, 448587250547880364312998824100142781832002491807797554233277109625321555526950425023215743109760909527612986436313497543133603769113094218925472945334223939771684911674114594383329812680099071618542069490401164113149299269806494788678936049434267166672312670105320059285800764845917405038243022972683567686862055442132133699091060023879225704166728623235301057086116134392930454897470872517830183804157659700625445889830, 10930161231241723347656392354185186093279947414736961273749133046917264525983266922573827501912949183911557744485967859327719400057117437345731516339396700486673896394578991271601789139805337761538463364911028532947314087595485794633342964066494181066852782300122468958298766435768883484054954993425768743684068334128908076033268101822190508581559994522635605495674677985961570352022867982948658497701704571958572471959037, 8912625957861947176692856854564685913647250060559881612290601882706188054788510505473405766899729572895845562443591906130010557402952386484482517393552180643811875543260186615419673392566496124447912269542460226666482647910551668827648093182498966897648613164572222270243359702963101177490336287533554365928047224202986800381789195759761436787301775857956490336462761874360038594427862527456596260884381704781454223633779, 2306551289216069191130454513919221829895901755421732012054334929893242554080663470365833623647910595823559794161380381203244457273338204281828065815403836409342993408047475650247775548054870518506855112285782988053629107469383261669351486184529190835182475578503456288807168306057143062378581633799682759776120760924076418979302287358897599267369532373529226015751378954828919709070562305354324298101375251784620884529050, 4255339440978927655211913099708439239541744749715858205450532296135993491711072531673546488130525220452788120740747243665720666392815530093014478271039742032112194171931906319993753445172382189426854066713529003995100528854075591430543823563496149091625019122021620407298536429119275536878732816760877148779834810333996516623906435500182034146675214175983106767418866525349482073016790959017939121229158782423051437153215, 9873893139520117327959006627839041532640596084122498183275311439807583416537326867898240112497398037831103133225780536794667751621338906594306093907094491162973280124466357134326208711961138712559043474881854410281347249860558412201637927695809309506382983697195652836773807770471078146063769391274295604089026631661057995193996447578694999955394342030970191038699379802329038272700169720344712485611198818958034826301237, 4765089917604817672113377465925141955529222421516223531063923657154702433478270434880545390917216534893263025759911541042026110573924335888049100333952299835341171480017258706209901577677469866704411013270064823075970967687971507570610839591584275076452847872481076324238205066797040752210320592563122318631044755701635637739646416025765614160810641418286841779812770371444583299208365194975180768006212895673072116522386, 6112224947687945480280239711320637787918908433138683424770734756570826229243307796646495301320885785370269249822669591195293264920047304899609677414526321546201923169183273630074677571673196655278790073365810828842079110549121344560176457524241399552011885247148188807289668163473493287160336470378903648449586092642655607573691920693404111756416187219108551575656506522734845257486376035264495521946081148938719828033544, 195388411930456292659004793034783822168552894119815825793239515251988057168890947473241809393054966668062312553975721264016843250888334146134794233076452609281861146295329070151936139818953601652277333969475084082043879066015009690415217938561659533862830515140741722462773302261048996453107340978194386484615281173964478851257661832707168812221430391245333553374969697275213417090199524308016415986232808953337791233555, 1244720792234771369080092658020249943250558558858543228087410218998345534662117779763183654722069027909843499722901164419943926229796467885376166352837320116084647482129514330031374427777713274658505472735592998618829380710477875259621314494025610959270630909513767438377166574595122721020642680480636508393782145457915510494406492704624711370382819548311152206515088909451187140041316879980487624305109667331613444702397, 17420521136158610155456592286731848541982479314642855401677490675166753515234198487007423812022874870146225072931804869494964153944097179858754058711975536064958198128181259089930184414024073207404745484941865020376185583612084575830698697473861393413223317543665696780708006419160734997175211056844409117770896148029948413413830070992404759100435183372428243532877202421584255843340950511372816896926816072148853459897597, 706903708472011058848699822306335654841601117402541259992980291382595513869156934281756720925440180372041334909766487263157124536984532709278378467802794655209393786719712770166975275570907988257884089016583036566222245762906544594817287350363157701978129672388011595734906479201562800232080436561292648589995413689187423799267922779667354879432847963481081819133273312642100271608294867632390722051556035070483171016618, 13588117928036525396131036929216722140727623626773457297456804642287761920269285941755714752389926502053635244735082938908723844163590227890370507021161665584070634134943166185409041414310104540858882424783436357851264149321701932666540464732095496709151056094385506784810633450577104530541976191745761226361392054647950122452702677055536328206478865891505902190711023934956429659436170984452323755148142827783946983689170, 13035612161448099569620637080527976769991099967659035134135726157510271293484224205316460392491491142810512547489719500384339641597134042306613279002050232752593558311676343579221779534892019944116141753798217189420843176613961166129335180457416469246554334190776482345258322812060613256769751208473952032112714346919765236132411088975889482598477817665407310561133545838921580753339246754910148949146829091161220277523800, 5061468190653798738267114315103277995240484866758940466674688031109170357205008555147400605884432466490013550324043153140916286904706720594942806466313925952519739861008671389738724448491617803723488014434597761423015360791986220671348427679576702646137192962379221866734759953356438405870464423279037434471697115717040170596343588013833231257338815360451128669119488799203334539631159855944659628348586189260831916846349, 310519211081224360436038529767369886079208063233638857045321280938913013264485831500988519083286823510448024911412774486006384354093058665586412478745091555621093880910291350060806527846380258780481452221805321697545098807534406639559969270790330318763674434212070131506363658570473180232691446781542261978745471405470147422634838558227017494138965139937056188221867200916092073501864711946128579149564779783995131812764, 7765454929386860718098457667571027065776365809087712130247806423210057380994819419379356255913567513855445325193098721224960552359712259673134202556374845746328084939006183410638772980553376342740123581295433206004604779839814416843588103144731533226288767681739309033321761816241055963854560413354103299523850186399263379947122808750960631330918177463573091711382789330104148605172305241880223088742424771925359262276961, 21279920209240501229319113350331584665790430778846094897524930483118106031814634260802903045495829850399437278182329574699963138929930179421992737117248479197193414157068700951767757037252093980620859984584071460503299890187279597588828028508209377280155232780973353085622102108867131114851476798667397114731024315266211677829660093151838411660005343321511262290101904600206044359113839043382769572874124915349587253828026, 9404384361847700092017917497360922914422495675694955197107944898045656929107075851201447292136561925215747086463268855004949841022671138446351748131867439799577663701934862965438385718226937668810306608404586652755516424859810792109427278538957262669803852485387086606698225561320268174451728686271748237597096162506211489602963953896833644360026423773017344347726848234574166701592970696201428964781400031197865618239089, 11473536515781570615295467590180776005414036990843757506218537332857260548916287699656257748679485492923976380438772031340714031903195664536413478729735501964060575660816573010818951724268030300190364858009842520160469005602716000106343559079229134105037981332746560515786853914884397058119553354501751785487490141582378799261378484951808914485153056302334467726453053631816737123137188339174736559611576619507335456442065, 6658209986765214576523603095408925684859819107411400320441704339845709232148546095393111386992961430272770760133826876144536472235021040569911199220002850001682157274254019940107808579210365324279421587725318046615758025182034807320964209281952211101801085038313213267840401921768361130482812244634047647201542664623820862660431801687169272410840936474148169852200351846151154823648248871251508145387214557197530965990966, 3662147743842078783350403504385983360536988791880409841594842856902008843747184249906408091065206792255852486983899949749040441757153766073770174862371596437255143770762330535544930819336506298143363720373654482508230603611719528450050592020391695607369389318359724713540160798965029351305356511671756157832414716675860595439627182073770194023818550160188620097391401855031574633727321506854349395990238905940067612856696, 7933293379259371913947753225829182973440327166821331624782742813667530306183685142511569661517697089303221887502895505020874247160719683710997562072608556098407772048528722269678632972762531765385931704290441640393166153819226767175593692496736619644331844236704817294952000150386014066539732697524646127418982668700056812006011572693231332529972933598812433064570022253850176804351568177341485541235602653505364414768080, 14070615118184600860551882213714094275919094443487489248696755809883503918195587018270172984608205938888536939875430264012942369576596527716679396096608215568698430682346516654899828724942187624877959402757540416078645260766852866647428645421972345262477895972147694258806702534022844164408377042363711608742060536759496086945857809612633396792905136739597255654549008843569173238058444402641970915726989105904551420858546, 15342946815132442226042116907050674991277073193801523392169239948932666433020608630679091801966034372511342999029292508497887755004306581018004584285609282795773152090001950867971092852778256889890353738132730167551173577706777310439847369540286505119147781133148801979251138693701919045904692041106260141920375686688488149802396671219316061485675475896415179620183729993314843987100325425615893137781286754296462178178342, 3740152297282187181815345820098735405456007044475540504111210108524926232502982744404912884880365972432141621724673777802787744807157725980349110691844313336431011685019041193074796249612246618677944456394104745372829079160559888495080142311688681340347875401650358392693131033779246448214818537452437421066622719432500713770985665015229700477055550680052280279789072242114276313112192777540668840785267601183144210396020, 10185332676507104923693600244914563536350322909616212746220121432434723035761182080872998830142207437310309114085510373952850103117757585120341980926754941337344093553857422551961676140723291586487782410700709958292644147040988012341985875728853255609738370894663167840784046951024718142033286281019071858182773531406479425092563184020268791578909132566309388794626911391615731256258486251046314500831039355225743436984975]
S=28856686525748125802152914172483571798453880654624111179873716369801238646447969551927508246737816822527579725991046201801262381722186539084044859241033407568422008911415092147086235301286167536726137372507078079415577358704181165698320539751269992479349480281465975374187246799267369957964807679383646749609694064517591097971225234359495013928292239934008888234863117359059334395043146949808360202225171337210959511092044766
n = len(M)
L = matrix(ZZ,n+1,n+1)

for row, x in enumerate(M):
	L[row, row] = 1
	L[row, n] = x
L[n, n] = S
list = L.LLL().row(0).list()[:-1]
flag=''.join(chr(abs(i))for i in list)
print(flag)

其他赛题

[MoeCTF 2021]BBBBBBBackpack

from Crypto.Util.number import*
import random

flag = xxxxx
m = bytes_to_long(flag)

backpack = [1]
for i in range(160):
    backpack = backpack + [random.randrange(backpack[-1]*2,backpack[-1]*4)]
print(backpack)

backpack = backpack[::-1]
l_list = []
for i in backpack:
    l_list.append(m//i)
    m = m % i 
print(l_list)
print(m)

'''
[1, 3, 6, 23, 81, 199, 670, 1844, 5535, 19547, 75437, 259056, 974664, 2399609, 7304021, 18537736, 38733276, 143785607, 300890806, 778420517, 3112554961, 9955080778, 34625138877, 103531993246, 294207209833, 632363887456, 2341888528510, 8736224869982, 33727228149167, 113026240109398, 334534210335245, 754812282783351, 2871232541211362, 7147990367228081, 16813142520913249, 62232346665698392, 132813746566508109, 436969187287191174, 1371311321857557068, 3465499917202578303, 10761115866584374884, 25998484366411649657, 81986464388691181616, 324842980726420787162, 1063428202306999892763, 3318046410585817603032, 12569059003729082352479, 29822650425811094387624, 89829868596281155601134, 207467076929560545986692, 424101883375592006882573, 1410057940679583010646572, 4795250448769489602371933, 12419955465903295439689190, 32127052925660652338148413, 121768246803017981541739592, 286293639144639999224246905, 876618562849333372078886060, 3495370549956845610130431964, 13777448384830441398471073019, 45339968634224370226443992856, 159636974047457043534720001443, 403806399587759901542286515690, 1190949464093267805434271517577, 2625636206558220580206955200643, 5447410189447132699195152662348, 13798370097217657917056458399390, 42652195271813913821236091812630, 87624112365004035907264763291796, 295833079631922620770335225824586, 717255284196409248439771704866883, 2119024457898120787521595829459142, 8097762744600097674390735606807128, 22990496332708170421088808438995636, 55268619563994680834441597248247582, 157779112538179073738464223501777499, 553561084981889545670380643023607621, 2094594867042850711386606235023415160, 7427564397983932982484534762285032864, 28541899514275079822011638819911534081, 59854615377110931361953157015440306520, 137071568336121640486639449884477676903, 434368553369190183317274206512577489165, 1607515956833802196435755021284640023303, 4247439813046769661567823675143526066989, 12252982336388472725165513300377051313644, 43586970358791422986656986286232849952290, 94754002216262928157061686798919700234151, 205403633516427560050027271636224615375855, 727922215919878343821825296552148942903123, 1541646353685774868780093433673052445519807, 5703469721749658936787093922654529457118594, 20762100689139896330208273986505541316962105, 80195197197818086812949239946286778357513961, 198522126001869063688321920177617046841212852, 719060816608760633741229682178956301630549900, 2171712751463320729665634385979825928332317622, 7968526190188064156742281507099763347000210904, 20302513556821857703528100337806260797703562338, 54967103106163860243927426134510653397499429384, 189866376897538250029834405810321956080892995934, 516088075785491414669664215795496674103100750375, 1531616665488077085604100033058238685259376456655, 4795563798371064843556375420641263389159268373753, 12715206263244537077480789152826620386135239585589, 45628223673569886022145657218662773486560769778049, 127988774487590162169660910342623736153210927472871, 429761810968391607465089641939438991272623610573254, 1694286408402338132220805654166083638884822137745848, 5577419986858786911316434594350519553014729018524982, 22146179230778265190752372551893625479326089828877879, 78983119075073724439850825731329386811892547014513513, 165805826557531832743325076551678254671357810872202277, 525687524776397669648788242907896052104054917192402349, 1596680185629512867035574394423929715498386636216930988, 3808351509446054183279144714875260973968494634290203802, 10792542598439044383994436390450612942036864538927761344, 31776077718298264756461043701077481610506447838959767949, 69483787236434708634666641366101673156349500969799745632, 212620878051727200345257734337176214877612639791408110401, 565705372069455623425268706185184158331866127768259060570, 2228971348185635371906791535156337404926063871528397270892, 4859328204121938264839760465087547752629065763656619388434, 14185348803209161448182653444177464165713091554806223414499, 44242932119616103779840255273986809836494122475150635493273, 156176016196847319874949580221731690886061627436916661422852, 472567672907289753186461661432798790751774534772655287936877, 1765317440470718113352833182911767208733594355879647245836603, 5835719030771522391675663002032404790451900100534570526468736, 14528961633147270325279483890277955669830128461595478399405580, 53503137764341373520101774208921450303897226002280491351371881, 153340302591307960181257267214621247064964249027062324798966650, 467036429085212303265974827129085622046910166509299763268535756, 1760478013800716951650816419888923889893355872867499404847043361, 4791886951911545137378952129838133145784256723738609871941913863, 19126760116038883506408830737976498053029475253123685318001466609, 51635927378821965754946959553487670084314385367430813170544188707, 203944552994591250724882161307279862158139878326498083669171922709, 718868928147325949276701359623063723395455731358210896767864810436, 2005627527854915017699090052821431775394584514441537184407714355949, 6108484926321410509000933490330125849664844216966621898372849074206, 15273733259375332107091552084526951416159646708621190826219429490015, 34145117254940196604842578208457005181132408450899191627170638987883, 120825229084143066199868275091825674337472013226784591902132114229359, 387687667198606192147021527980207738864855944986764666796629571317797, 1461874344207808204456192497546273455901754164965322967295868406627707, 3258300231591322626530795072101331694347928535549768492906530809069244, 8874418273687545553519370439384854004509761935319681848589844232674343, 26555971104148502495508475192114409958713364020252024170586326291995544, 56653286369586527413345416396708661964062474995701742952261047069623359, 154383566127721041301459355493059400704799197964228029280865862358894596, 341393868848806018386217706353404785528207249510734290203621418976352706, 1171362524761660822765817023463786914069613269413196584856696440695273738, 4194882148022101614597714583113090146333385168895367467002069867303753334, 10081717223153632058965668126630772845024206141591578024505075742926631137, 39590555580101758090745061229221178837429140073072263518741551403983751377, 124978669991117804453179514660098523434116842472570073354436333226196401318, 285677744249355467333640461312079508294900634926466871637187648581093663108, 685643590088926190360498081484403342771108281930489395367499236756131358960, 2509513194338799699151211958956210034789618340347017416940796124375457114430, 7869725510782496795692771133398729561144872690341264618424961946628895219979]
[0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 0, 2, 1, 0, 1, 2, 1, 1, 1, 2, 0, 0, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 0, 0, 2, 1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 3, 0, 2, 2, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1, 3, 0, 2, 0, 0, 1, 1, 3, 1, 2, 2, 1, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 3, 1, 0, 2, 2, 0, 1, 0, 1, 2, 1, 2, 3, 1, 0, 2, 1, 1, 2, 1, 2, 1, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 1, 2, 3, 0, 1, 1, 2, 0, 1, 0, 0, 2, 2, 3, 2, 1, 2, 1, 1, 1, 3, 1, 0]
'''

这题的背包密码和之前理论中提到的不大一样：
$$
m=kl+m’
$$
所以可以进行一个对应累加，求得flag：

from Crypto.Util.number import *

num=[1, 3, 6, 23, 81, 199, 670, 1844, 5535, 19547, 75437, 259056, 974664, 2399609, 7304021, 18537736, 38733276, 143785607, 300890806, 778420517, 3112554961, 9955080778, 34625138877, 103531993246, 294207209833, 632363887456, 2341888528510, 8736224869982, 33727228149167, 113026240109398, 334534210335245, 754812282783351, 2871232541211362, 7147990367228081, 16813142520913249, 62232346665698392, 132813746566508109, 436969187287191174, 1371311321857557068, 3465499917202578303, 10761115866584374884, 25998484366411649657, 81986464388691181616, 324842980726420787162, 1063428202306999892763, 3318046410585817603032, 12569059003729082352479, 29822650425811094387624, 89829868596281155601134, 207467076929560545986692, 424101883375592006882573, 1410057940679583010646572, 4795250448769489602371933, 12419955465903295439689190, 32127052925660652338148413, 121768246803017981541739592, 286293639144639999224246905, 876618562849333372078886060, 3495370549956845610130431964, 13777448384830441398471073019, 45339968634224370226443992856, 159636974047457043534720001443, 403806399587759901542286515690, 1190949464093267805434271517577, 2625636206558220580206955200643, 5447410189447132699195152662348, 13798370097217657917056458399390, 42652195271813913821236091812630, 87624112365004035907264763291796, 295833079631922620770335225824586, 717255284196409248439771704866883, 2119024457898120787521595829459142, 8097762744600097674390735606807128, 22990496332708170421088808438995636, 55268619563994680834441597248247582, 157779112538179073738464223501777499, 553561084981889545670380643023607621, 2094594867042850711386606235023415160, 7427564397983932982484534762285032864, 28541899514275079822011638819911534081, 59854615377110931361953157015440306520, 137071568336121640486639449884477676903, 434368553369190183317274206512577489165, 1607515956833802196435755021284640023303, 4247439813046769661567823675143526066989, 12252982336388472725165513300377051313644, 43586970358791422986656986286232849952290, 94754002216262928157061686798919700234151, 205403633516427560050027271636224615375855, 727922215919878343821825296552148942903123, 1541646353685774868780093433673052445519807, 5703469721749658936787093922654529457118594, 20762100689139896330208273986505541316962105, 80195197197818086812949239946286778357513961, 198522126001869063688321920177617046841212852, 719060816608760633741229682178956301630549900, 2171712751463320729665634385979825928332317622, 7968526190188064156742281507099763347000210904, 20302513556821857703528100337806260797703562338, 54967103106163860243927426134510653397499429384, 189866376897538250029834405810321956080892995934, 516088075785491414669664215795496674103100750375, 1531616665488077085604100033058238685259376456655, 4795563798371064843556375420641263389159268373753, 12715206263244537077480789152826620386135239585589, 45628223673569886022145657218662773486560769778049, 127988774487590162169660910342623736153210927472871, 429761810968391607465089641939438991272623610573254, 1694286408402338132220805654166083638884822137745848, 5577419986858786911316434594350519553014729018524982, 22146179230778265190752372551893625479326089828877879, 78983119075073724439850825731329386811892547014513513, 165805826557531832743325076551678254671357810872202277, 525687524776397669648788242907896052104054917192402349, 1596680185629512867035574394423929715498386636216930988, 3808351509446054183279144714875260973968494634290203802, 10792542598439044383994436390450612942036864538927761344, 31776077718298264756461043701077481610506447838959767949, 69483787236434708634666641366101673156349500969799745632, 212620878051727200345257734337176214877612639791408110401, 565705372069455623425268706185184158331866127768259060570, 2228971348185635371906791535156337404926063871528397270892, 4859328204121938264839760465087547752629065763656619388434, 14185348803209161448182653444177464165713091554806223414499, 44242932119616103779840255273986809836494122475150635493273, 156176016196847319874949580221731690886061627436916661422852, 472567672907289753186461661432798790751774534772655287936877, 1765317440470718113352833182911767208733594355879647245836603, 5835719030771522391675663002032404790451900100534570526468736, 14528961633147270325279483890277955669830128461595478399405580, 53503137764341373520101774208921450303897226002280491351371881, 153340302591307960181257267214621247064964249027062324798966650, 467036429085212303265974827129085622046910166509299763268535756, 1760478013800716951650816419888923889893355872867499404847043361, 4791886951911545137378952129838133145784256723738609871941913863, 19126760116038883506408830737976498053029475253123685318001466609, 51635927378821965754946959553487670084314385367430813170544188707, 203944552994591250724882161307279862158139878326498083669171922709, 718868928147325949276701359623063723395455731358210896767864810436, 2005627527854915017699090052821431775394584514441537184407714355949, 6108484926321410509000933490330125849664844216966621898372849074206, 15273733259375332107091552084526951416159646708621190826219429490015, 34145117254940196604842578208457005181132408450899191627170638987883, 120825229084143066199868275091825674337472013226784591902132114229359, 387687667198606192147021527980207738864855944986764666796629571317797, 1461874344207808204456192497546273455901754164965322967295868406627707, 3258300231591322626530795072101331694347928535549768492906530809069244, 8874418273687545553519370439384854004509761935319681848589844232674343, 26555971104148502495508475192114409958713364020252024170586326291995544, 56653286369586527413345416396708661964062474995701742952261047069623359, 154383566127721041301459355493059400704799197964228029280865862358894596, 341393868848806018386217706353404785528207249510734290203621418976352706, 1171362524761660822765817023463786914069613269413196584856696440695273738, 4194882148022101614597714583113090146333385168895367467002069867303753334, 10081717223153632058965668126630772845024206141591578024505075742926631137, 39590555580101758090745061229221178837429140073072263518741551403983751377, 124978669991117804453179514660098523434116842472570073354436333226196401318, 285677744249355467333640461312079508294900634926466871637187648581093663108, 685643590088926190360498081484403342771108281930489395367499236756131358960, 2509513194338799699151211958956210034789618340347017416940796124375457114430, 7869725510782496795692771133398729561144872690341264618424961946628895219979]
res=[0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 0, 2, 1, 0, 1, 2, 1, 1, 1, 2, 0, 0, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 0, 0, 2, 1, 0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 3, 0, 2, 2, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 2, 0, 0, 1, 0, 1, 3, 0, 2, 0, 0, 1, 1, 3, 1, 2, 2, 1, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 3, 1, 0, 2, 2, 0, 1, 0, 1, 2, 1, 2, 3, 1, 0, 2, 1, 1, 2, 1, 2, 1, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 1, 2, 3, 0, 1, 1, 2, 0, 1, 0, 0, 2, 2, 3, 2, 1, 2, 1, 1, 1, 3, 1, 0]

num=num[::-1]
m=0
for i in range(len(res)):
    m+=res[i]*num[i]
print(long_to_bytes(m))