NEEPU Sec 2023 公开赛 Crypto wp
FunnyRsa
观察到N为4096bits，e=3很小，直接对密文开e次方
Loss
def myhex(x):
return "".join(hex(k)[2:] for k in x)很显然把0x0_这种0开头的16进制的0去掉了，浅浅爆破一下就行。
小技巧，插入最后一位0要在奇数位
解密脚本照着加密脚本来就行
exp
def dec(ct,key):
aes = Cipher(AES(key), modes.ECB())
enc = aes.decryptor()
pt = enc.update(ct)
pt += enc.finalize()
return pt
ct = '98691cbec88e449e8bac58e91142269a7da5efa9e7c62848e7135f1150f02a'
key = '8ee2b28564433679d93b82873fe8a'
key[0:]
for i in tqdm(range(30)):
new_k=key[:i]+'0'+key[i:]
for j in range(31):
new_k1=new_k[:j]+'0'+new_k[j:]
for k in range(16):
new_k2=new_k1[:2*k]+'0'+new_k1[2*k:]
for m in range(63):
new_c=ct[:m]+'0'+ct[m:]
for n in range(32):
new_c2=new_c[:2*n]+'0'+new_c[2*n:]
if b'Neepu' in dec(bytes.fromhex(new_c2),bytes.fromhex(new_k2)):
print(dec(bytes.fromhex(new_c2),bytes.fromhex(new_k2)))loud & loud2
改的D^3 noisy
运用crt，然后构造格同样的构造方法
先对每一行乘$P_i*inveser(P_i,p_i),其中P_i=P//p_i$
对一个矩阵，每行有一个$flag0$然后，对每行取一个flag0的那个值，然后进行求和模P即为flag0
这里P是256*20=5120bits，flag0是4096bits。子集和是一个小解。构造相应的格
对于loud2来说$p_i$的bits改小成了128bits，flag位数是4096。按照上面的经验值，去构造128*40=5120bits会小了一点，要选多一组，选41组即可就能找到了。
exp1
p=[66467878562792562224887473415011035371976498729276781135103070806273826602147, 87779827664444719705378632508432527366151596527264599732383282214161710342059, 106478845076259796180788022071614290976203859464583466743581048528447954519879, 96059795988661207615203630115134173796188205316583242342092930969746956840537, 76648433583138097341785050433545276046328401071616329410459071963649387342037, 75363807436621723536569872393312030066473340867618075065014040776064056013377, 84549506983821330145587582824091845683589581353932033068622843538281197238321, 111370876180722361599897961586244954018438484624454058266043059162224754345369, 64482965162169334114246637526347201196498007629645251181883638859700004974179, 115737745133463165088409210929201564518908251675851193212090312153202710950611, 65430568356698229457733164116539029669340192339524852345167889932007830803713, 83005759669335703543538842561745612525242745913149020160169673469294684269349, 86695300569990829413494539259312051326564517598709183416846805385774886176327, 87649503475806433108642579024197030978459906709386640769733298397489631575119, 67546279258240068058305769281370224151667980031696762855998467222703960646549, 109277222890519331704406685175081474974918071159722270158398833428598261621993, 94947541482876422720663520475916415155713415168744242709306335577278248129671, 72169704519430039945520319412623531417839608722431394881643470024106954771823, 67960163975784724339119270210646072354375119081204577840800359343098463410911, 99600976311231076437603674530239237427983536499904250636338541144596856152681]
c=[[36006797306819385066479875554093947690583427970449583820207929310836800884907, 42421831928852572111305575764455253114855197661030346257979092292334693704638, 12802758082612276306666301210467012086210333405770973816248015272325645518737, 35891119003347284519077367147618128608424314149438118637710340094202006973607], [69221811235046204007409195125183399115207721139473251108686359647136964539528, 68728546052531932227774742525240050245981893208569278338806756195046394386320, 77378932313251132635143406501260917558950175409375255430759788116685665756853, 52610629088183684552705334542273079173241031671071904128690224212767984326814], [84632180774187758644772651231005808936754972376616591239738706882585325508504, 22245885241129428291065279034982203110690225047634487933389806520943556010139, 65058154300579433325392929157176043693547112910255708084394089838078169979653, 26450521689799343844879689401496427283279097300795496218417820952255310453381], [31743210200723432871171527300926464156713378567872351797727553809801223755669, 13585899089974057026763852048073375117825112528263695778864069316682632842469, 61718974141826995988697061776372539645461814294568567001726256109104825647174, 51180314603392071189287058511013567287870020999513958065031674007822278281592], [54972437884087220348657249916515696089000557932808046438758622081654015388431, 60595394189514447466338506137494568375465810079275014516953880523799578017650, 48290106501584587524538351792623115913538457076946109833703750186838567097829, 75809640108047877199495621711957016420204838905577105767711805228492185803198], [2043782039074334576524460230918369530353673853539675192552828729137718721899, 49835004172676327317136633790276532689791891581739516605994211773520862094089, 74150446127124215081973853925119891529594162176613983713739514646864857274598, 3870903633214309884568064156029910145031131868082685800718700340446754642668], [58530922734504496400650172153260509666806593206632885245359170202099163777029, 24679955301703325026039585637067957593890919790442322117013190013849632870045, 47461847478301275711387089619360312020232490159064156700718722079533108310495, 78436661760605062831488783213279281637896003485976271847409520316669048162591], [3960169205004685923298734670827529710258905436583484891133449600679523626998, 56971763036590510871648632641525055519742294555040115044720432874482626152527, 7500941845513450196840656641552395008944195976110947855355515297144549893577, 104364444158131675753431216431697712763613996035708348677723420914206545999308], [21090310989423433113256120275297260716078136824734467530250689161392790805917, 59095240674034520085214866457855433129352762312493710903594522366480317145097, 25950268632849909273587896220763105221984980662119437334003683923010964181793, 22214910913289817220594820237750728594412035322558117144502181839908519483813], [6516207309607110723013310828779534786605721487724433166085213573594060054191, 62491095915002854769743893168840271080994195414466604510886959458801333994425, 43298696119722427147738220942971604096101207270771677319478440633957185506012, 95999300849358990419162309412086189707629278626118528491801630061635930409174], [21901937371736027133484836626793049950863305103635439434565692334061323247459, 22177707944556298482781825594816606678702151909926553218938857302296851101061, 37265517992688571580384548897674161792052985496826940853296718063969030761085, 45803015810935362104176472501216732994877801735307247883040947086374864784522], [22887302429552282917137975404437379689230279867683032429064655381687354309967, 63687512791087585071097169701758075850922324857489524802811455099431146712006, 43241233600118761031756067392063544631958472413548145463886944168747993611755, 78540416079875697330277927812643707908744419489483603613867805715379418188382], [83274701456245595041914535781657541250722792681868330743604458671030342631093, 29265221035131869074958665850197081103720257562467498607821734305785454256445, 19656036104607964818483236621454584533830854692521644548949580232419092579485, 36685991496747026794589417986750583003976651961717444764360736602328859939203], [7197271849934394038490337096465830651019854061628854994110403632096530818658, 13199583400545916173897024693988359528617080325104182927755868559199746329580, 76705903744610047925943025263768006533642196751938988456317343613219129386367, 8284847848213860404087592474405055922947517109038702885136704630947806019241], [40192513898904947184731216279798716826510915071804534174239538082671192078053, 756883344718645808681598066443462390307116757281839378450937721653214302485, 46319296839244788373603804279624137323125709215284595152627739510983625831713, 38066834404440733412548216101182968084184940639461830700714702917736840764910], [52459924240743004858678271074727889512634425322058383892565820049302166247484, 1124830903052334805081369416754962375712146318972731973481260141314675294280, 7048586820754100983732909765398789018269542052380424872274364753361851089050, 46261533803791211860667474793341333491934930635468558951890405299902112599717], [23712997405587065505471765580307890926020635436932008780552027395793174460196, 67696894015776789806885369424535665938702806354704500197616129889160343225036, 22335907790107175161378264382954791596027764567679319454957440806458200559861, 76817272441881586284817699756225532359147752598882508352406898668675942956599], [48442733699161048528383543478196401606393182356208996862954079146924798030016, 33988046942702399144226829264100378601075005547176282333019034404108127701223, 3878811651113775226499837109875057444157158981192358109242560352485567236840, 48096508435450140842190594378561970076075899550630622502080370324305787016204], [4661700708549906139665791533582485338344505441635713456342199101346895847315, 57085434497175712126874334119472545667616658739402471396702109228089918012639, 43291903057149273908186130451801222008858189682043034712173498638683726314620, 43681777323686685006867808938443372833327865869793588659920726812432020143637], [34817244237217626483621974571192315048341502556634007719371004295715069335162, 10855671893795758052388714204250213675262352053079039688785650172729770783108, 55808546957704772545340135312880985328286637622927964296444521648705445287337, 57996505385421171401445757882512186395065784033051493647151141293523405436642]]
M=Matrix(ZZ,4*20+1)
C=[]
for i in range(4*20):
M[i,i]=2^4096
P=prod(p)
for i,cc in zip(p,c):
pp=P//i
temp=pp*ZZ(inverse(pp,i))
for j in cc:
C.append((j*temp %P))
assert len(C)==80
for i in range(80):
M[i,-1]=C[i]
M[-1,-1]=P
res=M.LLL()
res[0][-1]exp2
p=[262936694987601797121049793464622308733, 309997905911961162457215781817387730187, 257395035318380854775057601132411116087, 286147452080807365850159264284388234501, 277035174837154893834828039596691306911, 258512383940723711320851376437133539413, 186397118585773856570258104696335616987, 171693714739008150001705405614864428419, 238083747816293372423865971187230631971, 282316336151097891530064716780251391569, 215573026476616636083793163922337903571, 191937949030515697609508501946001624387, 333988937469961080573735881132937677827, 317025722732636974432186317028511339951, 217409176045939550636396694560687179723, 323829248130937902037354871334410597417, 290633791886285159803332972049642598119, 202797841071162300959708472431342537677, 245149729812549223399881540394215646847, 200387371258900838770670766895594007321, 306716544669916315302394725519563755459, 293035842724416297725379959023474526183, 227895858258458537242672101545454808547, 254094212367427428776672086286708146103, 221115644183739620122217327743305184517, 200894275744219605378208892056303260911, 333768359928612829779161218754524204543, 310166138123201658463207419764801157157, 280680591491526214042535976051113275493, 238753128853273749600427481335776990367, 203745093932675528326203316256781056747, 189983369614045871849654048387351520431, 245829952383269622766910201601332944763, 196898298879221153082315719118853521083, 211198991549431484868266572931541530269, 282638608058816523125522685098951647877, 244685115564771577008377078268985934383, 308385162262044841446419875108714071817, 266735166831162725429883170422891377611, 190460697635426606812499529682186774603, 277218152093651123974142625801331664797, 170706285257706307597940221604237043761, 238890312826281078306694144662035275139, 301412284494387419659599620938428305119, 250927850622318266629025478867436952459, 173370399311838765647601577255503953449, 306181404528504973833565723694846822767, 279105927120745567305400051747872353993, 195454349162604902759751005896979132101, 265726415221830081959069547663426811381, 220172850548170353106674039215740282649, 194854476610060492523113909621496666939, 320414161714112220806657555814838727423, 233654927520125753180229330411360435829, 216995829515718503652346475777729176667, 227448597731217481116239722185517286477, 259054744178265624852944080306440622537, 209499938666554153595882032274239234279, 287815214123410617771124615210648914437, 289800833651511853031431331522719846513, 247619673933496423772602176733888580633, 300437674527684250893165465795138547727, 218736659430370254617337271901687871887, 245803735048461972135505197356496137327, 180195085240908914011593973291144008931, 243306929536527726651752413081941643457, 180705277438873998735224970785020807463, 193178910063899311007109066615951335969, 188651670316430826600215803069381087967, 318618791616475384860239354074811518339, 295082891982962787055952208517313850391, 241856718587425607850889310184614887811, 287386125229095085179646707017373487703, 308735051432424374696423445556308335507, 252087617782808538275728568789133624743, 185120262250543052018516735954461507513, 219725015473792622072845859629743727363, 249566610978671659133923311113408212591, 318142462058875563931341345315737660453, 291164155086823164549445882979044718173, 301548238900154150424518525694279259061, 172801793252009923136417352578033783567, 218700238217543856435267489861629280613, 247169203865768132068540820809720813919, 252358048710092778484929503097227933837, 224497598289972893577953087230245933391, 227290969581850512315561703823574307069, 247215356572539088750411166886265991447, 310711194489203350855635677182151162437, 172299731038918152014941743693179797649, 174569270992749442971122424775099457393, 173948972089406269699463178902485640737, 332873601618043630484147399938277268433, 198115858757631193701515153610837413251, 236197646191166139823437499352682627943, 272754365892875574613680419631085296419, 284534349382510136758622371568141693737, 263531636280381782706257052038334994967, 330946504428743097542141406361619215733, 210082640494012234673960473056078811241, 317494298944351198830602274888138462191, 215255599855994955608240290636670596919, 203953245020051226446278040899583934277, 172032344975793178455537139190374546267, 290626777870627869433567188562380626797, 288000515923007337765256960488481794611, 258361430740200085381933112980085661203, 226051215167946371232344550769039380239, 189090246098690996679879190323514843271, 197458013143874445104149829785961109719, 292091740939242531470911923616104284327, 316413328926115277639172876137981321173, 311406967952178113984308045064796117217, 310001738224631904958232896915745363401, 224928490804966146692146013884682505589, 292180748001213763027919525285057767993, 212573914923852331227431204469281311489, 227620600930742625933721237124124923533, 242883813043974142974420735883348678273, 317841201792050963526527542895008356577, 321237210294070152141672229228732349357, 253764717890193724145224874572321243609, 279854397920636111065641946583981780251, 261392989770297575402121198700605967693, 284239066236026532465489658323767165717, 192798008552341934661555930471571287071, 209076879737919132300613312558554574681, 320366106421126199133788038213238812927, 323287441500434417255302359595317538093, 279758191129097393614509934182381575179, 184644703742226540333031178833883065027, 212911278028770964015401710511655293799, 206843338982212420470989182399821091541, 248454232414556710958469218277300396707, 266350809338605617022520050759173498053, 326857641648212391566537149779376066429, 187484589153580950940867098540997189439, 209176966481763802660789978216286166677, 301343443217618119227426367870504606019, 254942126405123960754710769548032648837, 333483738827979460835161983759173880331, 180566702053477667957576237778905307829, 246736872251397465059029734482699993779, 203106387083763530166782874251175451079, 199376962780795448796480004460828431141, 322573493324357632143221995104754152241, 175814175370937932022459804100052460447, 213634324081453756117305756430344836621, 214827187072577007077853355927909362593, 244655234936799186606970725843782870759, 324804586252174878270637851090353581181, 287359915279824697494190987464256364341, 247269043082878476692697149375947052149, 302338469908298163112256522976008569457, 289434806293499765116932941767541425211, 229057416353239744479802881023111631421, 327991505668778979039768394712338256891, 249082219330502152071434559571983546191, 188655206781090081782304255721397272339, 187983280180474789933439115918668963347, 302810076351072793379568532564379291413, 179983945991868022695731244512353867457, 303408078743600657893002387525244025659, 184759799104960290132730492819766054419, 252544862754450324779293788079546803379, 299515673227108283952173302803583334761, 236118799495228902005701149372818965879, 236590714260682432996480067217612070253, 214819142903124010064577278472991576877, 197133470075886154523993663107288795949, 205045970087544407523647907450239409677, 316373380852158301719733582972879650137, 218928406155927721658582131521152158759, 315882518605987765196718629375355079147, 315097362662627756846174491643870943521, 191714221078719572086970056274214184907, 285936816454379064411007021556389583213, 173575525882554836563266706913328286891, 196651383774394803481630181004004384303, 182514120574454147798189150099542075489, 293064240042642364970944127089704652507, 233605616215173335474792138753824747081, 195552128133853934784779965505929020013, 221461849397671130181426997258867618603, 193210517230984795850227680145958496463, 207600148416322729452581718481316979863, 240145829744607703554019610794202112317, 311450158523987602626695843612855395159, 322937679068882595239813181119111462509, 279610069114059126983625234227313386429, 235040641630891222889048332152657197573, 192033945161519574650714306533432932353, 307877476491666010721342869961141484149, 301416519475855353638894212489549594529, 209457484274072635767240796019046379373, 305823163627573236867351802479481213417, 257219348286045335820106799886754658203, 212145751719873350958928352986515021493, 178752153414941325109609938036063929807, 203763451642530557308940300757366661273, 287444007899138913658550952859071973553, 319960791489167312659991964409042626827, 180829215912992198409180618472507119113, 325369352646280120531765349085536828021, 182222406395356915273442503868953360351, 215038980117967072271036727585889091129, 224940574835414476387174895198533369489, 177283039308792828300533485201129211773, 217034216237553069255808990115124290909, 333697201199940089716421116525018796267, 235831453308309470277295453864079648797, 338139382198711394472013976474680587707, 266994458725307986215524437315425853877, 232729266197616811959625567115276065241, 306873354137582747808224708886371475971, 267795029992524037770750737145672834781, 222484809356454009811932177683176234603, 217658364673427877797680049438167238197, 183789471696265034386795392033914459047, 174360211218068921053866105806128815263, 202441778824215796333648744714204673329, 272459616928555560006485300508758162911, 297742812956633114598717325362212750059, 277893084236559757786585478736093496759, 256069265694109493854343632822785184919, 278044414111594394229563476864148997661, 203967988557681684709750870249576050629, 319512570940518826867377125950169965607, 243873321660182247913265888411231222443, 267806889497007177973187231481118101379, 234171719033259142486705719467399694539, 239932230988783334255055389995133334169, 310643328185056991866261528471966499089, 293896032495273238541349195649721275879, 267225677607629417170835296775579262967, 316826233261079253996829050104109474857, 203049459623390845685413043822201547013, 176964982245050256926987137387441924591, 293773344322904914458548688238399206173, 272890712628238933267874762448093155983, 186963354377038312597607180579500614311, 225360384875170051638197801843041832681, 201449058733944630998327251447687547081, 207607844731969619081962950750388363949, 267764030551432327236903684430315222933, 263482662800635292809887725293800940343, 293297465458055333318023179125681909213, 203695990119137376014042652171970725547, 183761139979279021388454616689964716097, 244168542722612367578557721528675418797, 199877754772242004722718835745466711211, 256126633339494864912582338028837323467, 241256054771958579184601317036459721059, 318757071104722606734951428387131691537, 173268771422658563314031655288220388519, 249367338375063824234119791424085840051]
c=[[31897532457274501591934358964001593139, 260540534267032420113044951904942386555, 210053675546933906368620431521163462862, 93435879054158692797301738897462145886], [20834128323237806554569521488317122541, 68773824030204947055061059467145109372, 10783886674325500603576683309362224539, 77006535797375425216344141553818214481], [205162247330767895393645043129700901339, 141055706817898443976838412564552462911, 79706146802485197810856400668405959179, 110031372704767985347282864782259992585], [124304868507066116416850883945087138460, 259360942224170972637950881374764845031, 63892793599848674637446689287748563343, 46223899182831627138706642524322017621], [10115188469419262841069186627081915711, 212784515963082935694346890587324698914, 9463736944230340015002593806477699546, 73647686338851665883421248166268109437], [210620269671614771373901657096628382266, 188212631517620151138069382055839262026, 249681257749117341406841180962697204314, 29638764881585538352661307234981807878], [72338479789243322660933121156900719511, 44570200642306503684498683901677508087, 122705229410956778144226775052849493305, 178973139975620402397250128453779080566], [168377511644469086371496183660100031478, 36443314157384893372573420535449899082, 17536466693848696392497407671379484140, 55246158572126186941761123286889182918], [156693912461453914242826332355483137074, 190977497448223609919393318605248393150, 161940999852049754773756231252867354203, 47946117361005988258692020195148001553], [85351470764416181865098752968216046358, 86119336722026219736406315507128459510, 25432967840919706573972138350283338727, 89880775337162533990361318053441189922], [134945265054351517121617964171504146684, 166151826165474748330789894118323256993, 73019696056646063891607896393243716846, 71256775820641335917075761614673324393], [26959330087990683959706054271946933757, 83269009879384174083150239377968189276, 35649359395098977742465304208679198732, 94024149938687669086783227916625564890], [270713263755324509763717498541799119954, 325752395093441826465908782988508854225, 238046221868935344327880595455943517622, 24510959023778272053291507966769213346], [49488537349154035214789311631858034775, 6873401974007141668965612977494142672, 307756875971888174405764296344705592058, 65917479454847747300303876654335901131], [82131315246355204240146459117001543371, 39737864720343649590098014773579062015, 72216593324855901246071024754129406851, 113327775397086435284303984114320756194], [53738772087049441799825537671144672354, 103904973931650393333900484616893136299, 209669509767852305772503573066871814957, 96802447489832157262487776231855546117], [252235108000183661595662157181023165063, 58254338685315383597787238141107635302, 184390689005199408876169467461158081163, 172489682515686446264620902199083908635], [159548316534562399631747874897402590353, 135048958084493059498020304385275761781, 172682962081227052520127672088515057706, 121016232375940873649838462647302622773], [47913454835453370630423597701266297295, 185699303247608137209842790053699113994, 137863580526614299644510703804136480021, 161471540646688855943558524865385728897], [73164436732196787144482926821584056489, 128894817336199012068673663318777186576, 151886610559681849447528603631644682629, 135075125454351478616170561963891848187], [179973018746320671444160030097155768922, 86283859979117297802011584299258410621, 71403791263138248387402940713453865836, 172258497448834530140956613448809749613], [167987226121352566822813107406134452323, 131054923295622763327959786930089966514, 1141280432287873688232846583721706461, 96882007804640775210758929174079998880], [179284968645408480591262447048379487281, 58263496463833587483114802892271391386, 149909492737232095307018683110788804676, 56055297024789587843407371221478220508], [56786067967212111039098546080199123707, 143490616832563830881722110611691716208, 70613729855072185320470096501645859159, 6831648457446986681624079722564614052], [166636059132417127073311915481545308081, 118334938576626118108191884314219265643, 18551748013687454220421582832915261636, 210433811811417991359095882570035284844], [107647952675295160538642351248225303426, 167397055090019954475211256487842946115, 37421514985810822000967985119077438511, 52244401420068594540411287611405656844], [68644004653264861506769329550378577659, 278405989774673012824578604439745456387, 150792549098607989668714254885612355901, 188720437177177099679617324326691565229], [105402727315548825483308779119952064469, 182474354003672399730811512211965938027, 154624986710393624407148783093427341360, 469236551782077806607849962679387008], [201240237289260214903693879427571305765, 84014855140462666856169467105372445292, 89922790797358508724052909801732926140, 83176091370730096460519112633042496902], [11023229341522862314941576973338057643, 167331426958989469158211388378744923901, 182248319757914384375839339939458900100, 118658973245375171666095975907477650822], [15610992428714257799514348158901491940, 89219476279938561096355494718636160815, 76259729609974780371009643256988777764, 124546450520884473865584394485612869925], [46887191371711933744663576986469974200, 188855961076958056769439817993596752135, 20673685879175365206004908813601737646, 144636479009771477619804891603807938971], [176202965085040227827886820257495515777, 133185078430659904306773644832112293730, 119317685826505159812084026466897460228, 19588388115701640888262118027835919460], [74183750256029504230800292092615154486, 141818012677622352835852802873773780202, 58639108749511440026090572734088855150, 152741401044888831794183262344946548280], [141655098117525659031294865489288921978, 150679593743746027797864688024618800518, 83497330748295480763515514060714629621, 156996039434961091630212486534089522827], [225481751310026702530334473398820390103, 149512016985690899973453711753201244839, 237580869716781931909217698580515555822, 232828580827316982593842239566274497411], [191974910785462824826375236295916029746, 90180882560866753058663561480680447870, 62456781674109277785632986962582738982, 207739701856530052927324585501719501986], [245732925293668526436587137502804755127, 77479036777470745374926042252400555330, 196183090784194367461853000474664546287, 105272414697605156609960073196450152024], [238721917819937474466806047300598518539, 14275679873991276389123117622270251674, 263743883043038183632193313705141843440, 164618706200586833745238791945313193808], [41484675382903727874232509656468913379, 158198968054942088850144042039152542202, 24742360306056178864757837571962081210, 83800573544640407112465663718164213541], [44990327654300793191598693823943589510, 48217580036575497150242312380435436594, 162837026575766611888190484039439612034, 164194605787571196590976421773781149677], [104519554729871466257364491962910562293, 26462274614240906929560788845594467700, 91580333702708964892619283680873316379, 32790931906717800116777874589415342319], [120099833951292128999106244575229471700, 96321319919194118097363819251071292538, 28896394451889031891593843617632216354, 88276711189079334996984436333957437560], [174107471769974613006111993261661753448, 266350870399281824248784680488916121385, 254100567666807444239725901772052489895, 79738173699821412242073280352183701606], [108544097770221412382986044105383469538, 116721323602344016405348145781068271539, 110908055577568587983620521665720421131, 46474303369510834196888196691034663936], [81495700514087579755223636551900337734, 52679436541007597229486391480244036326, 35120440067344335993520583179139850169, 48905133395847896291860144606830702269], [21321702712017936275877130704813668233, 227620219626815719820918898214484682492, 283829048135630434529145135977203156692, 167845696880519276024303520617761738964], [101912432526926179201473597305833086094, 159698848966573715009278884819979592968, 84847166050699380250256489252881727410, 196542176828735810264053905199070460963], [126469773610083852371420697914592167484, 178619075422125270257404822597439910820, 78287161544222486949308550653145121039, 50253149043915927965716773042387507730], [97479694087338841850132885735719816519, 84182183151645959317866799120424936707, 24205403984587671987721365276768482993, 196842363452530895152841542411596077721], [190223163387201695220241445943753109179, 47816468489744213288720633538444094829, 80324597354158851165880821921793330208, 89863436615053571847357840017561789473], [20530630500298487445211642473558599627, 132957377111051095314626587407671813080, 171806357363295279345839579537423198795, 43465828154513274257558780523508276387], [87085423545857494411165834646483538580, 265588588061461648945034010475387734877, 142528214662520184504862337846456012244, 114729364722350579174162350842559886320], [152216620527517516840042451587369228924, 207549833148928969197246532033555801363, 121564247889140224048290671608408814427, 98116509968324972107897058601377913958], [106765776623701167072766253911567328, 155443908389156485651537910464916349564, 49594310712078396826829252932624839976, 56801084837695142268834678819116203940], [109841462790897197189881915072467747932, 29021721029870097162690056264048069740, 133619551202133614901368012637035847309, 24877481787628180782804668852207856063], [128230778863202260622470480337042045775, 129070981140790439858908403754970763503, 171392360821568645419016147445740467828, 7577256858179186557734239331944026927], [32424748061513413995019990872590060638, 204060186549773754407025342178423867604, 179391115449129279773347662220862277403, 112840132740656971472073132728695953500], [114943433747687099538398800517713854300, 247185433078957841920443960590302667167, 227948728081539189545610482939180246140, 98534481826078696939037635669538784847], [103638418044873284640718078642499361677, 183747490282652454766583307781873067086, 236939900561404293627194568881148382199, 40075884484073624183833355093417308227], [59077974122479490367066851062507472226, 139104586706538418261861368806237975860, 119840002308337947404232545466633950072, 244605884017710315270171924151509547321], [286371004032881004540161849950078725590, 37824597156953769980465857182619539048, 157322708035813592080189071676718329815, 44030443710848065140261001068269095487], [110215719618428889434442587806304030563, 465757905872871022214874471862165481, 108085711097332241510510004956613294977, 218181708349685105126488846724496935324], [152936131197820041979308733463928859451, 100664250956147174040977998270659119347, 3098025354944606357149341308364346863, 115254543106209030689789768678904256215], [156412861802894894908492324039069112132, 161051290871050048520599512055013711961, 148588429671079513612867916112081538315, 75002646122576491635846635369501991244], [185712081315241603107630338912392395894, 22540700788543135204466339983601334194, 214781140297904722995652552566161495172, 162490590650095228998661147192445016999], [116582917021192705481232842492655966970, 6795396313017179394522749942677633464, 149526907943962666855959112757244502006, 2376378050496964356215921209533483247], [18432872423496295330016260844738116737, 121782716111382112086675767117642472520, 152501318585559847175144825882942716257, 22651896271384238797325993097420198549], [112203549213988053061854450753836167946, 177131605114623964530124289099797612176, 106572608947930566352330683009459651601, 134801702595913501635345652489077397167], [227872871358862245755050868301060598569, 100583463312885151456574322897115652814, 228499226713727653584380238272298588262, 131926695886392418197833682994044719967], [164120139805609209728724123731645785806, 28862074492950348898167605006256962084, 267213779732724807919245284839146009950, 99386091765908709251204249428175646522], [166716873209147556730539769222174645051, 15453318015110028282800033378056569442, 16293587930826747111491854649132874757, 88107588706690257091998720674252867481], [11197873196518825375041137797777817204, 77604597423550278297056815879540947588, 76403273435196741745559175680647779994, 71834507357334257927939137849112525914], [152191264117867259959665051018961257036, 265826611927902063806933794052525008942, 224841202976592345550644385081770421500, 302682848774645056736632312120651514603], [194194061161141157801585562131913092874, 197973184227602104044324492061415287887, 59589012996347295061252564013449102218, 45562774873480897769307702303626600558], [95313519433055074811016396070595843387, 142126918962036291638808594490470749409, 79912537679379033963183309417075373372, 146220611809005737570721403801849184899], [130393397355996822735740898348317166777, 34802332625533653282043210781666169301, 119196128372155970651227078365559349347, 212338223396271385772690193886319383969], [197340148093837205202183413033931598925, 27308099347695453016450935854641458418, 219300073131451723231602364540015943707, 140092627639069658702600054620994135289], [62498686055284186797136189475779623171, 64441704107957134156195455708283666575, 111085652822470553734070393728235163899, 194615883416466198031213757036608049464], [196876418286577221312732898971791908515, 190741022904957240620906511159207681378, 43082249770695864417887483263346316964, 260040300441233799050048501102648273411], [6885703852760573394847708706737085874, 125168509304342180155217366096720916820, 122485580727367221369072489436942090578, 294215988835298845610835231698414565383], [33900951797218430723397816038757682795, 99626800172356933461870635381213813355, 156067854591651189512375266494450209064, 65603822524439010309317211812504240467], [175876453373498774573768307239435355466, 32216955752585474805406139541377629504, 38856947489542884042673770573736527168, 154983109275416579070985742154884177889], [214940210350683186945331670659523709576, 71663513746134767461385950420494725425, 21394480834342498443351260676058303600, 136921570392572815964353447921732889452], [235961999731675063024036425564841775757, 107726980930311474916680320756713997980, 213675136729111083685262155615669789996, 211662543728800887473979764917535959116], [209950006559930729944796155073706535188, 53916329560493091264095601047579003142, 119552959762077386402689014436851576232, 140165341140387547226761462085695807765], [25192128767368484826444318005242106788, 56388430704752178135440754463993710153, 46800961071886890135012943902643585909, 183415646979453140991436463461994700069], [55968071704586306682677213916961904401, 148067352857439969961566326238812093295, 167580632798671202874661852952882183733, 239565605760303511677618536974889128099], [184669834691809767741957039703895212772, 237612102354033013541328008762303516268, 145157534511163287023371430105838282933, 158647071677968212569704915928673152496], [43798705980750507328860760088552035966, 2065737625587940210789057272192792021, 169441022629164071520835169974862151877, 11876474718605574900466919690606261942], [44163565940575068976250168042996451274, 15540938598055324178809719497533247008, 145045684094382802571665311381549396934, 47329389082919191348177640263342172668], [80132867279323561522278952353452058648, 126219019494648273906587888530741387427, 116071471768509697901298524271715181404, 8012817687942374276465133414626147401], [29435653434143743892675687088105778041, 22428873692644338385975832614150557194, 151519820775416032040980693676331377164, 219028246158524803611393015748003824572], [62619359934500108768373138054176734852, 92350758993381782547553859576075035533, 119005938290726485277974291581443650674, 93947566197509965030599752996637516178], [143967753270143104057283664577472570751, 149003552411012966407489630501125173161, 185937144318646004636945296407461968575, 186876983422133160858447363235711444152], [101902343396394560111276559681188381952, 146903308856570846867474159342853868772, 74930040334113349599787303658405995634, 252840038744538889453780646718298783453], [236938575310510027070556761584251551230, 79840537827875239030823120160233501821, 162384399449751041021982001560713274972, 165701933032391701623504365622441841186], [192726368949343670733020412498165549818, 79487274628296787217770728572810802654, 193411822808953950169065053286893174627, 19424885446265082876463276310043181227], [166715926025982298656755015006193768665, 258636227471482655867582205864727487847, 39078544263451108990802015811292108502, 131818529783549526417785446291385386685], [133958778641211261696968490589686675881, 104021919705406994721291643426570952237, 120374650774839945376634528983832775567, 94303460079200567962097731277532843803], [279283911653105230220457852983476968504, 122134654910309253305913748196145758220, 190668382693194757420396968486810334597, 310001453344826744106537794810318637412], [149219377682089859173149756530521396997, 65572270716601480535622969578420956915, 69968417528313914983091001057519110940, 62817967639741588814619392963952408139], [67480270395154105901379694399779152705, 22878050458878490403658394494627686160, 122648837392669422632726726713525350143, 163539664666721308491548111618441615306], [8279143031979371687110849986511945318, 89454287153215931017668099272987712583, 146877486885038838920639689486442985953, 25231528150201155140024121919529449514], [177641384477048202480451960877358537703, 122770279774277115161354385552353646573, 57928028466728338910086060038406570528, 232263665119017755562776375365937299017], [244014008525503690184921030993232520874, 134334765859843162531890380259989625493, 41410636511669605151878128048565793839, 258792138406951873817501739530872711905], [60377989719956732168703552752746666004, 4531322783372309511574419151642915928, 95048014520599696783981793151943106526, 219123828239024966897607811084419576192], [198195197395322101433954012461969518042, 9078094100178892546545843838106080591, 98585510978788115616172632063912623320, 16312648788909107837586694853538661357], [180728041746836086687069292684395503458, 121971288020106371415498690683868538740, 171303583295701996622757348580574503877, 56787219635650668298208027442877897713], [92359437366165702615148907991773687435, 194623404301477691454784201777050417380, 117674530650269070536323579018238473192, 100781904624554079698388229274758660961], [232008744414429410039270578828979648994, 55165845595656675418294275568295103602, 66647859177493672610418441226389631280, 225441197092489813423262519877953853263], [213159341798863839539301213461462949754, 9124545163983318137096036858968245157, 102211609279279649872988133143845387401, 46804597721407443555595882201272537531], [102713356999014122256333452248416798076, 299867859778609161386778546362112513749, 309155751278871631731267080129402187608, 166889064828376714198895167825419843506], [171698030165372305270556433018646505159, 256331831467266196993072783618641290543, 66402730125096520081477554502711208147, 26898256617238316470657284095259417563], [111043786512013409242934450974653226469, 17217316378669453844827658690729553543, 141232785400551327057416017380294236166, 18640014433965118917900872403810654808], [205257350354368697802500640813113483170, 168697220329636622144913505543077319233, 5434999904412442959910019030147279312, 77118181566970472016257096103396082988], [179720168027750956257025692647563515448, 28242634610289624267235325720776803996, 260267562961257310665879588959057955, 42287441798955713032129182326476166628], [137725096420185491291337204842025844881, 131132392771012189967804857438761022984, 177513849731793381523732296199442352478, 31269947606399242795863982072099242728], [105033086484408585024540348017283204042, 215608763962866540664290730729780205813, 55837009755398457664882455133103612475, 144925479903719629135483754028283227720], [270576932069395079529705801532147059718, 140857192924034215840058329296311234993, 255401544126282241422914857981244057609, 43207203952384790972877867168167337506], [298319694395495252252144985199655478627, 250835750535764602027446947775064124142, 61968508811788216082630696470455725117, 208029663919151835114430221951777843777], [176835247291789220374976344037228108436, 220704812126942508903606980648306288057, 178322826824886930580206562086677698252, 110384283866815960758717316037165556435], [57499176692206270608295937546342539259, 155885813903893925936745592610577299753, 261583010981769674083050311801950590647, 91881171800170403399878920559773841985], [96060529450080470600279243297778165947, 88687947861840705216032870411829376127, 55005980769467500623571988253774154506, 224925647280651796777768938199743411236], [125729692316584910177511481042638005759, 78069605397041410449680274964090964514, 203714197653281384011465474424281728604, 282888433450052872915484022868908623300], [56694558331163220125181229120164744559, 141615641384614863771798782597418029439, 101504949319499701638178720632992747871, 178996951514087922888564651494054330251], [64807177235819811396193327820215014382, 29365272231715117516793789160812633115, 106911244238812874955404207985296886306, 84517363873312439934656330328257754253], [223176674284571141772798792007141346623, 316982393514389673066650392518278453820, 30003160500172774483762326937865357510, 285571410827080893055630467776950375686], [179145797703537848509876706019049322904, 119959855975201895593902243415788956134, 97630392955856867279298866069617249728, 249919748403239450702498242497022172769], [255583551293032043864864921582840880193, 23792355273684024369283592552648862421, 155241016613501899608777833486812389780, 198518064609542624300565256518072513685], [120430036127245731949579475365968047790, 87291042533926980309526511520011553332, 103068732227562237967610544225787001173, 43633723162067718536459803677612839414], [93227115117254082594729853937575027050, 162567801820947205245793124409523718084, 83163683200342998627792318227273473506, 47834016137885681708028822604863319213], [76816358989066552202114359614533763038, 115688906980275061126526335350480073168, 9505946473350507903654417228504896710, 157766056673476271629604073399998455428], [193312635015953732303686257292161152994, 70754927397539064153474559949202873140, 156343914621961471109476960175463894551, 10705435796869505992431094138849866278], [230264007080338324146114216067715940453, 106339799819791424081427044413622781152, 83405348090890135769541277073212959855, 96101925969475852475334000530114168712], [295119785986754732277569807652166195052, 128168108366994822989004324931486801935, 152956325207953283609124166267369729332, 128084534577818078660288608736327929986], [9777188594813160963013176136814270562, 85423166815925896758280922862680263392, 176189727313130605987037198961229833726, 163952059386627921956804712423059269438], [208852837457812562027174590511200520774, 192346992364092467029882019495222533285, 26555083545371077199578238370530732095, 64820934264966442983298831712442526022], [98298344177629317117612232174502468254, 232560574630147037015062258888141405156, 84809654838645841951435534653874954636, 1513654401050446351033132356729253130], [181047365429204445781277937154474973752, 160343739157989935623394229684136054920, 204035983988720604231158337553957292203, 194227825667410215944117102912013303616], [146987694069584455797744888715736336857, 137818111056801761011605101582738541425, 199962108049457938412775462633444362798, 324133327940866377428823508818621229736], [143000519246719564991326340429555385920, 44890329404213354760444689740461329408, 178016720685831462131875797645819602983, 142819327759924894440544148041612133340], [239125789394152913905522718808542754298, 85083117651755159245652303485994557800, 34520315580520711086278797281862011278, 217356112019192355282355283892304738269], [128462756224796362585898410831715878391, 21448222962357517726674181504263395398, 65379582248378220380598453634797912694, 159025871357133980609935640613219043761], [67039452454699858046161229310473390397, 54513261154370407670131592053541447713, 131716234846085524663133818770108304793, 13895505114086792542390255816410288808], [203802131562338951277146117671211911492, 133923560921459977006053367078974010006, 305257866328148378282331511810514970975, 257806991339577396549547909497349512586], [134797422064890595103139536412458399236, 166093973112040515716560472117479648800, 110009776329599179322745450256286466672, 72709271612456853710652125065641063169], [173743999133483840428763191154199813335, 117966337103935428654784358022398542105, 170462080793254638237467744491291254540, 160361068763899873792754599674386483757], [74517938191138607001138998101025199309, 134516975785321767204096609955053169452, 132554964936872081263669786004242189941, 143522865570400729977806434934142705527], [199047783436739257162049323029446091676, 53067845489046938563276068537607643941, 154827930240607737114138914752064216834, 42865719152601260934982512860790753036], [18104801435982638412382975677718429466, 198150889382491457952590458566875648711, 205678226913690001809304728597374350136, 198411684489694721781740158338793170009], [19749528038839538597379839771782638911, 98209904178987212053661287328683027451, 183959978234831608533115386735994743756, 260670980463598175702166403260567171819], [188066401740927470350765868092138783120, 10062561581219237831242007983837443988, 66744908744548694566139115810744984881, 29382816195161504200570987348519871905], [198712687134089701185166223120312138569, 189634339265551888740911110314449746567, 143128893746349046436460227240910168224, 78463204902229050955426803458708118281], [51574495798530582800821253841085643620, 192882723656514333606384658087211969426, 54014081163770432010196627872365187365, 243381578931368062193948551739489362636], [211824059560763317921014653644867133252, 6860715825497891582549325698814088699, 189936747716673943915624331951913134987, 83529135630205923629472306671975832760], [254891574245497555814087610529956257659, 48108601173020617522809262539480040797, 255699521374263211465015388641788944314, 28318751702197859729615217127606847774], [60941466681031836230960013372097417803, 73733073110061649791388975471514624118, 199834617039476797327043485469253995156, 151967335971902266786266020343735791642], [168207299684932810699680329101486229393, 131955951039229277341637423816916462078, 4226459288103601880599508201004378251, 180486640023677482181170401819875195430], [4393822752848654477869954066597981541, 63260657722817465847150037460784277166, 123581520609651415810962298951586281133, 175882600246305006811717152775737875380], [47877125916481193190249335133165587663, 76554384250946002228763064000841829401, 40679415271073413212958907642145884489, 282603802372514046856201711909870496177], [88573997164811374159678530542665002884, 141918863410691282699509137455835631659, 90007949875448028989558961444058480762, 132512437074211330240409059787133036185], [100382430663875952370112576914310297202, 57159151185664008758047252971441823559, 129311985906520635683157066472700727712, 47164093138628567833074862109581870101], [175493384537228011026469760324776078361, 137235378375891622999912053314249719308, 144240354961456072085462453449952932161, 45880950916255262179113194258678947776], [220314220560463702111232840558415540957, 98732050430382865458515371457690710765, 56624964662603525169318009897205649959, 116478274856575621352232449145538687036], [38904300508811713116692428657187818402, 119683747080020069623870247768386559291, 256465065498744728455692810215956141431, 201416651608848795751664047948180088792], [234825481185218792369396391715368556181, 134697039295215138419364746647860126968, 120227216494045383392111745511209499583, 76584498465626463015736307676456713095], [225614711185056002130253658371887030783, 140355926673483580795060437472556890563, 102481021027748329796179595961852446665, 4900827765937030607514189613512488772], [196395547712370979649820834395093611828, 101113488813111436160678584392220522467, 130596538304969617387712408584463153172, 35338490641751234023605789368942917066], [130653660884936432442555388947162054923, 36558899367148869352171298596877617231, 14662145669493021049952084980329342025, 156234854241596071425096867491250716374], [10609853575986868181760428517788225397, 152260392404908849315928556709579718198, 23431025020073064931678000319979696623, 58943007108967016163410944931008781474], [70644934521889819403332429342600499923, 177564468884223291777619881700517542420, 134899876150054127119472062903457595866, 1967488057022599632317045974546660804], [125547002059450833786241312289532687481, 142148350737330675297711596438043475796, 10973639451342818395997900663685427755, 67582928198480173956842277234740463610], [266488969782119920540633032669281534616, 66117733522275813849333417854578650518, 141762037285850733451239061530658436602, 76308443302568912908067676684417909809], [86827443153622345202236832496465504683, 99100440212320190716984396119785111166, 154722965921805091158138406155315300385, 147401379911400201567720303208236894994], [36492531490713069706241240828408353834, 4593257872763419878681180264012382895, 31844514481905796089872576345242396046, 167840744338961105507010543290835914746], [253126578278445179144208943210135626649, 210923045553095393516336130464226499270, 163120580167650577670935745694939649274, 122786113438434978744134233707337470615], [55983605043043884315627172889713033874, 23053181146612926190303803910850196569, 172505746041750885753548463625108151054, 125711554555738033265620368680953771881], [26187448881484568117989567258874466441, 33575849311599579613521432882935919983, 120423950661894925229129002400494356589, 79613739272603817477937533799616545081], [159430095020735085206701571240219138526, 71471208774860432450836818335813307467, 49293268309909604630799683912644044667, 99506108463397124507125781075251596154], [170393635965899223198319031469312846801, 63067321154245242665814953178790015421, 245958467738172983804007349596864223848, 102458335480243769589930083315217985604], [137449788067606776979818484827731362927, 60267896519481425755904758656419947722, 46387368506554736893604586504211563529, 199513905309402816720863608213061061192], [97100573900717867128802050336512465605, 153846644521089016899159837173845651709, 3181090004081996890886681786431657748, 189146854188541470825586599766355772419], [125257559569663001760247149834724414541, 156784768484860353817100076453854829362, 157606698210719760675988721352238636378, 219419030266733603901603226259968623274], [40336779846457561366722379216774670539, 68625874836737453314179194629520114414, 90270435228178562127777550562827787670, 93092119932827181459165700665411937549], [10384527644205220890923681712335300682, 116090708130959652765564067354050952059, 68086537559167312664321678771480133746, 30803099580253438487972984114058035733], [97495081489902930876107862416265921888, 4347124474278607409270283747312760022, 174710015959534371807166601676378387013, 69413541746521358763432128377274785286], [192650194014574171013257953787769704325, 56042581603580651499701796053616999838, 251333586114869877480690684937543615649, 191454564023061332448687687236252349513], [169230268720110350729992056559264687555, 209817029886838348841792805270298494505, 139969644037944447566066318320430080966, 68243124570859630661449483866498908476], [175302552374705837720467475269579578333, 34079358790763230870981356986611646282, 122352520290484867079165126569307871703, 246205819136363260969902064564228360392], [153917776256583890420357539031903904682, 69934970139538901807092647204185026875, 35267824356186459862236324136288995229, 35889850508510704638020458025996381301], [191111330006905408922211244218689967286, 103967866292927788053702079881410218951, 27953079743224067396448772253162486041, 106729358380294060600139237907651506042], [280253596135062347984986508617659441731, 307487827917038788548839273991439824561, 36894428628732151408043072223121590365, 76420543758154510081595316427622695195], [114681455830903256868461496567228454543, 259580757890921331422275218383449827416, 144296827350577668511150646598925166478, 7812613557717682246105027202466243086], [24046670660179233524656655114208638021, 162658743113403421198755229358375570953, 110884497157911025013721294489306169100, 93866799161798837965666714405069388354], [149840280794716101298007531949344254750, 120076726599553619261139665380532106450, 262176953651249097999793313718741344993, 44904424560653493661680666680215598411], [4688871796216616080105215431881746450, 170451121315330123411655945190941328429, 72222141254270208332153892040260212841, 165617162490604250009116549706169344823], [11597777778994864686161778877144021093, 203022894113387657039155443269599829026, 208907846095688820516464557354004252160, 132062942310162283565370990597453671981], [41073909076200760465362160649251450092, 23727600228727219264630085792353145837, 71034297091393432635296182734041407924, 77444641722000464027601097873038268978], [108765902505582520034485131403541233728, 164872367161747570524607102879341437838, 37935665682628465679108932559946500579, 20910522552049838646870946691922169971], [165422231426632740574403566806109321717, 78811426401516249344439238013196686575, 53905513853611537424614798185944033938, 35098288194316966656976921799299174349], [226121221947315113851312366628030373200, 207981612010258910574303979621948725987, 121931814513467629622339694230795183220, 99991068080483988015226769581306267588], [106151240747813083947144592666206469110, 54497864831436441809375608839561551267, 69418088681840099284404538825832393369, 101829998463229867819500690594044063774], [266303888310584340591690271087313022799, 304907429328736369501865246910839592797, 159099547452886359255873818709663053981, 80209860080729195853557772751535335340], [74298777915003578922337096025923207281, 5191471709700349053291668021754266675, 19494292259443141214142204148296718118, 69293084770448593065504570684868134253], [205038495954790150472122402476160596421, 396811295930185828326567369212407256, 67724642690131836214727752767622540074, 16948736934513870953451424466347261863], [167822991754817407976867686713451228613, 77415375218269381319958439137508521812, 222519208120020634338440669370537076580, 6937776184675400419495028215829354304], [175401888340414322984080648687819751705, 25795066437375525513746874209023621555, 93948305492794486095550580171559196998, 122171028498716765479586391450190378441], [173080273803226023556047527691499520552, 167015379533416052001559305585894763175, 25834729150284425620721098783096817464, 125823421518752449791514312812853703178], [241832912338733874848465800747138313671, 225217149432340654610560613615824334324, 67247358619506799183153017869102027915, 251857884773958194236222358346500245133], [128655153235018571667130463073005935194, 181515889433725147309018021180761357819, 160305365438594950590166073018840110739, 230318921969131912559993979435685954766], [253222561121322854521883054260318764123, 279319985143688824736589010774078687212, 299326237631431876410741943095874186463, 313664230905206897829529779461738158486], [58864501817261071084509901786436063534, 21621266588007927870884208988127070051, 136223011690283291186523095459208553772, 138738891151872372222653886727138279013], [22587536947941977848069471140678692225, 206890834379200499548117083929793587477, 45146183695910686841052850805793125252, 90020102105806551479111193844823628368], [260510437153561050650261107907616745212, 306795555860485658202308198898958209858, 253409965894611821242550921688335367075, 204193264660612222529494185149333296599], [214781886323002343125130596411911873603, 188828117468300122408709091982694361599, 49347192541543988427356014856499698735, 87240193732109052572611443879746811519], [31986480139898866442821997878970993217, 595536776165408829000244529314059196, 121637232813314248866900070405446179979, 24586509094042626862328680843834368285], [87430081026766412540055190073895532458, 90141514480360900567677227335862616364, 9117781317677423814101258805296075188, 173684689766887691510362351894795514261], [6399285297479902080394326139761180931, 164167774484975295380593978914731111801, 167247318450826586986286320243664532381, 67531588807698123563712769004565744177], [63116198539915858795979965217305455235, 136836837937795641644765059137709479659, 170261551285504188251278814153024409513, 163474762098674572441100094657192771916], [118728657569954857519265998725382047309, 97285636682564986778444811022192588398, 105273567015655504010562253071906116999, 29041444335645521444595164610440141462], [98718765403146296313053155381264035563, 46648602894216204431864025377563314110, 52053079921873669276472899711052911165, 156110322353299321405695831673959251577], [179179357530220115023126874124542793576, 213232403728554457916200216239329937971, 295252310855858236992395683639931595615, 36629614886703386316441308813097048431], [122112494958252678577174423405128851574, 78056945836677707437832712798300425209, 79430817172650872865566207702101753659, 231293540401332076787599606075298574387], [245192646035624987923115205410501771132, 195401166700413610155708494084887585222, 49029593950976043717695607572099838671, 167129174009098693361798538252898717984], [229798655292417846853991963047436287188, 166269037264509671388404392583268202717, 215761133842311628231621098934774667774, 28654633485278560719998009405980979026], [17003031897865761309610908543119945911, 117072405545263761574889451784339521455, 131893482601428765940898498442651157907, 10628699647249119854732083748470431143], [119407047220408683308235083192472908642, 194018906527835865777634005101275756790, 275573755060341117193864282698809771054, 290236316596134697947452313468264847357], [26850761006925669274660884341778546699, 157931094413042826883370036833361286033, 193847934054560732878649166143447044039, 13922183004661828810006812984375982109], [14445558522874703677220685084436688762, 251673482351051707737854970928726443384, 81565914126171078380576464957062679949, 259157541725205628919251362997474535738], [43782492393612320417440631398521113184, 174980147107248619820371960465360019055, 224621717853513719349239542617943086043, 167311836592698550149108043196104676046], [164451085486448622705745260481300288337, 84752447720097251462574995003441492768, 139184189717295461790550547383051566405, 170573522324894600358820686443777740485], [140814546149127604666979181709459444295, 6588930470017954392155194646843124173, 188071649827369256639574171611772520613, 116914562968158223902476306582709511890], [276606777137177081423579892384989661458, 164090526530019091786482113891081727145, 256926537736349855182703089421545629989, 142557697836940902518360345029782549324], [243715507272563099011844808025114378989, 250403708928498619786512596024018798736, 250343559585529514740768314160596805374, 111539379040045574280290205097439134607], [24216293486551032932606584620426101684, 167582668241922266777381452876288612950, 31520770066749828567977870625519947768, 218716982619938320860801600633479197551], [128163049836136693876915186668460172588, 96602317122770990141729558218302300828, 36333383838536718586166190558815385076, 131355791823763697096926175636528640496], [100937306664526323695168417977411678300, 92725022122520943777991695880384979965, 156840278421314960568295515883851165585, 11079372989948743797152632737746836892], [156329748680824138999262246948426433316, 69983215317143167876389244424217741808, 44320996723351191720920826893246004119, 8222383271710864774176957904720403667], [202186441543519554618069430384991439205, 80055265264806341497024649989263605422, 134145405384515017720800289341669067211, 210796433739216979816958617886781497954], [116761926044431348918229036036731406744, 122813152529328449548775630393303716699, 15935044091943168967335564175378705271, 150160966914923522815939193160260468058], [168679971056356668440505996938402885184, 163107575351362127939535422256908071969, 55854539114658564014744626872086315735, 59746527433071692428154558281636539420], [106943910662821198816419811825707037658, 69840314901853354586313616138648079209, 99833568664994240438000584039194455570, 162851112306340122350856685689621667741], [111359412282511916404905226369260206298, 191354878874214098793799204215160978004, 52050297274678538005310230851531460934, 180604247092547306072279135092733662290], [14597177161661573416054188572757459752, 81208874742411402694769975189929088751, 173444496445837089902328211302939658278, 209856798814153649810083732631301541538], [20546245091765322526573077446189790105, 112027525949770323620483536698255112648, 135150813410184821452427717671951933698, 226092966816637839105163593590640601022], [263357690182656029021986792905229127366, 274327607499019075347802766507234288638, 277273683596238549189881120964907143156, 104308458624271967952863922321874861216], [114706729644949694633256188167499251662, 134642010658733456604603507320493925185, 126954115145478440165752640245927118828, 42624407194497755256959615620635422861], [156816997769706665304101553970544414312, 108562034374436140540003701778520957758, 14872429674404935647995229232041147546, 159824299238605425836643298920642585172], [217146339859782897813024491491371170158, 75380687565442223739517441964273341606, 118135262733800414212462666437741208919, 101296928843795367039926359011478642844], [196361360154605955946455182968656122482, 95383532800985793925844112594442938271, 23655443933065812510309005764535351133, 138426774784657955515614727525628908034], [111786147417599981645718198497182401092, 150631414948944134714812843565681555511, 234673324986555550719465334236110593518, 161918577635114590687972379880609700538], [91820937069441264995937685097677887405, 103189747416873965024317155818315647277, 40209332792847429562618610027159497126, 175702398390725493790533335885414284937], [233199703240784711467346053782312622391, 81029033344702244057961256821752539080, 63908498942159851061462484693789736726, 251033929600782697048194772018899770914], [123458679229885716534039961513365982976, 29127319178088371702693295356164761921, 97505093046900219990471764856012186667, 94452108757090188571669849401102704877], [63603083491210857746147261563093140494, 208379648602702641013413317674500233107, 171182872362521824053785285788842308153, 213759424841848441035967456508001062269]]
#今年d^3ctf的类似题
from Crypto.Util.number import *
num=41
M=Matrix(ZZ,4*num+1)
C=[]
for i in range(4*num):
M[i,i]=2^4096
P=prod(p[:num])
for i,cc in zip(p[:num],c[:num]):
pp=P//i
temp=pp*ZZ(inverse(pp,i))
for j in cc:
C.append((j*temp %P))
assert len(C)==4*num
for i in range(4*num):
M[i,-1]=C[i]
M[-1,-1]=P
res=M.LLL()
res[0][-1]easymath
这个也挺简单先设$flag=e$。这里可以factor(N-1)是光滑的，那么离散对数是随便解的
然后发现这里面$n_1,l_1$等于-1，-2，其实感觉上面的式子就已经可以解出来了。
exp
from Crypto.Util.number import *
flag=bytes_to_long(b'Neepu{xxx}')
N = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
m = 1391372358062724416224243990838035874507346098208831800403257
n = 3583006200974501742604527103814726194237416368238514877166633691321127310414088215607009332255751700661232767709290883038406749484575415867828156201338536386376279995491732514052716934519151026884616917483040
l = 359786222110993880715372696002813612045630045754565831162281874392294886391569010600976425535545860799388851419768061619942493351122730748490893471593987207207967996028533058621192187630928610989765004439777
c = 1895030805615627998889733471639619972225091175824712353587361803906002039112746104833908879918848049981737808710773335455541140252543329151696420250885361493998408542681830779056032193286985350503581777508964
G=GF(N)
m=G(m)
PR.<x> = PolynomialRing(G)
f=110*x^3+313*x+114-c*x^2
for i in range(len(f.roots())):
temp=G(f.roots()[i][0])
print(long_to_bytes(ZZ(discrete_log(temp,m))))
