20220427-PWNHUB春季赛-CryptoSecWriteUp

 

EZMAT

第一眼看上去很像背包加密

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
from random import randint, random
from secret import flag

l = len(flag)

m1 = bytes_to_long(flag[:l // 2])
m2 = bytes_to_long(flag[l // 2:])

n = 60
m = 330
p = getPrime(512)

G = random_matrix(GF(2), n, m)
bin_m1 = list(map(int, bin(m1)[2:]))
assert len(bin_m1) == 167
pad_m1 = bin_m1 + [randint(0,1) for i in range(m - len(bin_m1))]
G[randint(0, n-1)] = pad_m1
v = random_matrix(GF(p), 1, n)
G = G.change_ring(ZZ)
w = v * G


e = 0x10001
bin_m2 = list(map(int, bin(m2)[2:]))
assert len(bin_m2) == 167
pad_m2 = bin_m2 + [randint(0,1) for i in range(m - len(bin_m2))]
while 1:
M = random_matrix(GF(2), m, m)
M[randint(0, n-1)] = pad_m2
if M.determinant() != 0:
break
MM = M^e

print(f'p = {p}')
print(f'w = {list(w[0])}')
print(f'MM = {list(MM)}')

代码所作的事情:将flag的第一部分,放进01矩阵$G(60\times 330)$的1到60行中随机一行,并用计算$w=v\times G$,$v$为有限域为512 bits的素数$p$的随机向量,告诉我们$p$和$w$

将flag的第二部分,放进01矩阵$M(330\times 330)$的1到60行中随机一行,并计算$MM=M^e$,告诉我们$MM$和$e$


第一部分,hidden subset sum problem,在不知道$v$和$G$的情况下,只通过$w$和$p$可以求出完整的$G$

有类似的题,2022zer0pts-Karen

原理参考论文A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem

先记下脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#!/usr/bin/env sage
from sage.all import *
from Crypto.Util.number import long_to_bytes

# https://eprint.iacr.org/2020/461.pdf

w = [1431228392312510535526594629978659997684558726389950387726492442798555043880431899561865999893699240538136805233953991064005206813402086756656542482929901, 7088653453775955113267635836900322862857796933643127784611625509616744727249743043523074754590935327965817285448541426479532959702928731921990179805231364, 10301619105035180837870800653432944443335375359099641531234425441182436171267421504478941213131463920435565741091842463038445039580294116239095998807024501, 11413707547353679566491217241662371466424267468467559567372323813213556673873826665149615703273159609618751321084690889506640048613725567078787788727641671, 1137031128465104861903413952756533659501524013448469521333392838679451680073452597411646772067004483700965869550834761952973178029548247826435217234530212, 2401725076278741508338248279299065076336479422415748545571973306129412562947456232110363158197769399744946341402432627872473043753248258245292943960581579, 2264216582027543021531807315374392295140992520158201807673229099572692874565157540874929889959680199170225229924132634151785155213635892002355739154521676, 6492896304272877128798317129915114549579911446272216835504470013878683013035652496808374669354910675470428329152072037295067382897923534527874698538263323, 1205066433747361476875752855554429110141151938267754677972606200900329981907246079051553631244842861912769349341811409233450213763685487290547802000488530, 10957945841561942657881963963933670906818538956361911349706738334563982198748266759728339768551048341009804539725652260336523672166487629699231764542746386, 6605963548095680878845449811053354837581663851277767995905848338383487408943561669525956716430299496973771700224274046946475511809213394786930170597677591, 698677349019160943369265522181770017893469299712366044572703180972911670319004443082214457300020906673566847940015267401258332024497354080579111351823022, 3027355658244460514181140230322534044386289552420724085767923807820836085549413101927321274806485275358666884014807000446274892492381213922126233757560818, 5942903380720625911151565733751199544687951848252039799525931274750100807225521291954350046440286130002809567037314127744976363974408680899670006131288591, 10106820300532855888841703133724849565522211972702735527122590089089795044113821807757254207918400528863284558906920445292688495738265129208934343074935107, 12926601152673566135069604282968113685309577890335120566074363963074886949271179518009201469940348193121561746097296580204612559430312328568698718134996345, 13056457996446768306029704765596196682556080345508955021476561595264629837776607094494685783366807973527889931465115990190403091248646137262436531494474578, 3504964389091287611181114547663813826028585832109644460099688850099394258968180985552590714545199822942740643133943800093222581688771596115043118780261373, 113738031083200732518859738940636691074971334673582805341202076656983007834300883611683797472162355569653633847817372365018177741807434979746161429755685, 9719895696838536942465981916822144811335673554091955309961459530519812524045601040216508013458565904405588114343645874296710684084416972144907553891789624, 1211841627002906404411734032062970689190236281096560653854091191889938057956810150598281553984772568672594438740835038054353526049068321299734604882628413, 12631066613410297089569624001406118979639188227955102957268850069768059363810811011533869336112183038875753645159917180152529378852681370369121043239740513, 1038757893105471675506292117419306597592771806061931070245194486975847780068053339879498048493371326157648354647299945604230971838907456072992155108524134, 12416945376623846173717300933568540465811269790734115463081940079444174685246376948711274587780506630825295676086406349538006291030702694807798284825716779, 481465578888960770073789523841478057672621470201221852706932405213631848728250015541980796682035851943717295328155617834249534288494862397595480670574396, 6687204950955039115060724090435110046042476103213149434725385484071743462226515950345917118026422875356861413064191275091477336832275410022146542037743341, 3660159119982137322191716364361070341417297697288448266807751281456711065238908120188728108315580895493224857729143012338768550341092341648230802939060010, 10623291465417038483636576264459306558885359049615138089951557603287233087536863394854250455900263650318047524188504412776764257812085097758632951098007799, 12466752664723189751902732977762186155016039783844204091021909740059845000957480147564813540690662453603182573063843242542304261411420736030300983424004927, 9392452112686119726797149057985448543459849353309313343063077156579652629762808571665854808418297463204043367302109249415343894894972984384478744684991154, 5850454382166159664293384590806300247412959589985442880551549741048959844374873831731288457414883025928102556896853332436963562190185994446487444895575038, 1495291197455646818704791483602928260515487673066618429797848634889396300859683292882166298332620582954924292116414093986229260848852720417255811072525438, 12004320763474254807389712267732794652743084759761095484033993415476613543695015020088753808301097438672780123286015550037077128549918234377296933357294081, 9529150211789789769518755379932397252116582444846897693960863977847550543617441456853727322927473527347665370214681922432412962199973270874078989732156800, 2526246689314557075094696082780236053550610235592342649683390822852179392319548820822273620794350860311616971041718215295736727214685415646616112228591482, 7835170243940549334590275746978974620405621270772544360576844921832811960500132401001022695318431594994881659584162509479640673812458531232388098613890688, 2032272874164187073346168052067634363227024303547560131374795595228387782209518612604922497847099645494476762970729692190415551960798803635893087198583772, 9373950061355916863194304367630653233722225290687167784450178886235154958583097612187851742847236783873103524290803711017959853383782651422780657152052767, 10188373190879317602281062680880683235577589776838977660912858472388205237274682060480521373646151911519975057564079346800968043362914767328791723314233209, 8630160328169679859928533194305312353022568983223644530782660581526026784848104681220312051223920130895720639525499718590297541071948472971404176823065154, 437293522774303357282081669550310676568241458011955789351785107687741116347699292985546170061153895623415195198125001893432216079097526622700095453430476, 10118272610582226736080143128297107387996115357416393582859651600550905737192077085925073798650185392889670426357956233715225159056093016078257523969059980, 11947608410331590691438881753841949560795136922273167654340994483546181121284218784814291575425777140979351364743618086582243774767221747641043203915922332, 6246547380096321302875535133584832277253183614855306702749574162267312197197323966168658838778919332330193412874806703579094242783204262973282554754281811, 5797491831878589502749733370189336756293180137147829813152029459919796473892341017732317004975678669253235401750258408814922348042647732366623058428548611, 2957284471006458368401490972337626300259665943540742943950598098780658893625059242314892185113971583306296770649205930775347295733738712481847362934837297, 4474614136285396284259265370966850338958583845180466693369372249613701157739763155780791345317380854242689190696684145739316719972340072462838733721239526, 12036191650838368137540761679058605580260017361169403523712853295062219391590897583921073421442572424711853439839466365696823021893094361564998722668924664, 1061811726267682308177501365712557111702350464320413204656713408242523669989245858305231953914214824829375374120126395921311551439828712443425787778690026, 9195473577878323981110629038997485641761991084194574358199394433391424427537740783576965336656489748483977411787234848831408198512002885570895668911250506, 238136255261591314750690622450141252279742334937413212969461443358794676097802055046597681616991048855700640325285842202662466943741479299015636480810964, 1558335372462299302213534917096245100201668643981180268233730109230117968882472740481073955090857646030096721325509994901595366730078413896817137445131961, 12170240438593987644110106612311485351031917639161080976933500347454437679700021668131071405081039194768000363195594630461263991824524243406683167259277370, 11487876350560027778844516660615163314318452567181713404252965272562175971055490991717284904849681669079139884518946409157395875866372789773700780299705980, 8987502383288847653797253311737725620233127875027535539542423779725711611980106568469387927210555312111273149459741824298833519644342610037634825276510237, 2555824078480605650080630230366587097363758578742587606659443372382334332015958938780015467280874187219212154241768030996199770788775094386679842352596687, 747983589184392000243426678260675011869277792238783005861203608987643887222049667892870332209102094788581931366506643772299617272439799987247797189281407, 1887335529683267219550279766998804254773510853235713059441686253433745430626755257701942542119204874311181253508915826961900067000883936867251073495546786, 6793948851689182117040825437694087394098174066079825902245234386932473943975235469225181150707290489484566040807072751187437603828225639665166981878461570, 729534228488464856535229001907175211583011024255007251212354781337994105613776766722923203218312213486704604441488599114413313205313296003417918661423840, 12219440141713086057979633374801208124570964749249611511207821688607041589266348764755331458287240609056076024848570747699911713743038169838045351158322097, 12868365448926946701227003282789027140839737470352084607930619748264039803625682056251511775388537658282702831976770755304562512756090192134782528243608559, 10049561559946680258005157604304335862285562286432993094988911800833385163267795027554481960537607871308429529416765262627677883372168314356926096898415898, 982423366721139890988231468087611409838520123004050821132488714222641048128781810525546077509843713566673994472693084251867468475187243885478374739242905, 643374389949028977015518867988935486705143531417761331436485787309312661871942994315293640322789657996825640030136667769439554894810898620366448505685900, 6234280276760481787105713824803435549484931857378861928821473217799496488841019250033753183751368979711421041094680459370852508424631542132896834781278273, 3260966677002104072987494265773099498521781616677553671887771080762331487370833079729487515124479844202465096698034494994817223080933397239705755902408865, 11772305451783187346345791115601107738192903818861339490847039779654449246752672665917283749779640469769351269310281451909830878795623054113816928197468468, 4111349372976067430249749762810634455769197055467069085514580729028839350522795697622980462571834894300725598344485325797552663362110600808927093972730621, 12948205194213252744810635805657554672209762086787779558205406225503158127731365437062072420171878102515828689440242464144773478229871202804861095055538503, 3898202970356893237872547364182984844278241570721309971832725832505248741149993221212998893352042846482685567945856651887730667820124888064529352082880042, 9733202550771048461939718402900526788233281636320507260796788360299007144503442685882137303602100994253741988114897549689626320560660632834960127734684701, 8633668173115484273370183709144677580217856727778079419229076644248051288221617844516472943718994941210507613187078414353014943624129796784019265799066901, 3197813648651487960329472715941179855565509072639452513671719688580244831930974329428115539422438964490251820023678687717035641992272079427165945221350005, 7231054910067479633373143319867249279430116505455961793025591058986729168052165766434401823995355970999606424732262095832389658244117929362808979373738216, 4978243629152770473382844468604893278805387722504079889776130036372265418268561689241590701837534896781402776834722142809217053469966013757310838626083750, 5300307833885546681490351449486386000894930860773822997675242123919438541892329933981306903438207612376047837997100384800526654992772709510725011812057559, 11466955840428846565304150197813672836733555570828060806596925133833218176015910570342413497963180476403044280587630912964450059411624385210944745586941907, 9061755571226558295351278485049116581908094064020916207286103978445448392338674083803959444525528275513823234088834415756845811529459284003252150131902981, 8719080998829646402062436573575809187055920921593314180039229253101391104070817054991511901028261010423320107858567779823706525853230389147247564331504915, 7720892200741359130044034003302957125505653947106397779664829801700971174005697123991055550812826331996115787358674502635052784926812365779679508625556266, 7915052175381866384530821069933787215827127824060836877911376777047878634948208443664452901862062133772933407074155703503438176558385743663821572571037604, 755634569959333924093841803622895264613123386576966730375849122244188959663948757264194278496032354558274304442029716400497306095019600314869119143243319, 535108291021169569814740364537398651065861932904856683851061771709974272586544884745907128969158493339119710631742039326217414794913533272175013330642204, 1766381526083881448833436690034232476055921169539382440992304893596986800152971674485141718289418915308167414187663528939782974396715605198100318850539309, 5635640370201649225522749647243849026783405906483844284337240228345284070751847779286872583881056200132899665924874829126679621113547054734362647989898584, 11057182685082717424932200446445748924597392986393612329992981247017820253899815834586015444384965953591242359119347451140009293305552658858075463915278130, 1264373134626632146874450047944443263147359105352492062902753800543078571690431046062879495883229223446624219951228650363921476650287364690499584146187412, 749136822011162867888622469155701972612548957704067512778701662364231754979411724824800351762707289924484572422797871561770558438067531575649678363162401, 8909717278588719318263999623868676658829245501761410768369305274737658809636055616707048571509960811825404275018852851733791519096128649030253921775571462, 9596124046550836528479878128521167749854610782585365118677557972538376491186974800918329994894681223672076459082885973627852142868835397501455182442815273, 12281647114653400638534805437891995883581529367586126597326607512167230696500005347958804630257553964616258079773666917107592733309964668356341918179516278, 8434547483201174131426760876848581862373538298618595419054621271354615333055124701777101863641451464154711351549863117064714842259645892638962764947059894, 10691135073863129721674230326400155655270686937268245233123488103073869673694836361816363534428681779774589575937935622176377646220919495359459616722573131, 11844318885901464503034544162903252481931543240663098832728122624092487972599753742263068938573484124993981214237698509362015136766207640869374314385599641, 7366126348575804593323056202600377962869688117637744141766432178788185520966778877921782941570381962284461385740541893969981376394903113861260357438340382, 9343508117662751738682381258298708079220406270822089925570493991705500214704117888520237736027132648864395877843509978822203818714491370610785708946921400, 12555488923199627514251535231610211230340946233613814029184121769874722026950700434739008263327396518645591158612372986485537927914533066733462959085352648, 12771222599466540421580597120329660870787531739607598303019653192707724563606273165993444821859005764157333070661169484849375645666715340191937156990993923, 12775570202218473097918564003823165219309204758213398350249790840567261469754893085006785087447747589338865285985863258622586431357379709435578978580452972, 3501676119162628898854184768919660749958042928432829177611269494127254626237067534801588388068156126023966614455535773349418824328743684411736412947522681, 766038278089703614031254693860200873254965870798485792034537345970919679114420382341094908294419964810459978530921588366578555303686838586676548978686697, 9200084440097422713723184564361986670863411438657899459340888129628203906829101212206551993428497298560967332292748868529869324555912767164023440011630373, 7248182189841635853620903676356359915722897209283995213439155185759732189544077765882878672402895857959330346391177685716258027311191196839026968632640668, 3903048008077706888124191090711212686483223429283746743427911041084491027178325671414721725674922399907222814734194155393592463318522559077209009284851644, 7373433630931534092923416825542036970103428397074726902430414890253855760415720868434762844199370567704613460781115621985635673154108507969966995725724714, 1883539906397365530951650753167451506361230130157774117171758869832809846259952548187367016942044743135973551977078491125425464902015356293844099942795331, 1591146157812571061496741425827349808101648089816516934448249870584070994990294560075963104503706735505284925767844561134938970384064706077453285545669642, 5833737694896529223187135905387932689723569376075335694830045643796739473484403952448697013017618842734068330713201206113421653582613190597954533769481250, 9255227304965602224871153955184445831268369556247146728090621898323558066418780862139529462797078461657326302707890746545282378510054373198801150924837675, 9479659478311610461969163129871745886983416850189305726169783465159399608031619710661206286394710495335709517576133141117477344833288730158098797456336442, 8224931642951901129198912912047441675620097002807597527506214528769051441515893039390842526346814449938478020626044057350688622685235036616468301917322773, 6399682018184257957484710547204492454542078844570333019861447029837441013996818183962228162888625231928204964202827352596531807935101236353914475583420833, 1351974653450642841342285764793273223441911970117416210711745946423383165687366169188396153894450519083193809413117803248637701328417299533170726712332138, 1841105859487614037903255724860536845130659616470093330499708378064172521281044007463293902075402422383183830404723773691831388470688204340763262398016832, 7256325370576810999026868672021209054632921240446621405507883893651277341042596356969793116096619669466016081327623019994021483157757760666916537465301263, 815144825737559923180454719884799053740799492165185315652121169168549408702217948455081151410899689926782304733455726228765316295708031180183819927469860, 8751554280434906507269806311350393240473328380420526754369497837731786038409898602276466332084676279752990217407220718053400159459043544626169666739050022, 1563351247033728841540597366994862122406214703476058022365240408091635544158536953686029146673062821734060585330883223458432388894100988848911229289322515, 344462356225971400301185891924930593456315290728085633565908125574306221431175461013739795015567599336891360978925066979689121614460042567064665501063628, 12702417453530026913944532364924752533087503609255592026933775291524696441200137684435689047816444642359372774221103526915906569981283456814483341638090743, 3618436267357939683538240054991261765432454580358442432673111476708000385639374189539627539219970887160571025469011058963474647023192088438272544085525773, 1066839698204068187673538378436985513431986506368005080913396378304620321512851499729596912292996593830409019420392380524236155773411748014455247212903428, 5859615027702864071038532753109921269197215622425911271604375113634496543513243816645072544158258368748760493994542885316124889790978540269927004128878084, 6287468106392309536685747826879832756519707583757335878941306390680174524446229098577427865811878324175704266863409738910403973852844029856749119376759732, 38130665230712507276461557161203479283719604673285045321287312913846420936394197602380069474280033764398402859638826112335282264216165762225674270032649, 10063065212802037026084044824929690559023552852541979388267843577583273739348910362045712204462792192742940472189916364641750990258548240973389384287156021, 6248549144938361961584891675241401658253162499801439076638787741101786389182080502619999617728562743241419943119805784236382046791493166361233885337385492, 12108972682362633270229750264105872913575237844803898526477210970565750854054121147487779033647990335550350749322193065127263093416202254126093974654410868, 9964294524708111217991617817117385088252814427763447100721174869995595591912871939856914008365957569737245565815741026375862124250448442651106654123889465, 4724638736558393687095826717015376436576145117671267549534515450284022761533131789940577338074215313024499419581834070334848667891756798686384649867087994, 7600480798888666522932203781559018373853766066983407322179213042989458488826392567188063539851863598204590948475231109027199904555581154776058789463615883, 11558962545760746885655692060553524500485355906172485376669019979322604403467948095682806082625539481339435871765068450918146642706759133425326050541240051, 4709414886535978303750582320996305635981894371770251205027695775427567700239089275648587770247927059849898905550127345356902391974448897830436021619721190, 6605317739014878061307087896834374501381591903882834375677663388860378533141397971430993200820272364993415973911371465242435197214953779070079004440262331, 6209729334521462898952652308171090737380269438955461947807054292528323729558983117791698015474407055724080065914839352142902375148369686617420369178212920, 11408733482245968081278315012459587523645396111970672993792497650994086463665331984398670312720761490094549219858187596865970296873184823765929380510643606, 11647119702826563791549279812847967494430363050225420601835618420633995731037411136240207289466717017787913882181459629344000071242994496836151658621405301, 5922373638860432110002438847173829720552185036337489229549383658697409117366056893217242026918045931723797133466423096592868624854344254620440310968168063, 3802167856555006093558037813999990342932315720646729735177268393569753936185214579901559241110814919789902151436837233525880952039563821800635992721684001, 3248469824667831894670736986623647595924295716266783125323491858193903076842757683982364013608889945237654388448656055031096296999759327691680034086392778, 8825947537490389730745851018786949171684224312638907329218630238019708067789070542368658857871286786796140594540420632539717139841580465243532484066122546, 9409808666168694109794246232351874546087819694542801906848406474132490021051500638906336597810824481460082046172602225296775933583378057416192687486279192, 4676014109756910230931200570181911980739076680345646411036510122422090390627745658176310446237686218151334169701047077890654774288944726723924497224509568, 9906506354370523622721529585342371397515211204786858897196216830057957352139017300336985461417462990087787216613040726795128056746895844799755971310766428, 11440452438237110749260289745630670477609274731652836081261768940211633202979477268543296398128638217623601597068747171639688236481006913371536439778956923, 3814556489816594267515324409950046180578128199352423150306419781964010862813866149152833585887952967923176744834709102974782891975417902156340025615819647, 2256480884742789358770625291014099136931025314779686413063440800394925935123475639298602437673915269875831585126583622491704188532348696865644718037525265, 1651354113586995153282593319137537528579388200006658366141037113657438857692007680678432325147972360577889922376242414374713146825495119766839292762078737, 3916090946595823065955876447110360289727454385878060152633678563641057101239169379914489077446424859774145287605532678368601528171021418229828645277942626, 12328780955382165489710935578504399928056584372489710115156894713282833373878682950959625233578991619039501124425796940892290938404770385072646436067575791, 3223049973715265720173360988429173101385315490778831661959873311346621424817503922587849494795006762179826919333295419241136010241544018106238615053728767, 9225103493878015715157297704188911422524055329319806140970396067229984506656632628228237350460579512787705536449890638071147729646638766931775503807879015, 9688214446894388783550594969682368513396832059443734303127669895914265756878380201983382029906489594041996179825759843195653845523042109379971552483613451, 10242409657655725016938749471985129188798309366174034133088838264252394910960903081247491135652597401318677370972231809898653372320820877601506317993559084, 10797427851614636843354625531373753291178683700996331929194508409641968476125490657285216348346385715226315206095509651971209703879677398835495178738031385, 7714631854999959075338967716001402420804782846645127981592837506501881740203723621041255504566172765423065107561738999774593829867608117668292793451353456, 1743126260149072582833144487834698045973779238345784233219237610727985300063122899726231794558871462273383901255705445639333294039633505494358286536575399, 11243907424673156453647259930254368749023872158650150484172563434441591664533414591305923231237035785651965643110532552676349852154206748544453563179158831, 3271748383217145518130198868964759647847728192449466253286329788777813294009061705577739513901565329407745802070081536217642193919893813003509203736465311, 8026451001990980546112091586562907871311536356340904911440440712966695847957223371705911665515213144858664832022208131347832214267662175191675914657202356, 3608027215923197578907928768062984760577286035574794457517467453577252472369144589227196270467928495183983127644452952476393166909987035099294846428620801, 11860501333814268441615806825937052368600169396278084933311480456834591036083658344223638024752843693493544569272963764785891243787198175976243275153050369, 3335941850599619569837923795317342591528957852324979432994859599097609321327044493651642692564108535494780666316987714282699398769445520520522730390630429, 10431868141984038978347203712500680899909020263313070991906643779638289689006837299777141075755714842915754445893673094134148488119143987817729965013907294, 7081673812694653176473776583448370825992006052882065235658005809799308755458863983776292147982873662508313145497620453489599321821675430838917777711801622, 7748071578121955436373126355319918520812094430005959371473612368582012316544556989819531176085441600290796193166747936764639808234781043859534141206058760, 10091965837966592932221774801962554583562280469692671128041234379616901154814840340446267519804949154758652567800391289635334156850407038902908397642424620, 12784927868701678293749075013231084890110951016301573261642813677281262633342451601877281338541552191194980450849853238044665646216541681853795904108436904, 11178214598296697533316956992511786598122893507170240588925040019350762341528248029514632421687971718572113109939844591544883674273136273800269386031235592, 3151733094485730242587807663990459188153109306177850236140113741267358323246158023377321785122432044221084239432773111199049210358888371075209016605710148, 3003180616240522014141553285624773927927704592351091690326153474559356381576612411979519723845431289800573304886862641003044713466824714952816187269249026, 1480705251709151024053703749331025975954731936026667335412247730009177914304679915984496247565415355872433503848566429230630988704628900261108355428180430, 12823300914163707770115461569173792063494665839760191790471358935659034553305705225449244796990061621037345161654433800875870375765524403758565030037577505, 4428617137151658034861401245510846698490948122866286171357223359001316300363606963927788892279348055978015592295600425521007040484789593759235491506802597, 12335323137239667867470475944672597800006265117584279174601678395309257070454636853852713376580706743981025857792051297774171267081378852380973084828448812, 11367654961604056770827500500647389034322587242161952999185817095696146203937100916121937331303687932775532321601385493185606675788042028025748408051778199, 1013979456326778615598967813086331686510375325153655804489735580607935627928401920246521700223094667114051979340948902727533707480639670827855662449742762, 1347329878372260330920581792669603564749112686537953321077248776762159683624410059761501866911790993387945306972727303058364710226169869236985554417858306, 7166286985307736979543960047433314374469819443218915380229380748884820146423158541381038709816073958019495530018721822572921744985998035465935183718007038, 12261256133405302353183279821288508975135834346207098191896352700900387667446542154388710111413251425455887591433221212936040310368637860769597919566142154, 13054673659218401714607963178393373280764899628546475967280766143360296801160844802909724859436471974152928109053543137779151492023555719268550568963013281, 10901060093920598480734096716086420170717622171891723260344319116415848902764020110643502877294685153988473064315420324165102978321132087049342597954966945, 6518336008458323547244831785323287068823050667986877028748791481126356932035893760308149640995648243814315731885811662148356292287078157464847513826508791, 4757096003420065470642721347475878730436306294107622114183024208290007100819091785341133925389908503657929357347156620458601026575621435847403910265285054, 12701037702026828375400723094011412235935884143696972018653988800473371612984844697179828947682060917792307056399817317319365095721580496174781673717410499, 2684402791235748472264599316218040650050909623961233522929343015620135404523627865325368116737763338637838936400428372883306939615738594375368586208599596, 7253446499740129804699893394423872016428209671903262574508104569852517138087938646377480995788139689095580968429119530783898952990889038505766516735550583, 4670871576625792434899552573275846829895127921980420551229702793203037066753947522481995886336748620421361638147384483244578808122263322200718884815100319, 6436035391228709080518591666147764211965745848768770207148275961552328184567379589002879255103721560556194687988617620759772328150707116009484114091372954, 2603588787573486244437759847482559498841610100486297262218450640654260695856132979395019434175687609251100668655466305389741023001081397827923018079724214, 3258981384523127664682311321325081754424071356758906952878309762386966904508184386016181667597181524532363286627273117954676529927228939386725032769541021, 10716465857596990649762353058777439637291190201423912428111521202920832414740063221947381689538277035579853286587584447912554562478369918286699852410587472, 706036141969225813690002173177488249327119728244582594288246084016231255377125124427159016407558452732706927520837164694058469719775688833609314253164648, 4632220814443961259007023103409840274448477019709664984868194061885042645699994670385523191442866959395771056094601224655729828023866267968901372045420996, 9210613590041586640242607105559247344630999059331724943809374217671168919468657886893107069586919403100261633838737798672707935342282197951745801509347863, 3662797899794067224802856999303913974388134439885789350697884106709544572000601627835502998704502665181313707738487225218831654572388527775988884850721360, 6183826785466043146752429402089688207377451472955884716506783166188253811628678136532391448477543739099135819301086253589699908460208865087379412494629600, 980781474887652517517025442652420256483598634340413165357556681008233423419601244249624076285338811454954947363842456575606229473325061324279097321408307, 2573139911729082331900298612126481051892221381399260350399886904684837611249417324021123489278839358015383824483600256949610083181879793137106009700651040, 8816594787348469669350743759004822295584538075179841263946036291349126266558641732498204245258373374592530419827861145128675675558039838419904439436191759, 2255722915698324931589347886655850522377119877023109381704847456712914444904963505055603313790358173463286352775484761403640414653150074888475702251326193, 6971252301125376663500249842469308823039704872132781163252015743341752268088056835721652260184886006290898242543388762575185688710722839174745419795595886, 8424630475404969383165801261097054893139943873262447112492076781007086420578253204110771358840334270547305518093900775202230833617655265057732150061911513, 9502208274864432677529647006039187274121165308217114796960464758081370198048549785781264055643681465929131334349357114437102967255220937712323675380629040, 4725873168489472904034373469445665624145512752173549371503604421346281364996048223619893210492630783647345888984344081778730655960908798114131085005136776, 5564048191720138003929841681980126016758233348436816970658196823179586855260083674928850884788054127685838820390991843041583983101902485691896219417303216, 2798235398933927860240236196302730062620541782668721577795210434403597408965579740094033647460976417160261245871584266788190468661819359109263534778522774, 9107246506257322243018154849348348213394252714604484244927588019410650715118490637467007092326122806317702029225490748183651096221333915879931696781002758, 11497072393263140108784317326677871872715063869058991481013107445997772658351794106690322806553653402659098205138964045987343273734664625336891736581105536, 6913728296310438658236732792850696114330053546010728743394388105625628221734815756521437921619380446267582955500761641241085289400298979065454605023892264, 6566323945321331901722912997406700499222157861802546195242502541673320376175541668323406241274437279647713277282392349996274648897840489539252613393352577, 8640014236168834882559004060382744345776624780804660507078137263698211068716143190617956307208165316791122905820355982037035037350914429053188762938560326, 797702164102629483594383782749800554780966244583848933734079019759727156689457844568752966661245658144167651647857236353134520676965494424011963472434670, 6912816594516049418178403303565003937236951604914600084119778100081161412246317787034097369058609634775523853643808939510974102656015713497203344960050796, 6594237154210741709415820096138880549550252900702811861601702191658604865163009893185472168712090164616728826775000700591186256790305089448884993127484823, 152817246316169689942071434662322253133434997897193671133900658283624318531160135354480108791273506582765967868110273201052582110709127407793766082571306, 4453371301514360520783600537213272941133312459408010198621770623949218255656206401939959437183972654951372752079104667342388818011085077587562999230726748, 6795316026770331320886397930720944872355999958856947495811654711483003283684659349953575134071767241077940440532506299319308357579706803204400194065297048, 355994790157826797756780733948798672012714733739058571802550421524871290950899606810468542048130025847229651509137487049422171650366125074348818596840444, 3881142585728858791628630933707884230004988041313814292650199114821161191840762235010748631895385134039215571123339386589982804424402710606787387894503364, 2271741492449074977822429196781082545310809395390452961440387406166456358618345653593110599945546663803982650140365216346478484742239889116941288728139626, 1806326140675816997760206702444449346626896317378731074854910827754000720716017112199510861920566262424587823109260932016056165412922890217025520151204851, 12838542135633797430387226421675551736848454672650594098456719834810273318244115370862431950046523210502757808173818273624210494072818066509812136739357707, 10807866039576748650647600782458509333612438170447084168611695145524077354586157290303516169833040791539815200502436971488937703753587221972458923234738412, 10063980714956002919841731404830913598743815710010184237031763836072283209050153048800109800594067144146274174539602821867960766292457097702789395550486943, 6523854451397001676431220943905069828546804288645569816743446949958190943938723847139749901400208440247803810269523284186623396632970498784367934202773512, 5512509042439090180148299628232519798135470791270970925078649882643539836857843368393893261967398686235545165275265342133322568370819863264016162431512588, 11624084472125165113661905434872200102788905585276895417416063507857724861286247742591377043187917510396232808820431909537495776172497110317959091446611086, 8173695360442126236530175168704703511941442684555318133905175400822145041072300441113888157536190998584296979376382797085826005332688597165375072673580015, 1842529941226910409752881539456410900984428454182866949815738248245189497780042017508404284183434854362986201607712375090213224947718351225295758151091274, 6026554792695187031291388105259521539001295856318498792950078389582767875052029495772393926700411318646445145081358965338365772376526447008540922864696850, 7430373254524805867469537405525215307389774051094243936874048729978721841271182019053370314930610675689598948691190039402418432780401951074108030500419361, 4845316339472324172059140507109238105783007009961100120208680215373952514257408538628603884557724945202894757966207266080801818315456369131960053156079557, 9881813377588651286122040816436763120270629469694028186369159602802877666328012209944991939060842826619327006626431776555873280975675986596109133546851440, 9343590526116328617974612825269796297869365893703529352491748935591206718580389017408752773131299695504635230325097058377718539855431427455921906838792120, 7475065046621154555597733255237973896161073850121136044361079656084847625249807753875209661238388404352623792389953181179893941510106616096169975751278241, 5490162838759129759362380152832704515720069802636420158710752462780701697387982840611249845822909341184319490197189785951012083523891519892288584429043746, 5798523790534085747927695553475367996569744408657600231432095603498907963483057823822256534745999204451695056389286640708350656637499137165441329574338854, 2644462035548108102696784810601068238025474024302424384296396812879376811336908560553787524663888614235667534448178687483584881745996948163558337788689457, 4293911088807339528458733478705521027856610163311188667149666847349072457577558230484446097611027450986676599917469167817603082389167173047831242134183645, 2357666151804843720669445404417195355413358383974795253656408308700995238126885816455135770267726543317806255078028867911777521824014955470256379085036660, 9197276769453081485191286858310760297867302809425222140367990535668561503570338592080521412519460223667400005291980030327136848971753105884811618232109771, 1779754871452237358745532769510782517255873316908199233450281852368141574999220514489018152339239615187612420620418950876546530671762376366678117580463905, 10946755498557972333407315907355277932510842265901362127874877809044980837022304546644451291238270397116320217572847012638966886916028338518065358546220062, 662926948532410536471897313671121550318205973279189411182394830628923136152127919978120920669005233363407021163714239917245382462715932248878778423287744, 9504294852920486164721500535134862257578737418232550334945274005195392593310548836761742362254120138227363586232929306391572138948403777436456290554186964, 11133597852134052563072042180257143271415004630682146452755967235105826974594403827724938036425122241721921860495030066529636341616093622864575825128367579, 4231439175195917460606286941004496860241570390278458564665612486528723426686711433864511624260794043150631045734119274163571709070143677382995380272782620, 8277375077373394578087964675331976064684726059268042119849805808231843909750084797612503724934173330845714702737061352449740100656198481602228910536995733, 7459404597711939944798225379177030599058260164252616842092419606867287497558507619048502608890520955318242019227889534894466053844667493411165595299005586, 5950718166680598797365765314346841634155736691748142434795096820851250180865746728060391367338907528270823837666577056609111276621006550441458459434202627, 2591768363519030716283706115481580804983107771185301105626625297133788237765081081406210282793766902345328347816333386821822046370439481821459959483506736, 1079355220131564883458310920667260334607551976958468464716798253691563434752350212903794818870325772814580808634805356408490255378163283038776530379545538, 8593403036019325846621363976033031701446218857725664334229596086994903483910876044007303109799543843958056248049432152434474743635519735554285002954500476, 2790097572461410409980875330329312444913505981126437205566036565020068862093795129371596545054569925327026357197047668076379520197979294716858356516274346, 5875217705179119189886733396157369817475213310366573567386926236868806143202796071682269656773606112283876320959733459869655746265017451840603860366652718, 5851565869679667606716818114534004451009370658240987920514705882053920941583778088482362143851141023616108453025525620092695606071858249046906338785181913, 10663630057949342671349484128409366571910671549983309193847859632422632416960200655614016276025310258893523070187019033283387653386171233054582451339506123, 11587666913145558499626869374532950531400275539617529993064574740077552532564494518383292289060054272069434162383913160988831749183920225527539285651581127, 5241645805846584238864923609180354944205016231696812489189135384842163666367770311292073752560138754997964182936950858083867526087582684213906609726396736, 10695307738813297367439523210554782067563450511443752003224743556543293815569900435880161170074379256442021241807313705632713406700602638640459712542666780, 2890190125254382327279039875904297542714852322179965846119608158820800571759021599405500546544154692732748502612768707430696383485641483760686838847832547, 7739548952607385383191969751573528129018575229532293116036712655571860461226489675276942118181626428311276997702957307632764891378486696022008078627834540, 3379032222575681112977946603924691626502435348577727801953529597148314189828631552532708464810167010722934266991830581861683451139598322617644735814042405, 11440678062329741021051810359817969911967248758029633267318057122489338807897997961562133122554863688506936294115348797754762847023330742967540048128725564, 5027181850105194130653036653372871523984138202432606399970547980403501083976857309333059746895846986964994595439025920598959513997750076614679288616480216, 2521479198451269485472481139094944586593126855496703003912900032568880488631698482781396525134661424391181989747826034374465218483347497654919037874246039, 5221978502132723342105009403104960583685599732026008335092907265339722285057333110918371443016140936968861009025747022863716118557133180398181550786688865, 11443964043566948815710535890284018468069073405965103369952170662939719812503726054036716817845800110634242480264621783329278914539899698459489032379477111, 12089018348861633465916384614948994050371956573396810551802482356736604130849378812575251147787026508596002611327060548870376565819823980986929949360517549, 6102613899086675653913988856136604276620203431502615830674777388110263343557087395376343363215158329408228665820807489614840389653228965903016952588820688, 12321342713337020658608315892523447458131242896860046036285966567113879532052010839254314711222434388334646013151710478865716166198749359720715198063831735, 3060224925610794337743052493776902410696551602244048739860111146629021800548850016963469499418546886901986842107912324409435634672674102298454947170036617, 11099962545742903536292654434441411026356972095035695278386771689280855661749835546025279868212852576578166496494624044276939629694142763312252436159510869, 10145592913667961811777843100829126888671533809498356318259564327845202904486100542794225160333627825328890322065533612979783695481239707810128134133651539, 9737637471188281332113475553951394368170901465871542953270042422496410322572192704487173805179667189432167480901391552051541704258128525348892435389523768, 11393215864152439958230707013423505663236805382243511739666728677556433316183262642701278850207925371799766312972172013102309308083468556340335517076754523, 12743479809506330566758292043962009402123679667345676071432704307657275914692787966398053725408261438097472277448717005867950133514684221373540255982531851, 7086693778798698567329080388054699139696098224072006079619474727279869768296068403724702208036186630663485020440334732776320817143258269449334033282791370, 10574534594314104421577763613445988428010174371401302676871277813427012620250292979423067726255867941858964048695659524431293218097457061269736802910730920, 2780359913473458399348641250384785321295559858145895888870371007298564237569130790231341230087757089221483211819775076651985997155170661252008338056944522, 7539274340541890375476348127651321410414027021731268453952602279773950364161207017261099512905828806256747565814360811700414183315622921194082810528446113, 1770620311643022810508245358263835664253735753601258901497999219671478118733607838390560473492940067778627349267591224152983952859985887004152723233583743, 4737802951910677301190924445873641903604964984409222494616033093860969049642762821582629898026401558902824570817521753604840578046817050930168141151138363, 3865647278758923065052658601210619065840391115081454228420328441886594402939912233942325339492570066695343893464840582859779047695340196157017985441033195, 13035910541057905951991155830075220558370838679692332169830744819610956310527967128093195573373360636115878113559496062748588086715265455979004976189563603, 1178761864576707499078431966830946212114375338365547959132445879380636116105360986235969719599221548087436611743731272866159062109157096188490502320635420, 4844884144707842237969713268693282807791996113982366513161474972320301672019863414778978546453514452912482514561685242429124913023175064086036983456431305, 7727425407272387682404464943386826249000884037030459000398141028782945251900971274141858509827962146585196145428397490555872902994502701998472362055375803, 2414534541899840210032319100316628104346897239770649369265880316361456678760641476921810055675050735107308384448181744788206461595656829406608702204401735, 8839013530179061789121385581470494505094896879246856107030381699524257509251796868368051070453643025146157230699538293100243172914096515387555682422488205, 373090179973192110571840625724512639570878107885051007527179781411339133108435431504852098343746551790479157684439542606720559281124112737838854887057573, 1280682069449887148748854516587453990262931313273871806543972234691294666111188318562951428474290441371378363275572422438045043786812818896849466329335052, 260371395285369490703913478013891852548673714290940301230354230672207001636590828718387296673384420986484755126782444152260044050363793338170538768194563, 9873806698548981160876612806118260022915487971207378820524309252374448879220925384786921395442373816159644470794679920757492661660639622212731445402164532, 2852931093817473370502049554884607845620807249825797304491600794922674366327600617923668366810271267481345768894646385644511632287614826774393887210802513, 9538898830413390802288794736418189181635017043350809429955696040150523897606460310175823154080522341313270483425498106850289065322744983400860790663080827, 8065159848340405542937392634705468874986893129500962380794487021597739098435149584782185438851339070015806723150519717570044699626719203371586797387660209, 1434999545114412329339548986639047732812467996546532886685405224489430510460795626880450042957732891689251482042580608009471609940707063670544868654145472, 9196011144297628307224774316199155216562124865707887249801057444263961875325704421666329504944788651167636358956013705002249249148510080098550113202642897, 5313270887301959253832141299021266157436607251314784584771149030455296515014505022291198311037842691318837910656459401372032727406265890828341578800174937, 9628467396809772500009592441025444261151654685086736350614835947273326957331712339165887583258336660452913653599774965359092551068407133221966319091771052, 27603144835466646745076532086514752396932840389244204996901248858280850210149866152976768797030430364681712932016848639111189882169138724540884850605042, 10994030282549215351961076298662565568078051216681620523854201780894423028484982546055332769935735987629070411593903154114766289028507904549134435456678164, 11849765942558414159377131926339151414584951007384890181243652647913018144070122773822442731331782785453926886326830544133717510845507446858652801395251187, 4975444926806554283619602851485410022086375848224539337689270704483636897897460989845038741426651784631115456170682859780000066334556143365130931601434195, 2964671647627695781330725692713241622107673563697138293433929136660261380816938324249871950179277116012105119385256962547427836349115026343141424261271099, 5278320594671279386718082211851500769405728637405020426603365034914975307864414794403645779306636020067457859724746829077569402060534993266901524332256643, 2147899490673561212449348962294078501047899867348454146215057779896917416058174526892386565149190450273794915095672044544416793835767478355231003962693720, 1252212167569973250747353454945063763753788723601585984139493455415559112840685213278744957243974835965458920661980677455994696628080771913736843591548293, 4773104435388076697906908329009107230064317123502127219391165313146495510375015984109499594799940510023642698610160020990335743294140912542113107305728333, 5821452964301708081807015703698740875041453079622210375425594371416470013397869693059390433335318622393634461564608754028357443304091134664602559040387845, 6943381519198890242048511884903497601900012456803171785670346229278857331177650559678521505420232023270606179613341230225150760716298637833269959005093230, 9822789459134823658404678357659803370832766106972864205202768208392754443007037764183778296604773644712158274104202528055563537282187229549132505851280017, 10488925859295844553179608131766870506723098301869330411042032453294669614131739103917228099623428590572114323730219905641869972102861375872598314524757502, 5137850662873458519860924569001899978006789869081248588518208990426713820306331800899827568187126955704990736052966832882815244823522224026386765430015145, 10118170517700911623838349062988493418105867993522847161874398426931443235267806329466953215796052316822265800007127683787298664845520803466169506906846764, 12021133672335397989968423762696259751054294579981663361017673393394908485345064231170898008945093822981549831978757080011946439139609662192786339258343536, 12523340377586347076117992809149456308346212654734774666434266655959471911706588906265978775395226424600759416587421497302103782097726660559341996981268406, 7868038479193501471103955874820736374431452378144005986168950903905523760180844210734390813216502421172093902928983112327374920060024596409525715596378420, 9071093647289069667509101411114902681486720466821470428908630112587844290277173552496395146772699213676026293903746403651929051176138844669024904590510257, 105786813918182001355350892229074891892369118408629681323533982461200404229857705015514295114476861039247664082796496268069403573349755039420210216463168, 3508741859198568733759259222143531475245320572141246348019000478222587780980824446833324048990463172814704894680380917578158731408394654942692410849834199, 3156027690474689826533526289344180626346735295427430220453057941955291329960652456891420316916808777374552434330018968624181054296840813696851145942245761, 7620776147378467841816680482193119847485005569177936444661202633892595394195718743158669108922497458017794013303750053488354410717527957472410272261297147, 6374357393973660460216724859695748163756378629509222067462574982592585124852746830596457084832093167497877241593752079462397017168810678526198852646336419, 8345066821557001321387299539614005885182668424482069787366667790419282853164081687377158602567265954355018722193612238317215778043584648764490972564616539, 232273247616918118300391619047640773935034151633954105720241704680657035272075681998590410293524518421720309989223583865132866647294207028673718851141308, 8275423292153331227191851564384810919707865916972369128727875994307119910319174441869911243881915412707231396140031682576456184810744861481727870279935653]
p = 13098344657133513491542748313032371872132222648288093501198265832003698640456051502514950141389223416736613006649988183928415853889952240807027731932522251
m = len(w)
n = 60


def allpmones(v):
return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)


# We generate the lattice of vectors orthogonal to b modulo x0
def orthoLattice(b, x0):
m = b.length()
M = Matrix(ZZ, m, m)

for i in range(1, m):
M[i, i] = 1
M[1:m, 0] = -b[1:m] * inverse_mod(b[0], x0)
M[0, 0] = x0

for i in range(1, m):
M[i, 0] = mod(M[i, 0], x0)

return M


def allones(v):
if len([vj for vj in v if vj in [0, 1]]) == len(v):
return v
if len([vj for vj in v if vj in [0, -1]]) == len(v):
return -v
return None


def recoverBinary(M5):
lv = [allones(vi) for vi in M5 if allones(vi)]
n = M5.nrows()
for v in lv:
for i in range(n):
nv = allones(M5[i] - v)
if nv and nv not in lv:
lv.append(nv)
nv = allones(M5[i] + v)
if nv and nv not in lv:
lv.append(nv)
return Matrix(lv)


def kernelLLL(M):
n = M.nrows()
m = M.ncols()
if m < 2 * n:
return M.right_kernel().matrix()
K = 2 ^ (m // 2) * M.height()

MB = Matrix(ZZ, m + n, m)
MB[:n] = K * M
MB[n:] = identity_matrix(m)

MB2 = MB.T.LLL().T

assert MB2[:n, : m - n] == 0
Ke = MB2[n:, : m - n].T

return Ke


def attack(m, n, p, h):
# This is the Nguyen-Stern attack, based on BKZ in the second step
print("n =", n, "m =", m)

iota = 0.033
nx0 = int(2 * iota * n ^ 2 + n * log(n, 2))
print("nx0 =", nx0)

x0 = p
b = vector(h)

# only information we get
M = orthoLattice(b, x0)

t = cputime()
M2 = M.LLL()
print("LLL step1: %.1f" % cputime(t))

# assert sum([vi == 0 and 1 or 0 for vi in M2 * X]) == m - n
MOrtho = M2[: m - n]

print(" log(Height, 2) = ", int(log(MOrtho.height(), 2)))

t2 = cputime()
ke = kernelLLL(MOrtho)

print(" Kernel: %.1f" % cputime(t2))
print(" Total step1: %.1f" % cputime(t))

if n > 160:
return

beta = 2
tbk = cputime()
while beta < n:
if beta == 2:
M5 = ke.LLL()
else:
M5 = M5.BKZ(block_size=beta)

# we break when we only get vectors with {-1,0,1} components
if len([True for v in M5 if allpmones(v)]) == n:
break

if beta == 2:
beta = 10
else:
beta += 10

print("BKZ beta=%d: %.1f" % (beta, cputime(tbk)))
t2 = cputime()
MB = recoverBinary(M5)
print(" Recovery: %.1f" % cputime(t2))
print(" Number of recovered vector = ", MB.nrows())
print(" Number of recovered vector.T = ", MB.ncols())
for r in MB:
t = ''
for j in r[:167]:
t += str(j)
try:
print(long_to_bytes(int(t, 2)).decode())
except:
pass


if __name__ == "__main__":
attack(m, n, p, w)

# n = 60 m = 330
# nx0 = 592
# LLL step1: 54.0
# log(Height, 2) = 2
# Kernel: 3.4
# Total step1: 57.4
# BKZ beta=2: 7.0
# Recovery: 2.8
# Number of recovered vector = 60
# Number of recovered vector.T = 330
# flag{634b9828-aa75-11

第二部分,类似RSA求逆元,这里的$\varphi$相当于矩阵的乘法阶(某些线性变换qs是可逆的,没想到矩阵的幂运算也可以是可逆的),用sage的multiplicative_order函数可以求——这个函数其实类似于求欧拉函数吧

image-20220427132040682

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *

d = inverse(e, MM.multiplicative_order())
m = MM ^ d
for i in x[:60]:
t = ''
for j in i[:167]:
t += str(j)
try:
print(long_to_bytes(int(t, 2)).decode())
except:
pass
# ec-ad2c-00155d24943f}

sage太强大

crypto-EZRSA

题目如下,提示不是ECC是RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import os
from Crypto.Util.number import *
from secret import flag

p = getPrime(1024)
q = getPrime(512)
e = 0x10001
n = p * q
E = EllipticCurve(Zmod(n), [p+q, p^2+(q-1)//2])

def gen_point():
while 1:
pad_m = flag + os.urandom(20)
m = bytes_to_long(pad_m)
x = Integer(m)
Ep = E.change_ring(GF(p))
Eq = E.change_ring(GF(q))
try:
y = crt([Integer(Ep.lift_x(x)[1]), Integer(Eq.lift_x(x)[1])], [p, q])
return (x, y)
except:
pass

m_point = E(gen_point())
cipher_point = e * m_point
print(f'cipher_point = {cipher_point.xy()}')
print(f'n = {n}')

代码主要做的事情:用1024 bits的p和512 bits的$q$创造RSA私钥,然后在构造有限域为$GF(n)$下的椭圆曲线$E$,$a=p+q$,$b=p^2+\lfloor(q-1)/2\rfloor$,创造了一个坐标,横坐标$x$即为flag,纵坐标$y$是模$p$和模$q$的同余方程的解,最后将这个椭圆曲线上的坐标乘以$e=65537$,得到加密后的椭圆曲线坐标

感觉对于下面这个不好下手
$$
(x,\ y)\times e=(x’, y’)\notag
$$
所以应该利用$p$和$q$之间巨大的差值吧

1
2
p = getPrime(1024)
q = getPrime(512)

但是没找到相关的攻击


吐了,菜的一批(一直梦想直接分解$n$

这里$p$和$q$之间的位数不平衡,或者称之为bias,虽然不能单独使用分解$n$,但是如果能找到关于$n,p,q$之间的方程,就可以利用$q$是该方程模$n$下的小根求解,从而分解$n$

将已知的点带入椭圆曲线,可以想到两边模个$p$,得
$$
(y’)^2\equiv (x’)^3+qx’+\frac{q-1}{2}\ (mod\ p)\notag
$$
然后用CopperSmith求个小根就出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *

cipher_point = (338555080220637081961629108201515088631648910827927160728143665306856840891283037339677849661861227903908933145477264046446986150577658634798201036502060805774599658207669111688439996110692201008037849119605962378316457201998475046620515963725786423440494993922281942396227626532022005579340476627086260000576524772862121364339849726687865874619472513654142054490221489754144358483093331358263771080584662872680106076787261957704707055652825959314984924849600101, 936859805496385391559236776246883920797971062581544240268575675825570737296851006237870839271568976317212531276234406232945021531066674291887782791534409966305833225084692612867437424551505174720475931132798839349207246806850341280754752239303350596733681932273450149927797735966407187594725231158980098119489003450563623494155562513634618466910170109518754662675054081897025489520391417883488720972781393802142478712026232107041683271177224983497203599032383279)
n = 988000511804778695813521569460767024014375863209856154754147082419975777208656083311740358048468580712106204105426217752071608551112269505247365548210006567296850568411531004204795967810292432041395592133501302461324005142940183488044983348152371980166614840414803124031222965874472013554869981954785271467321919039144942853506143787908194930700818770224752026306092706366253640515130802157497666497193713819097381223915943111321812676982912146706199692543488639
e = 0x10001

PR.<q> = PolynomialRing(Zmod(n))
x, y = cipher_point[0], cipher_point[1]
f = y ^ 2 - x ^ 3 - x * q - (q - 1) / 2
f = f.monic()
root = f.small_roots(X=2^512, beta=0.667)[0]
q = int(root)
p = n // q
assert n == p * q

E = EllipticCurve(Zmod(n), [p+q, p^2+(q-1)//2])
Eq = E.change_ring(GF(q))
cipher_point = Eq(cipher_point)
d = inverse(e, Eq.order())
m_point = cipher_point * d

m = int(m_point[0])
print(long_to_bytes(m)[:-20])
# b'flag{0f02b65a-ab26-11ec-829c-00155d24943f}'

BTW,small_roots的参数参考下sage官方文档吧,要手动调

这里$\beta=0.667$即p.nbits()/n.nbits(),$\delta$默认$0.99$,$\epsilon$默认$\beta/8$,求得的$X$最接近$q$

image-20220427112451624

image-20220427105614545

然后这里说$E$和$Ep$的阶都不好求,$Eq$比较小可以求,flag加pad也没达到512 bits,所以就可以在$Eq$上求逆元,恢复$x$

Reference

  1. pwnhub官方wp
  2. Nu1L wp
  3. A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem