2024-江西省第三届天使杯网络安全技能大赛线上预选赛-wp-crypto

写这篇wp是为了记录一个题目，虽然做出来之后发现也不算特别难，但是真挺有意思的。

crypto2

题目：

from sage.all import *
from Crypto.Util.number import *
from secret import flag

t, nbits = 20, 1024
p, q = [getPrime(nbits // 2) for _ in range(2)]
n = p*q
polyeval = lambda poly, x: sum(Zmod(n)(poly[i])*x**i for i in range(len(poly)))

def task(sec: int) -> list:
    def Generator():
        k = randint(2, n-2)
        poly = [randint(2, n-2) for _ in range(t)]
        while True:
            k = polyeval(poly, k)
            yield k

    gen = Generator()
    out = list()
    for _ in range(t+3):
        f = [randint(2, n-2) for _ in range(3)]
        y = ZZ(polyeval(f, sec)*inverse_mod(1337*next(gen)+polyeval(f, 1337), n) % n)
        out.append([f, y])
    return out

sec = randint(2, n-2)
out = task(sec)
enc = sum([flag[i]*pow(sec, i+1, n) for i in range(len(flag))]) % n
print(f"{n = }\n{out = }\n{enc = }")
'''
n = 134244092158335046594573031280335347640814224965165610870079200723228181732816587720772779789970773621774007559909858582214532292338602185755371472186568223669521349923964759893434029395538924868308972596949502001200224966727258928525712271153191978246850586778824974959853826087848206237194363076920374702599
out = [[[109518867113719161922134462457076720623169151950070628749806642766770290543872431292746431300721594062968632443201961746428696045800710596757256474586615570391087858989343253762125977698153411182270492066791793078643140657537917255483475258569906127395907312569498084594621835892474548788539573224342586901160, 45801130570679432049685074489181075717691924893033534207368492788181417854951453729261890191466368799263530078525502255270398443612511277272328973758303735925508741505778216458565906155984800450061956094933467098425274164394192601394090616359870001779160104961448111827397601142810928687779823079981364887315, 101584906031211111469229221943307689840565152794186734381857222635055389646600002660601365756140711501821757436512212605008939707772506781696922074479361856789105023319042731138852863913802226826924200279989336641589573606465726990466423894922009958682124124969460465196843490063615912006002575213962935708757], 46589345151301600111293442779508632039631528839710692531013299171067411927666063226369538551729573253604699328756187844907442809330095178659079286227828621466592747077863484195056149035571849648879213951708329825585989859124699573587613999367893944218309679248660098966667906562056876349081287788760321789955], [[74037223235301069834288165435920594724922189650805942606024677777396462093097852218960420047003827499773716008945273594248977300630155040826872979655515705713371372927929114339363075496471244048098899822213137127545993960464796664452405982013642443366699749960754424288493366511083942615442212810165118414681, 108469889430089011920778854134165850425865203844757498807471704800512529235420516445684346975347312078349118768939609842634977945037962842722637824856366959686946495096537051420258368914446006054686722121045340919122747564708523233009438069361049362649611507222290771551244445964947814393430382817628855291323, 32693607415520397035240957958134292993931256727248456394081934432540017710249707038382177492576756481392083741131589485972813558157905410236491282028388667603797869063156020237618803397816523835325138309691843907818801522398166786004700103926248633756355127087422419514574717398684444180633976635537564725104], 55297980949204408160909058482733132192152656469720361884553633125567207384141302707649035203422880362915174362933928041397778756328101417057714097740998897598850580192825099517147878497481047073927591012099886630058577443268564860088187737292893044374499730780458242967266538150935674542628530947259141392022], [[38376696898104705606425197143717546246094476952618102613672738532670394255616564401119018603736972839909575128111629145758563369580193190543426354469798618473072535725316657911545547962683858754825163958490342793620966834090308134426965947076508963398785817718003526245240957470093752339087204047530423749146, 36745402992604311669682315360672912194089296232645698486647849822337011746994338169451542203505509541090611093167790975596937604680630873151931344434126344739620726558388677828929643115905829420023225382842898187440834884271656175344549264797525915416002959320912991071834097351187568190630245909542724464271, 89443750196208466065528084829746939660280689034993919347771142688586892848217589473191754773409586841870754695582308919249469780995712011538378656418689472965948942423438058244808208030697013433944698779331156991838486780788670878366244185563265082219043408869294560169016188532363263019427063806688936768007], 90630703031301180011738552328330702059511770952180966832613651574957357443073118722480277174064427053145589922449905337655098080350135206868460585866761164762530566370810901500681325207237384064185000684393703138079854457528128182696521396130209078610271705673062256616689584590707001584627052161494542702049], [[104423269193157138679803090679794651222768148166573657733696442097033940400910149767967099902241773860545976148657065107676763800006920174094749371625043118352536610424139580192227746901277948433355146763920220846768907095142935115329554617098683646192697377794849284416308615152751832509665721289892765070387, 26010779655499541245059067049541624983460415163710585383104875863952430913172821032936218028702892952229118732989274577544518109989349869918290933509689451744119615909958814161016547597248986213034880023820420535264624695568711131502756532993749569093802637440939040419533118078591354163446172348055126894626, 116116793431217668644218228350959411394960382455150501813388413922816010626561271548446292031597705176517437360171873019228826911960002370518877101709701232550761549123159730829676322136491880502033993740668346287160651747759262928246913395805673938810215649923939633128959243536171185949654298971420929033018], 47276971911651810790967634814670250686300397165124766224970093776354000085840811451620017418497704551597859788911143399893242844375180336974615822876169609314011035690106033540804973928125743447719066204679850962142686994623169592714803078634084371358017723796454848500158534935844617512613541325855355315275], [[43442966348676003078372546438310713402798803203330124060701737160847742573950414225371205805033579226427422258350252143388680480993526520750039885886582288060180020895682583994979945016269722724679082676020992297125926802633507200664324377794274325880953249601978629548165164433235122437032631922502891206812, 84362939520653970839959825563461862836719188613535147657801797228657486823752581983842764032627095981300624725645652820205625323144577053572156855895197638053648046952372837101003123045539668550793487549928378800485124710291933106057892702268387971213200394298689902524208288660419653729311519433803359650640, 52964128533441073893705664686639165670671255023316853196647027553035041827899457118744436851006392964580134438247660973887222271108974117595093431685948410378424530626393601257973381535134573525556567741314897944080328696787790159196042815099665687607012021608844143103531454256707694488206241772225772997149], 124279931569011917544212307429932784304052201794467840561216642236617517046513330343173394469848333187906507278423026817102535998938044076757967650075769528130263502837008991182854588813666267531873282952061820811706983366478287481212521437002677556715309152603784644463265030351557250044561477211279068389980], [[82292847380278049487108401613984489802161852163099793753418183850993753593849178828096836934929598040502276946597572832194874950265088022154527914063199137279548419230421552953986216092840389242156728688422978612152335461511829766045168148360776300981256565356909267704296453032745263274832414972307881143343, 33129105156012177485619889215615986049994685675739648194291037925303951298793590920990184907144206159525382734933967985934926493562421255002205860671734327327121862774648857658690610528337663192102073603142477749532868131983715199521342648386348813993897613809952279271261417320599304565463868309607022016290, 107476053030802001562809624210214306038344106467747585960034723795783583485771308261110403948418790090650818644621177917021525602694706622053119415043864050154847118443904782124746816255822371298224153731135997889708138913176381051713314532224774998760866260850395682849128886440743025890916870175441315000869], 29154234634886695653746523550566193084296255854156667849583276262018413641192514186956522740468150968409477863273737578562603162404741961410756014138955430833955551049200008287985726997768960108315637066075060150188260920066952474222142236536303716618381326993643124047291503647494759166406673695395079087056], [[83667780747819801205469564743166245677459205340221633206514244326482830326173307613524185381284979609794793732821611940022235942112097959912430171974232135575743411372451159011296341115369779583488192896659448814259892583302169102182012313429980706822613537599440549630763387389760754989348195868469342173380, 94940780471820682121264504845713029628182899490307991280036473965059631631687309590088640219226457047097403787149032791035292530689481940377582770949318251399969298693410419941855033424670484747116147717901550531289284342488894013299674813102472712144513828960651001099353382557891321970577112674466918669694, 8911917008862929116606796143590539987019968570272002461329756452940682335580465693057425913937642869060356531404542402581248917205649287993266942743716929287502170643612922757128722975956081971656094626843718888312832707656829001644529434489025784111720565033929403764284599864711119439298700071006809368871], 95957219623003687272751624548607352617112770137522062990243318332417852703250860834440401334197317564754141632063715504299785469135047583357127452073311721358952210119434177990086280562475976507599350416933446007875485473408936970004139587398568904239670236428513169683506819434149054221422223769737134616029], [[97684327134082168310845410276477721156303676053904617572855069671214834619875515479159821451695497278230941783361581147579315142507076905383978579552189835469899186919243126162812687282734930449635885552975802624743352416604508825728273723242498177132414652862648527809837744425109327622190045453855133371412, 67660301401955788840836044657202374153483609840492133985167293018970202165715845149877268832330491386913878988871743365127909676358666589085754259787901007724867293345774210760856537310807460255151052953964865873933104319450443282241851093154346398376482819870052447251119126022848586898587649104487322883488, 10505934257868020141845760662987185987939495925015827602790964670355964408799743512466216668841687909340012179668266849637593167878024970689381766111903548634413013326863258595631241035185889472607570270597608413021765191705472230195947839669942932306689690182844572159170692985394770743340177975656232518546], 73107125023172143053930896733038761179543957833621336947389992566246501288135905482252815409182712827015062046942616920892838330843339193438908238528003450188395561932095814342693805106495085890879662895817125213241160339195707039807236478761056439366928486845101286085886541223731850753454654043323328950212], [[116640867721915438566496441136426666834146172578896453571421280764426997286964419324478540697173787361015845102031887059951968915141398252060854948572619530819205476727013246262058765717251361343923563328829217547189999530812443946570313383901259765829860171304981051504374731462157404820700620592366318259514, 94432577777432782334253176626045407830709159709525576057623631795952732487825723777027821987369776530733566545676396665039688441204111198945250620162550514222592394197488933357631702135528520268573870050613387272253355774833027501441898012892507945117693505704319657261516764351583508861975856844872212699542, 75400459955406427226604155789905146796340587475345741710401015572678294096002260990207290862895924206491361781604740251245872764127501926069791604360145843654344654040630274870351239857226368962102050707922096785978798793927164818404797246012828809067060549008535605004730418084103382329505280467796327195917], 120173485996822592042735123102887074905838607804535925722241485221664277699802872683832527565615690008294461655904826434542176481314142850936575263704502945310645275512580510218157918373676674610556868915487915030510206510531575578891798909654565350178114243306073868368301867906911217848851255905062575228974], [[107758040565178638961248886292866038871952402804323228974551955178286277744815634097424844691106102006901162741418012112859064378652227557930015926615006424818650635170274430267702216688370030948882861913460734688279725603251771727947365243284855974677293210352612840961073868372278678893652244712328208574969, 72705721979041436836931636236257584449654610775236441041927836342411126244436027312387385675198499184680509766466095468837097736446466545691096041386775667374821695411965870511631027958342650096717759274008250501166419608806290858452161052776075762961755041822518492237980440713510576982459454416035699437099, 52931811385354706652600546065181068959459756427701435779638492223658131739689593932581122982481396293936447743371805069393931803375935991674747197595300172493458907913465142763987039709710148785067591734290341969224745426869325397437168002637361296623693083493516184054242891894956900952934969509606918400592], 78842189497158869208796042214333597320383330372904087446011393650083782978269924582606544924258119580350309325022210689626017020758960395760455539483257183951268880855606010767090294500414695777775099219872542489325093173735486503797246001666216856205175591060583423936372227613105554266301253358887230608142], [[88007739172562671436543585355733003991213598384081315847472751277356824441180015516242158539363704006237076961584593932756884190263699422264394287281702355671965924147644037177605150743873578997379257297455353150764070666108806376094597736722615844833989020240576138321185562975624932999968175964584936180147, 75564799403860301584136685396361154709098759962404727608252393456264596991743048475544947624278965481553307607159451884907353406437873559304262938285278565622726961431632729658433055667514021703660064659833342845515207777946389538333596459723728352067299555413032757159973184937940298090040821549183720008317, 119974179220806153928582192102744530354289353862630644219395586210304691997782688075057934243003882693995451180536696656762151482619554061381275760401894557699612745869705655866477555798125808648109579863827533496649455500872457819130210805159186770993356850566205416207150991142260628663411160049541047001777], 21699765364926132873014517098773625656679846102387494865555313201426918355403620941467153878890414096702056915536656621398505590231789270531779906190812163829632358072327165945581089777216601304204860430364296088828455315783848347303188410016883629469372656537939630781062338008253607796635890516774249183942], [[77154587929512061782499838316443422735837813458066027705016696492886186902594881640719357633004823069861344281186987390339273186427858736363108674229759721728552184848896559459126700095004170759477845763729054787866989865226824469266427245017853324392422090352949902555029533941042860861337712066955857621580, 65592259589191923641156705534368617515831985208298150094587483254969717613175610515781394588539621146413621822684222040778630325799801155055792899106039347314292308593377198635315838930250124550325909200457196631182505314474643768887935955851209043113065502914538420971653409878142136426846053477906064897083, 48266042281062412061210448706877856789671853140372310932296200161572563349472668348514397746705508376753550668418709751009317443109305660468596190022952539106049492135999432940255942442837260972580908055398652023788993419732461311737306775635505811301347510177748476403752676708790629553886922301161715828064], 20871643467401252478785109060645674000841899091193643057847046894042538201258786720649032455996039121382417633328690404819939833585331271959512109330563639667736943868395399188114364008457011452222778472528945863876072168137476122048374499729650434211576012101622963763433800489822157337355742510069393613838], [[32030913227940874645947638682430480891091397856414430195708317196167880534351734738246152789789059523572305616221034808828358190922408676403533989392839704793481149757989905131265656438320662135654760683878529744940020039597056656278123548492187937739962781138917946005506809122861837200546231179185905737681, 59368329649997977616457862040069375585985048901938735148975496939285731901390958744726202558599821571489907006039962844160322531990408195413632988471159173182893520877697727057753514659315270792200282628316155149697635385296980478184069439303044053707734642154966915237627719084496580884315870598961010608853, 61535737524846979750167502011072246503057070565853388743821211561408617981724919729715382378511267319270361278311606982634174216389315946195938221843209210519339095956302551818633339770919299974702833523921029911858497404197404681955211459059698150048840538526797482043085625299690364576227151773297877921254], 20857465440072309609723156170846662184514967453081044828559597685190863893125401618796381822057048527948306252272099294048874935670026887256487722786512729696318017074742293929009129534735030910711142009830969425183276934030962444094390983713644985317275584999458276023865615692997916748106002424935436934193], [[34415051479629174515386611287380178064475237255493873255103742559979824066807953965005586236063453811884379909496035568819603634856439058763193766955424424038522500404494483560446318516860860053090200604622886649019780986788053735702512863674097927696381757466908126870302213727474159032431237859857321957917, 6043070250706712996375684964335689539177080051200060122198088348796628739405806150654421141599303109705330762851886135858288291687251165410804952599505182057536567998300456873351423371580939318797342832481491976389752477237702963398815144620105530132949227264138440529489245510888863683524458497665387028552, 24610001652861939736052943858761200981280712369908387096442335625933641648068351108482581590987111722671446991879337889953738290945715718625895979817134537425437849815977442318251684244037883294953976300267709353914057813487102601218698228698466566459955651147278759504575631520148864577246653539343872999094], 61166350677417847963511602871770558612555258601088345670188118051857453618838424836669642063013635388209989948466567163979646837846673437233838843660606538127881798085274427332008857538588222065834363959077059380405720478097873104856735929900585948946029762443225698504297282180882868435205734579677504284847], [[133965835473313349205695882878801697323333445489043766216335417215105477128003125718775047498019914167045154230735912491621523686409687924582987185740681950541312681040640094327622795329958075425997822475866376444342840010376336257736416336899033965538015137588555982590743466810376343030519879749554451299047, 57161250910509891509367169817993904494878880657948491540587985954962989898126102472549065099604861815858888214602989671149205699990805834959019262984263782710480900347512265472799408926002261857734168768518178529645964435563813017654239202471082241871886360731342550765218029794841327160051615646638469797624, 18212584209567115750966116149957774774942768707552662512157491599832281681422910822746371867488881729978650357244207648220769164878563956706379673311265902941257835875668965757801087915267258640185276864595329352568327403333186662521961763444815249182230267047753058679861409869296584869211807805658988219464], 45055515130387148770236243226343704988685000056139059260385838055655375871395550302263675557387301293240955173152283066138699638123955706888280767180577155265153207899681042039429681066732578165628687463595671784993692518839424179594805764755351790134502622297792147214924723988401368895804249464406902619452], [[20074258815242038201226670832101394145540921188047178949984324591446755194041594782105325917715523581756348227903537898000830384640301371619016680150049297982925091800352431368588804084478199312576279637184231530027472128507443142169431299693686168674356639971161442354308671061299305326058350311163505063382, 131835726929561151140316614833563007760752025447737788794451171806553086766140001283448942793677193547837590229414064034071970590970149772838435387168048119150852200332883934723997111157962304888654640149319584941272396582254265405477839501718338508374758294643529688551572162670632801226201494157099672539027, 118327133579540596749005063765322706200565095282080402692529854894459750393659827938880675238158388539514464323062271604507292816673357210831031377353189436792009021647271330987286351400316350529995415085693606107341355601035091798268644670387330550629825755282041416037108720107716123231761467539723996237293], 121436790205719452783314797397253968409010753965816156718520962108445626466819767129125782777946367936704340105790122915793588713563970716781587417561493385210556852117396249589227036380938234856411832110952349170318097147822745761634824974578247679233863528129313518734398165682426773223020338745880225658775], [[71404375119124883738529258019940312427816127477468070904348002772534382584026907924493628756843232431813795406514485248604190380452412895693144966096815662159808227406503087362725905168337823329173366409195383508499751063558610889520426243002407715020656745189380489620083803672971649443916887656905342231949, 71404501022746191641499882941129414753591997044137400605314614899744424172095962415174251609209435297467787746397370663201928199154572830202519513080699936668131957353223213185944538796268859002599587761566868149482924115063217260946425534997480153801910444421069294433682755677645056283696047197769186863092, 42712427067358413745295021613192257893500736518762624574168755105524617363101473059382184741840279947283825035875174122384790861685062589129947171184183332281561691273738910026368141474029989203278588879536405741819641439318940610526843363433306672185474799003558280223344250820266817687458008810604126839226], 22578776845094394365381370028616129262605094924868959752076175562936679002732397774973215934138516991749694336530170739764616202905552893792091476628351348643246305752303197468870083266453455600201259814359154122847571745843377407651432695104765988638227337754376693099940905640269683876849480893682748669459], [[76173673319341148763367248399036291626206160225842605564954455723236744147157927904994436423261865771848277867673951859836261608937548414579817134062725094669085161043193974260326711378903572114327428157991685128065730478218644317730914991667713278058312210343307263884911032020870111346317316625987881502470, 131165517102581316498152514780135767139932387136931201693432888419910126474544916475538938914094314079551396484174749663815056556586300163085202745230163834937435342020954396192302551168595526188911825109247771098098691117045536920115008726238769484430043312698335292507373041578790596033456485865606212653006, 26725311574730657189050358163112525954946562659578497730780341397661725750393104531140366814086890948080522088180787505106696392019691301809340870470949338595924910835690762919357050156317229692341304464195714139148765069163087686823890676874681008147969940974549414071007095478805709194280002825348827712969], 131645225584614307547525160689924905487932902013219697723147071483464029755491530839150260971648085234473370588942067453902250052928726730760128034660128931186244949268345545840129280501213339066761801523906750500453679682955701341463051356650403015053454076071255020655421557644525557919947449868953461253783], [[27437872504631415634910456217993896795966254156563366585278067596826075585355930810870612142018589827560288294461822300857621305479562124865670752830204858260584792292953586605702709979791275240468622210832287672822384142978477942117049346584458933821982745936126779531916870363060656639144254755108616827850, 49841815245476560064166415625590229382378384456395822569965849794134573546021861040387186669547551654530752026754401207790405224664099698156156561505688981626107191989255378757935563827731193982693695359576306008734183148277484584028152826820711073791633841700748459726906752085995761772462251233607057333802, 108375482744848261372317434901037766678181122775052050311354526438851078940781028882482253756911076002015903771249224516132767032445501662304604939142938269768953307352998308415232477813009345072988171477528858085382158096172599945415129484673185929271515341501532356578389243001639372381636961994468796770707], 61395102632239083484504726167366480534468603555364023608078872219819805291764352149058391066636448656681223742767666238684930265537583240970048885928932840834096339478644284075592388596484170836326105957785190699505372543564143808603142392816667498274140974250850306390305627026443469251689674379781790958567], [[10609570863065575780821890012334653801913798838322112671550662476486732649540015631078774895925927952037225723488009527828622063927534023118820506797517922812088838664372258763293901534968310228394018463107132515728240047925387548339281990453580120339070086053905169595252641458403856265389765065952090074333, 103444199818680248634364660257581830971021418173449878535237457681418487181985115447703447378996668374031745158127115823494568130591127990218054083017702330846305563437157924683757479537507781049970162797330550816946397745603826586270812159497568997233373627650354871404378102744192658453194602836100330972058, 96423061962217628304833826414324825245197730371393933326814069575476723513941021403416806723608062332613915443088893033395545725530880954689621874773250324611359253045180106954479341285264370598001046479677635293555849175879748297478192089927716143844622898784235701344498260016750530002463148082834107688243], 66734295900575868347096012271184729871830037658954515588515076327921004930800659066428248596964195907511020879010157544475932898130109351709103421391383578893193574696402547604591328159171106820088551934795707779333573236237541200818233614410805787050154632148300193701271293017437642938897263253672060790539], [[132779651437769126678641739926412364695323940354902978803028688225358651160467218606365218438487203499188406326608282478718677926694443084790973655240791572416555306259131060031308820090158148013130420245178202035563087834281605922730760191538290152826169504270279096303628783118163023808732404514847357163431, 72890444702328751361939762173049549740339458421494979057908767422910673892690809409218528061353199000726923934345570818786813466321024899403270263860765546022110565117248894347457683282266471549761622680094532172717150549993340788951153134669973370898601753309232897501837814399078322174432563443030478723713, 128440369875589306952948698140181219977135329127036906402063859395646980385051210420635242905750156443244842579071511073889655644170347134163251208392436750175400084540454165573311716693371505845618716857372084571247443345530397976967775051536639158205175836289123014632993589154211784670273197140652960246533], 95172869507741231065382541211066913509407087719157599853105489885709989716885952945355866415678686085117462030201875556256461335293558667578885386798040716003504670387342555169203177619392161625642160497146472371166344123691986877357282553309550827059925899662013372976272216917946344277405160319808217123582], [[62935387574373724877075280876778664419571538053686633467370407725216357768483187357006985416602577659962222264224046243860302365687364567308876845047838671589409787627552806431185453611764476906839763482744821132330705311249393958604608405765828598324865773561660502272693321837724856585066420129352831308187, 66183984413544372251198217464156825514019412676512195065694138714041188999138783127552959655756101025829656368680650027837033587735573209786757717244248014780503277090549052812918871440145968632007711229680389753238599365761311931525967295342151440143004951072948020128000876471262799540138624414481138380744, 7107988831489313234252200245611001861914677760911083460936195327328892539383195062569036005401322478192041598556847763686985590981339465568681877416487978081510664891620656075041540574984361465979328586045364140238268342641058890067655666820121389178653802745337291743043625332342455034223525545715103699759], 51466151662224664405232285191034349679215973289844647654979945760494611632809273932624234265920236498020046911509706550374643394466403117407803559840468409490990589556758084801702184544450378530485657634405405694442988665194093217669741371707090519476562845553189336822185727048325161005675939574583319427300], [[83404771755717587543185672079708980477385730295342500639536239251266897195653860852158688557668135895201483736953415417814611874746522565742595348977953641334036013159058333513376232845490235828555385331362557721865625899922583592498790491028674150893942026391326659785793330699040111249032501379393017932332, 44377758379211273518173218747390419724969265787357427867406043477897294746966530283414986270552425835014581126024422113101042869436316863056085697589859801901654316393226629156087358232819943612066499465757605893758597983072018392149443488945231047349700959325118002038552662442629644678924263962339666955059, 102413361995552877335418353531040829574676181855883758839461103487602625265124617539641603795476529086136912183227988663217327604338488852103153683607800691769812732492586810592865491035051561536817297136288453561500528395998168165335248796130533335135266054228763827717577556589789558248164374562975302634096], 715167925936859257105030541332421018011771562437589343468681221179796421506875764942924912525155342121246446378251737324282521093600808758466352609530523062530557978827559269075319814198898025681567750699039278288624794536239506904997900339100580851478130693196911373003070024306231028911057928015308199174]]
enc = 110879468774054646611853514338753094691271633780346258691087137907834914373684531593216132616273580229844385901066493617366286725266379984340209631131102400401979638003074808631783672650352444881692959176739232939251869912795562628895096755457730901751313813611100868566602786679857800494548137703677838041788
'''

题目基于多项式，加密流程如下：

随机生成512bit的大素数p、q，并求其乘积为n
随机生成小于n的整数sec，并进入task
进入task之后，会初始化一个generator，其中包含：
- 一个初始种子k
- 一个长为20的系数列表poly（等价于一个度为19的多项式，记这个多项式为h）
- 每次调用generator会迭代生成新的数字，迭代方式为：
  $k = h(k)$
进行23轮加密，每次加密的流程为：
- 随机生成一个度为2的多项式f
- 按如下方式计算出y：
  $k = h(k)$ $y = f(sec) \cdot [1337k + f(1337)]^{-1} \quad(mod\;n)$
- 将本次的f、y添加到out中

生成完out后，最后一步是：

1	enc = sum([flag[i]*pow(sec, i+1, n) for i in range(len(flag))]) % n

给出n、out、enc，要求还原flag。

很显然最后一步是用sec的幂次做了个背包，只需要LLL就可以拿到flag的每个字符。因此核心问题在于如何利用out得到sec的值。

再回顾一下23轮加密的式子：

$y_i = f_i(sec) \cdot [1337k_i + f_i(1337)]^{-1} \quad(mod\;n)$

有逆元的存在肯定是不太理想的，所以先移项整理一下：

$y_i[1337k_i + f_i(1337)] - f_i(sec) = 0 \quad(mod\;n)$

我们有23组fi和yi，而我们未知的变量有：

sec
h的20个系数
种子k

一共是22个，看上去方程比变量多，似乎可以groebner。

然而实际上测试一下，可以发现说即使是每两组相邻式子之间建立多项式（这样可以控制多项式的度在40以内），次数也仍然不低，并且变量也实在太多了，所以groebner估计一年也做不出来。

这个时候换一换思路，对上面的式子继续变形，把k单独露出来：

$k_i = [f_i(sec) \cdot y_i^{-1} - f_i(1337)] \cdot 1337^{-1} \quad(mod\;n)$

不妨取前两组式子出来观察：

$k_0 = [f_0(sec) \cdot y_0^{-1} - f_0(1337)] \cdot 1337^{-1} \quad(mod\;n)$ $k_1 = [f_1(sec) \cdot y_1^{-1} - f_1(1337)] \cdot 1337^{-1} \quad(mod\;n)$

而等式右边其实都是关于sec的二次多项式，也就是我们可以写为：

$k_0 = g_0(sec) \quad(mod\;n)$ $k_1 = g_1(sec) \quad(mod\;n)$

其中g的具体形式我们是知道的。再来，我们又有：

$h(k_0) = k_1$

那么代入回去也就是：

$h(g_0(sec)) = g_1(sec) \quad(mod\;n)$

所以我们其实拥有了22组如下等式，其实也就是多项式h的点对：

$h(g_i(sec)) = g_{i+1}(sec) \quad(mod\;n)$

而h是一个所有系数我们都不知道的19次多项式：

$h = h_0 + h_1x + h_2x^2 + ... + h_{19}x^{19}$

求解多项式系数的一个有力手段是插值，因此要往那上面靠才行。而这题目与普通插值的区别在于：我们拥有的22组点对并不是普通意义下的数值对：

$y = h(x)$

而是22组函数点对：

$g_{i+1}(x) = h(g_i(x))$

回顾一下普通插值的方法，我们其实是用多组数值点对$(x_i,y_i)$，去构造了如下的矩阵方程：

$\left( \begin{matrix} 1&x_0&x_0^2&\cdots&x_0^{19}\\ 1&x_1&x_1^2&\cdots&x_1^{19}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_{18}&x_{18}^2&\cdots&x_{18}^{19}\\ 1&x_{19}&x_{19}^2&\cdots&x_{19}^{19}\\ \end{matrix} \right) \left( \begin{matrix} h_0\\ h_1\\ \vdots\\ h_{18}\\ h_{19}\\ \end{matrix} \right) = \left( \begin{matrix} y_0\\ y_1\\ \vdots\\ y_{18}\\ y_{19}\\ \end{matrix} \right)$

然后解这个矩阵方程就可以得到h的全部系数了。

类似的，我们可以对这个题目的函数点对如法炮制一个矩阵方程，也就是：

$\left( \begin{matrix} 1&g_0(x)&g_0(x)^2&\cdots&g_0(x)^{19}\\ 1&g_1(x)&g_1(x)^2&\cdots&g_1(x)^{19}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&g_{18}(x)&g_{18}(x)^2&\cdots&g_{18}(x)^{19}\\ 1&g_{19}(x)&g_{19}(x)^2&\cdots&g_{19}(x)^{19}\\ \end{matrix} \right) \left( \begin{matrix} h_0\\ h_1\\ \vdots\\ h_{18}\\ h_{19}\\ \end{matrix} \right) = \left( \begin{matrix} g_{1}(x)\\ g_{2}(x)\\ \vdots\\ g_{19}(x)\\ g_{20}(x)\\ \end{matrix} \right)$

然而问题在于，矩阵和向量都是带x的，没法直接解这个矩阵方程，那怎么办呢？

我们再多取一组数据，使得：

$\left( \begin{matrix} 1&g_0(x)&g_0(x)^2&\cdots&g_0(x)^{19}\\ 1&g_1(x)&g_1(x)^2&\cdots&g_1(x)^{19}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&g_{19}(x)&g_{19}(x)^2&\cdots&g_{19}(x)^{19}\\ 1&g_{20}(x)&g_{20}(x)^2&\cdots&g_{20}(x)^{19}\\ \end{matrix} \right) _{21,20} \left( \begin{matrix} h_0\\ h_1\\ \vdots\\ h_{18}\\ h_{19}\\ \end{matrix} \right) _{20,1} = \left( \begin{matrix} g_{1}(x)\\ g_{2}(x)\\ \vdots\\ g_{20}(x)\\ g_{21}(x)\\ \end{matrix} \right) _{21,1}$

多取一组有什么用呢？我们知道，这个矩阵方程一定是有解的，他的解就是：

x为sec
hi为h的各项系数

而这是个非齐次的矩阵方程，他有解的充要条件是系数矩阵的秩等于增广矩阵的秩，而系数矩阵的秩无论如何都小于等于列数20，这其实说明一点：

$L_1 = \left( \begin{matrix} 1&g_0(x)&g_0(x)^2&\cdots&g_0(x)^{19}&g_{1}(x)\\ 1&g_1(x)&g_1(x)^2&\cdots&g_1(x)^{19}&g_{2}(x)\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 1&g_{19}(x)&g_{19}(x)^2&\cdots&g_{19}(x)^{19}&g_{20}(x)\\ 1&g_{20}(x)&g_{20}(x)^2&\cdots&g_{20}(x)^{19}&g_{21}(x)\\ \end{matrix} \right) _{21,21}$

也就是这个增广矩阵的秩小于等于20。

而增广矩阵的维数是21x21，那么它的秩小于等于20代表着这个增广矩阵是不满秩的，也就是这个增广矩阵的行列式为0。又因为这个增广矩阵的行列式显然是一个x的多项式，我们不妨记为：

$F_1(x) = det(L_1)$

我们就得到了一个以sec为根的多项式，同理，我们再向后取一个矩阵，就可以得到：

$F_2(x) = det(L_2)$

现在我们就拥有了两个以sec为根的多项式F1、F2，因此求他们的gcd就可以得到sec了，得到sec之后简单爆破一下flag的长度做个背包就可以得到完整flag。

exp：

from Crypto.Util.number import *
from tqdm import *

polyeval = lambda poly, x: sum(Zmod(n)(poly[i])*x**i for i in range(len(poly)))
n = 134244092158335046594573031280335347640814224965165610870079200723228181732816587720772779789970773621774007559909858582214532292338602185755371472186568223669521349923964759893434029395538924868308972596949502001200224966727258928525712271153191978246850586778824974959853826087848206237194363076920374702599
out = [[[109518867113719161922134462457076720623169151950070628749806642766770290543872431292746431300721594062968632443201961746428696045800710596757256474586615570391087858989343253762125977698153411182270492066791793078643140657537917255483475258569906127395907312569498084594621835892474548788539573224342586901160, 45801130570679432049685074489181075717691924893033534207368492788181417854951453729261890191466368799263530078525502255270398443612511277272328973758303735925508741505778216458565906155984800450061956094933467098425274164394192601394090616359870001779160104961448111827397601142810928687779823079981364887315, 101584906031211111469229221943307689840565152794186734381857222635055389646600002660601365756140711501821757436512212605008939707772506781696922074479361856789105023319042731138852863913802226826924200279989336641589573606465726990466423894922009958682124124969460465196843490063615912006002575213962935708757], 46589345151301600111293442779508632039631528839710692531013299171067411927666063226369538551729573253604699328756187844907442809330095178659079286227828621466592747077863484195056149035571849648879213951708329825585989859124699573587613999367893944218309679248660098966667906562056876349081287788760321789955], [[74037223235301069834288165435920594724922189650805942606024677777396462093097852218960420047003827499773716008945273594248977300630155040826872979655515705713371372927929114339363075496471244048098899822213137127545993960464796664452405982013642443366699749960754424288493366511083942615442212810165118414681, 108469889430089011920778854134165850425865203844757498807471704800512529235420516445684346975347312078349118768939609842634977945037962842722637824856366959686946495096537051420258368914446006054686722121045340919122747564708523233009438069361049362649611507222290771551244445964947814393430382817628855291323, 32693607415520397035240957958134292993931256727248456394081934432540017710249707038382177492576756481392083741131589485972813558157905410236491282028388667603797869063156020237618803397816523835325138309691843907818801522398166786004700103926248633756355127087422419514574717398684444180633976635537564725104], 55297980949204408160909058482733132192152656469720361884553633125567207384141302707649035203422880362915174362933928041397778756328101417057714097740998897598850580192825099517147878497481047073927591012099886630058577443268564860088187737292893044374499730780458242967266538150935674542628530947259141392022], [[38376696898104705606425197143717546246094476952618102613672738532670394255616564401119018603736972839909575128111629145758563369580193190543426354469798618473072535725316657911545547962683858754825163958490342793620966834090308134426965947076508963398785817718003526245240957470093752339087204047530423749146, 36745402992604311669682315360672912194089296232645698486647849822337011746994338169451542203505509541090611093167790975596937604680630873151931344434126344739620726558388677828929643115905829420023225382842898187440834884271656175344549264797525915416002959320912991071834097351187568190630245909542724464271, 89443750196208466065528084829746939660280689034993919347771142688586892848217589473191754773409586841870754695582308919249469780995712011538378656418689472965948942423438058244808208030697013433944698779331156991838486780788670878366244185563265082219043408869294560169016188532363263019427063806688936768007], 90630703031301180011738552328330702059511770952180966832613651574957357443073118722480277174064427053145589922449905337655098080350135206868460585866761164762530566370810901500681325207237384064185000684393703138079854457528128182696521396130209078610271705673062256616689584590707001584627052161494542702049], [[104423269193157138679803090679794651222768148166573657733696442097033940400910149767967099902241773860545976148657065107676763800006920174094749371625043118352536610424139580192227746901277948433355146763920220846768907095142935115329554617098683646192697377794849284416308615152751832509665721289892765070387, 26010779655499541245059067049541624983460415163710585383104875863952430913172821032936218028702892952229118732989274577544518109989349869918290933509689451744119615909958814161016547597248986213034880023820420535264624695568711131502756532993749569093802637440939040419533118078591354163446172348055126894626, 116116793431217668644218228350959411394960382455150501813388413922816010626561271548446292031597705176517437360171873019228826911960002370518877101709701232550761549123159730829676322136491880502033993740668346287160651747759262928246913395805673938810215649923939633128959243536171185949654298971420929033018], 47276971911651810790967634814670250686300397165124766224970093776354000085840811451620017418497704551597859788911143399893242844375180336974615822876169609314011035690106033540804973928125743447719066204679850962142686994623169592714803078634084371358017723796454848500158534935844617512613541325855355315275], [[43442966348676003078372546438310713402798803203330124060701737160847742573950414225371205805033579226427422258350252143388680480993526520750039885886582288060180020895682583994979945016269722724679082676020992297125926802633507200664324377794274325880953249601978629548165164433235122437032631922502891206812, 84362939520653970839959825563461862836719188613535147657801797228657486823752581983842764032627095981300624725645652820205625323144577053572156855895197638053648046952372837101003123045539668550793487549928378800485124710291933106057892702268387971213200394298689902524208288660419653729311519433803359650640, 52964128533441073893705664686639165670671255023316853196647027553035041827899457118744436851006392964580134438247660973887222271108974117595093431685948410378424530626393601257973381535134573525556567741314897944080328696787790159196042815099665687607012021608844143103531454256707694488206241772225772997149], 124279931569011917544212307429932784304052201794467840561216642236617517046513330343173394469848333187906507278423026817102535998938044076757967650075769528130263502837008991182854588813666267531873282952061820811706983366478287481212521437002677556715309152603784644463265030351557250044561477211279068389980], [[82292847380278049487108401613984489802161852163099793753418183850993753593849178828096836934929598040502276946597572832194874950265088022154527914063199137279548419230421552953986216092840389242156728688422978612152335461511829766045168148360776300981256565356909267704296453032745263274832414972307881143343, 33129105156012177485619889215615986049994685675739648194291037925303951298793590920990184907144206159525382734933967985934926493562421255002205860671734327327121862774648857658690610528337663192102073603142477749532868131983715199521342648386348813993897613809952279271261417320599304565463868309607022016290, 107476053030802001562809624210214306038344106467747585960034723795783583485771308261110403948418790090650818644621177917021525602694706622053119415043864050154847118443904782124746816255822371298224153731135997889708138913176381051713314532224774998760866260850395682849128886440743025890916870175441315000869], 29154234634886695653746523550566193084296255854156667849583276262018413641192514186956522740468150968409477863273737578562603162404741961410756014138955430833955551049200008287985726997768960108315637066075060150188260920066952474222142236536303716618381326993643124047291503647494759166406673695395079087056], [[83667780747819801205469564743166245677459205340221633206514244326482830326173307613524185381284979609794793732821611940022235942112097959912430171974232135575743411372451159011296341115369779583488192896659448814259892583302169102182012313429980706822613537599440549630763387389760754989348195868469342173380, 94940780471820682121264504845713029628182899490307991280036473965059631631687309590088640219226457047097403787149032791035292530689481940377582770949318251399969298693410419941855033424670484747116147717901550531289284342488894013299674813102472712144513828960651001099353382557891321970577112674466918669694, 8911917008862929116606796143590539987019968570272002461329756452940682335580465693057425913937642869060356531404542402581248917205649287993266942743716929287502170643612922757128722975956081971656094626843718888312832707656829001644529434489025784111720565033929403764284599864711119439298700071006809368871], 95957219623003687272751624548607352617112770137522062990243318332417852703250860834440401334197317564754141632063715504299785469135047583357127452073311721358952210119434177990086280562475976507599350416933446007875485473408936970004139587398568904239670236428513169683506819434149054221422223769737134616029], [[97684327134082168310845410276477721156303676053904617572855069671214834619875515479159821451695497278230941783361581147579315142507076905383978579552189835469899186919243126162812687282734930449635885552975802624743352416604508825728273723242498177132414652862648527809837744425109327622190045453855133371412, 67660301401955788840836044657202374153483609840492133985167293018970202165715845149877268832330491386913878988871743365127909676358666589085754259787901007724867293345774210760856537310807460255151052953964865873933104319450443282241851093154346398376482819870052447251119126022848586898587649104487322883488, 10505934257868020141845760662987185987939495925015827602790964670355964408799743512466216668841687909340012179668266849637593167878024970689381766111903548634413013326863258595631241035185889472607570270597608413021765191705472230195947839669942932306689690182844572159170692985394770743340177975656232518546], 73107125023172143053930896733038761179543957833621336947389992566246501288135905482252815409182712827015062046942616920892838330843339193438908238528003450188395561932095814342693805106495085890879662895817125213241160339195707039807236478761056439366928486845101286085886541223731850753454654043323328950212], [[116640867721915438566496441136426666834146172578896453571421280764426997286964419324478540697173787361015845102031887059951968915141398252060854948572619530819205476727013246262058765717251361343923563328829217547189999530812443946570313383901259765829860171304981051504374731462157404820700620592366318259514, 94432577777432782334253176626045407830709159709525576057623631795952732487825723777027821987369776530733566545676396665039688441204111198945250620162550514222592394197488933357631702135528520268573870050613387272253355774833027501441898012892507945117693505704319657261516764351583508861975856844872212699542, 75400459955406427226604155789905146796340587475345741710401015572678294096002260990207290862895924206491361781604740251245872764127501926069791604360145843654344654040630274870351239857226368962102050707922096785978798793927164818404797246012828809067060549008535605004730418084103382329505280467796327195917], 120173485996822592042735123102887074905838607804535925722241485221664277699802872683832527565615690008294461655904826434542176481314142850936575263704502945310645275512580510218157918373676674610556868915487915030510206510531575578891798909654565350178114243306073868368301867906911217848851255905062575228974], [[107758040565178638961248886292866038871952402804323228974551955178286277744815634097424844691106102006901162741418012112859064378652227557930015926615006424818650635170274430267702216688370030948882861913460734688279725603251771727947365243284855974677293210352612840961073868372278678893652244712328208574969, 72705721979041436836931636236257584449654610775236441041927836342411126244436027312387385675198499184680509766466095468837097736446466545691096041386775667374821695411965870511631027958342650096717759274008250501166419608806290858452161052776075762961755041822518492237980440713510576982459454416035699437099, 52931811385354706652600546065181068959459756427701435779638492223658131739689593932581122982481396293936447743371805069393931803375935991674747197595300172493458907913465142763987039709710148785067591734290341969224745426869325397437168002637361296623693083493516184054242891894956900952934969509606918400592], 78842189497158869208796042214333597320383330372904087446011393650083782978269924582606544924258119580350309325022210689626017020758960395760455539483257183951268880855606010767090294500414695777775099219872542489325093173735486503797246001666216856205175591060583423936372227613105554266301253358887230608142], [[88007739172562671436543585355733003991213598384081315847472751277356824441180015516242158539363704006237076961584593932756884190263699422264394287281702355671965924147644037177605150743873578997379257297455353150764070666108806376094597736722615844833989020240576138321185562975624932999968175964584936180147, 75564799403860301584136685396361154709098759962404727608252393456264596991743048475544947624278965481553307607159451884907353406437873559304262938285278565622726961431632729658433055667514021703660064659833342845515207777946389538333596459723728352067299555413032757159973184937940298090040821549183720008317, 119974179220806153928582192102744530354289353862630644219395586210304691997782688075057934243003882693995451180536696656762151482619554061381275760401894557699612745869705655866477555798125808648109579863827533496649455500872457819130210805159186770993356850566205416207150991142260628663411160049541047001777], 21699765364926132873014517098773625656679846102387494865555313201426918355403620941467153878890414096702056915536656621398505590231789270531779906190812163829632358072327165945581089777216601304204860430364296088828455315783848347303188410016883629469372656537939630781062338008253607796635890516774249183942], [[77154587929512061782499838316443422735837813458066027705016696492886186902594881640719357633004823069861344281186987390339273186427858736363108674229759721728552184848896559459126700095004170759477845763729054787866989865226824469266427245017853324392422090352949902555029533941042860861337712066955857621580, 65592259589191923641156705534368617515831985208298150094587483254969717613175610515781394588539621146413621822684222040778630325799801155055792899106039347314292308593377198635315838930250124550325909200457196631182505314474643768887935955851209043113065502914538420971653409878142136426846053477906064897083, 48266042281062412061210448706877856789671853140372310932296200161572563349472668348514397746705508376753550668418709751009317443109305660468596190022952539106049492135999432940255942442837260972580908055398652023788993419732461311737306775635505811301347510177748476403752676708790629553886922301161715828064], 20871643467401252478785109060645674000841899091193643057847046894042538201258786720649032455996039121382417633328690404819939833585331271959512109330563639667736943868395399188114364008457011452222778472528945863876072168137476122048374499729650434211576012101622963763433800489822157337355742510069393613838], [[32030913227940874645947638682430480891091397856414430195708317196167880534351734738246152789789059523572305616221034808828358190922408676403533989392839704793481149757989905131265656438320662135654760683878529744940020039597056656278123548492187937739962781138917946005506809122861837200546231179185905737681, 59368329649997977616457862040069375585985048901938735148975496939285731901390958744726202558599821571489907006039962844160322531990408195413632988471159173182893520877697727057753514659315270792200282628316155149697635385296980478184069439303044053707734642154966915237627719084496580884315870598961010608853, 61535737524846979750167502011072246503057070565853388743821211561408617981724919729715382378511267319270361278311606982634174216389315946195938221843209210519339095956302551818633339770919299974702833523921029911858497404197404681955211459059698150048840538526797482043085625299690364576227151773297877921254], 20857465440072309609723156170846662184514967453081044828559597685190863893125401618796381822057048527948306252272099294048874935670026887256487722786512729696318017074742293929009129534735030910711142009830969425183276934030962444094390983713644985317275584999458276023865615692997916748106002424935436934193], [[34415051479629174515386611287380178064475237255493873255103742559979824066807953965005586236063453811884379909496035568819603634856439058763193766955424424038522500404494483560446318516860860053090200604622886649019780986788053735702512863674097927696381757466908126870302213727474159032431237859857321957917, 6043070250706712996375684964335689539177080051200060122198088348796628739405806150654421141599303109705330762851886135858288291687251165410804952599505182057536567998300456873351423371580939318797342832481491976389752477237702963398815144620105530132949227264138440529489245510888863683524458497665387028552, 24610001652861939736052943858761200981280712369908387096442335625933641648068351108482581590987111722671446991879337889953738290945715718625895979817134537425437849815977442318251684244037883294953976300267709353914057813487102601218698228698466566459955651147278759504575631520148864577246653539343872999094], 61166350677417847963511602871770558612555258601088345670188118051857453618838424836669642063013635388209989948466567163979646837846673437233838843660606538127881798085274427332008857538588222065834363959077059380405720478097873104856735929900585948946029762443225698504297282180882868435205734579677504284847], [[133965835473313349205695882878801697323333445489043766216335417215105477128003125718775047498019914167045154230735912491621523686409687924582987185740681950541312681040640094327622795329958075425997822475866376444342840010376336257736416336899033965538015137588555982590743466810376343030519879749554451299047, 57161250910509891509367169817993904494878880657948491540587985954962989898126102472549065099604861815858888214602989671149205699990805834959019262984263782710480900347512265472799408926002261857734168768518178529645964435563813017654239202471082241871886360731342550765218029794841327160051615646638469797624, 18212584209567115750966116149957774774942768707552662512157491599832281681422910822746371867488881729978650357244207648220769164878563956706379673311265902941257835875668965757801087915267258640185276864595329352568327403333186662521961763444815249182230267047753058679861409869296584869211807805658988219464], 45055515130387148770236243226343704988685000056139059260385838055655375871395550302263675557387301293240955173152283066138699638123955706888280767180577155265153207899681042039429681066732578165628687463595671784993692518839424179594805764755351790134502622297792147214924723988401368895804249464406902619452], [[20074258815242038201226670832101394145540921188047178949984324591446755194041594782105325917715523581756348227903537898000830384640301371619016680150049297982925091800352431368588804084478199312576279637184231530027472128507443142169431299693686168674356639971161442354308671061299305326058350311163505063382, 131835726929561151140316614833563007760752025447737788794451171806553086766140001283448942793677193547837590229414064034071970590970149772838435387168048119150852200332883934723997111157962304888654640149319584941272396582254265405477839501718338508374758294643529688551572162670632801226201494157099672539027, 118327133579540596749005063765322706200565095282080402692529854894459750393659827938880675238158388539514464323062271604507292816673357210831031377353189436792009021647271330987286351400316350529995415085693606107341355601035091798268644670387330550629825755282041416037108720107716123231761467539723996237293], 121436790205719452783314797397253968409010753965816156718520962108445626466819767129125782777946367936704340105790122915793588713563970716781587417561493385210556852117396249589227036380938234856411832110952349170318097147822745761634824974578247679233863528129313518734398165682426773223020338745880225658775], [[71404375119124883738529258019940312427816127477468070904348002772534382584026907924493628756843232431813795406514485248604190380452412895693144966096815662159808227406503087362725905168337823329173366409195383508499751063558610889520426243002407715020656745189380489620083803672971649443916887656905342231949, 71404501022746191641499882941129414753591997044137400605314614899744424172095962415174251609209435297467787746397370663201928199154572830202519513080699936668131957353223213185944538796268859002599587761566868149482924115063217260946425534997480153801910444421069294433682755677645056283696047197769186863092, 42712427067358413745295021613192257893500736518762624574168755105524617363101473059382184741840279947283825035875174122384790861685062589129947171184183332281561691273738910026368141474029989203278588879536405741819641439318940610526843363433306672185474799003558280223344250820266817687458008810604126839226], 22578776845094394365381370028616129262605094924868959752076175562936679002732397774973215934138516991749694336530170739764616202905552893792091476628351348643246305752303197468870083266453455600201259814359154122847571745843377407651432695104765988638227337754376693099940905640269683876849480893682748669459], [[76173673319341148763367248399036291626206160225842605564954455723236744147157927904994436423261865771848277867673951859836261608937548414579817134062725094669085161043193974260326711378903572114327428157991685128065730478218644317730914991667713278058312210343307263884911032020870111346317316625987881502470, 131165517102581316498152514780135767139932387136931201693432888419910126474544916475538938914094314079551396484174749663815056556586300163085202745230163834937435342020954396192302551168595526188911825109247771098098691117045536920115008726238769484430043312698335292507373041578790596033456485865606212653006, 26725311574730657189050358163112525954946562659578497730780341397661725750393104531140366814086890948080522088180787505106696392019691301809340870470949338595924910835690762919357050156317229692341304464195714139148765069163087686823890676874681008147969940974549414071007095478805709194280002825348827712969], 131645225584614307547525160689924905487932902013219697723147071483464029755491530839150260971648085234473370588942067453902250052928726730760128034660128931186244949268345545840129280501213339066761801523906750500453679682955701341463051356650403015053454076071255020655421557644525557919947449868953461253783], [[27437872504631415634910456217993896795966254156563366585278067596826075585355930810870612142018589827560288294461822300857621305479562124865670752830204858260584792292953586605702709979791275240468622210832287672822384142978477942117049346584458933821982745936126779531916870363060656639144254755108616827850, 49841815245476560064166415625590229382378384456395822569965849794134573546021861040387186669547551654530752026754401207790405224664099698156156561505688981626107191989255378757935563827731193982693695359576306008734183148277484584028152826820711073791633841700748459726906752085995761772462251233607057333802, 108375482744848261372317434901037766678181122775052050311354526438851078940781028882482253756911076002015903771249224516132767032445501662304604939142938269768953307352998308415232477813009345072988171477528858085382158096172599945415129484673185929271515341501532356578389243001639372381636961994468796770707], 61395102632239083484504726167366480534468603555364023608078872219819805291764352149058391066636448656681223742767666238684930265537583240970048885928932840834096339478644284075592388596484170836326105957785190699505372543564143808603142392816667498274140974250850306390305627026443469251689674379781790958567], [[10609570863065575780821890012334653801913798838322112671550662476486732649540015631078774895925927952037225723488009527828622063927534023118820506797517922812088838664372258763293901534968310228394018463107132515728240047925387548339281990453580120339070086053905169595252641458403856265389765065952090074333, 103444199818680248634364660257581830971021418173449878535237457681418487181985115447703447378996668374031745158127115823494568130591127990218054083017702330846305563437157924683757479537507781049970162797330550816946397745603826586270812159497568997233373627650354871404378102744192658453194602836100330972058, 96423061962217628304833826414324825245197730371393933326814069575476723513941021403416806723608062332613915443088893033395545725530880954689621874773250324611359253045180106954479341285264370598001046479677635293555849175879748297478192089927716143844622898784235701344498260016750530002463148082834107688243], 66734295900575868347096012271184729871830037658954515588515076327921004930800659066428248596964195907511020879010157544475932898130109351709103421391383578893193574696402547604591328159171106820088551934795707779333573236237541200818233614410805787050154632148300193701271293017437642938897263253672060790539], [[132779651437769126678641739926412364695323940354902978803028688225358651160467218606365218438487203499188406326608282478718677926694443084790973655240791572416555306259131060031308820090158148013130420245178202035563087834281605922730760191538290152826169504270279096303628783118163023808732404514847357163431, 72890444702328751361939762173049549740339458421494979057908767422910673892690809409218528061353199000726923934345570818786813466321024899403270263860765546022110565117248894347457683282266471549761622680094532172717150549993340788951153134669973370898601753309232897501837814399078322174432563443030478723713, 128440369875589306952948698140181219977135329127036906402063859395646980385051210420635242905750156443244842579071511073889655644170347134163251208392436750175400084540454165573311716693371505845618716857372084571247443345530397976967775051536639158205175836289123014632993589154211784670273197140652960246533], 95172869507741231065382541211066913509407087719157599853105489885709989716885952945355866415678686085117462030201875556256461335293558667578885386798040716003504670387342555169203177619392161625642160497146472371166344123691986877357282553309550827059925899662013372976272216917946344277405160319808217123582], [[62935387574373724877075280876778664419571538053686633467370407725216357768483187357006985416602577659962222264224046243860302365687364567308876845047838671589409787627552806431185453611764476906839763482744821132330705311249393958604608405765828598324865773561660502272693321837724856585066420129352831308187, 66183984413544372251198217464156825514019412676512195065694138714041188999138783127552959655756101025829656368680650027837033587735573209786757717244248014780503277090549052812918871440145968632007711229680389753238599365761311931525967295342151440143004951072948020128000876471262799540138624414481138380744, 7107988831489313234252200245611001861914677760911083460936195327328892539383195062569036005401322478192041598556847763686985590981339465568681877416487978081510664891620656075041540574984361465979328586045364140238268342641058890067655666820121389178653802745337291743043625332342455034223525545715103699759], 51466151662224664405232285191034349679215973289844647654979945760494611632809273932624234265920236498020046911509706550374643394466403117407803559840468409490990589556758084801702184544450378530485657634405405694442988665194093217669741371707090519476562845553189336822185727048325161005675939574583319427300], [[83404771755717587543185672079708980477385730295342500639536239251266897195653860852158688557668135895201483736953415417814611874746522565742595348977953641334036013159058333513376232845490235828555385331362557721865625899922583592498790491028674150893942026391326659785793330699040111249032501379393017932332, 44377758379211273518173218747390419724969265787357427867406043477897294746966530283414986270552425835014581126024422113101042869436316863056085697589859801901654316393226629156087358232819943612066499465757605893758597983072018392149443488945231047349700959325118002038552662442629644678924263962339666955059, 102413361995552877335418353531040829574676181855883758839461103487602625265124617539641603795476529086136912183227988663217327604338488852103153683607800691769812732492586810592865491035051561536817297136288453561500528395998168165335248796130533335135266054228763827717577556589789558248164374562975302634096], 715167925936859257105030541332421018011771562437589343468681221179796421506875764942924912525155342121246446378251737324282521093600808758466352609530523062530557978827559269075319814198898025681567750699039278288624794536239506904997900339100580851478130693196911373003070024306231028911057928015308199174]]
enc = 110879468774054646611853514338753094691271633780346258691087137907834914373684531593216132616273580229844385901066493617366286725266379984340209631131102400401979638003074808631783672650352444881692959176739232939251869912795562628895096755457730901751313813611100868566602786679857800494548137703677838041788
t = 20


######################################################################################## part1 get sec
if(1):
    PR.<x> = PolynomialRing(Zmod(n))
    nums = len(out)-1
    M1 = Matrix(PR,t+1,t+1)
    R1 = vector(PR,t+1)
    for i in range(t+1):
        f,y = out[i]
        F = inverse(1337,n)*(polyeval(f,x)*inverse(y,n) - polyeval(f,1337))
        for j in range(20):
            M1[i,j] = F^j
        
        f,y = out[i+1]
        F = inverse(1337,n)*(polyeval(f,x)*inverse(y,n) - polyeval(f,1337))
        R1[i] = F
        M1[i,-1] = F

    M2 = Matrix(PR,t+1,t+1)
    R2 = vector(PR,t+1)
    for i in range(1,t+2):
        f,y = out[i]
        F = inverse(1337,n)*(polyeval(f,x)*inverse(y,n) - polyeval(f,1337))
        for j in range(20):
            M2[i-1,j] = F^j
        
        f,y = out[i+1]
        F = inverse(1337,n)*(polyeval(f,x)*inverse(y,n) - polyeval(f,1337))
        R2[i-1] = F
        M2[i-1,-1] = F

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    sec = -gcd(M1.det(), M2.det())[0]


######################################################################################## part2 LLL
if(1):
    for l in range(20,50):
        li = [pow(sec,i+1,n) for i in range(l)]
        L = block_matrix(ZZ, [
            [1,Matrix(ZZ,li).T.stack(Matrix(ZZ,[-enc]))],
            [0,n]
        ])
        L[:,-1:] *= n

        res = L.LLL()[0]
        if(abs(res[0]) <= 128):
            for i in res[:-2]:
                print(chr(abs(i)), end="")
            break


#flag{3b1f9195-cce4-a4c1-3821-73116ed66a22}