HSCTF CTF 2022 Writeup

from Crypto.Util.number import *
import random
import itertools
flag = open('flag.txt','rb').read()
pt = bytes_to_long(flag)
p,q = getPrime(512),getPrime(512)
n = p*q
a = random.randint(0,2**512)
b = random.randint(0,a)
c = random.randint(0,b)
d = random.randint(0,c)
e = random.randint(0,d)
f = 0x10001
g = [[-a,0,a],[-b,0,b],[-c,0,c],[-d,0,d],[-e,0,e]]
h = list(pow(sum(_),p,n) for _ in itertools.product(*g))
random.shuffle(h)
print(h[0:len(h)//2])
print(n)
print(pow(pt,f,n))

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

l = [54349218982607386847847085217819357939944577647586093692583148358017581437028911475150457837012931447425461446478122867920331540780220872854278761726914025671324024354670316774011785311886564066761925510157146208297572276311266112719091391961747478877693143393627673327533736628426700166137325090866307860351, 27135678066961980543626633525260046200484944418818647498594243543787826565635273064819688752939040148178015039803638498203583660705138444974158459410048571449668947241439394230879068040821438407134403955632866095873492734301604300730090112547556028730194181155811761784112406278832985961413310407330473364183, 11518179139031635958445091041627000001466259851462172913372853599636308012553018626064450517954913822272201758098351178720929147249481531347975493516157877254953975392788602758461627706489598075905181830739743700785427560856549124027135712289420156197903327062925894646118592073546725005957803333996759134357, 30583572611815170730008998607873817240309986848375658665902964347096580929805060184347319883063575633298731447887035085963893396545144818004009203370654978243338844810338797628733938933478213597145059003295706057820427150058312584765852310847718780240375546147091930065085990473224483994210039331323478559457, 14077349275268806627342244015497707710056034218700655602881424137307647938917257716815610926037346915845867401176943756245156989223510474196010230674550956771471796841091927829825495636311531517833432310598393388734655357683145929106679887902795730732027052595909709892074007328207710501612753559579275401678, 25735575371019520016844976708659328006409604316765238985328778748965802589197398748610359105960471663357788400740152664018215127004634595349504102752038089700312257571138706864708000898919372529896623370183357980457477104924451490874435233878645564134902958678389179559716059632339377425226384291550334267880, 52981557023468690057595152537538339484902534970758824513611832939035168466215968179785055321970260944897095779820876133143207801720710704187320863784499008891838694734524034975705010157826986180431547395074623375612841911049080598468015923370054667935006599070674280901941605248990445529835426435931071679163, 22994460106096097952222113865719148382501700170630082775282276670496360738675220101486755217537915380143969503239792604741461990052285828296784798910878335368031743973100704180840110639714733281016168694855701857556528221366777499737269142686213466943059705354030782228599434278950830601669056913347351382049, 52616016245490175663733369619962967329682196814000324030365860124460494391053388117370073473315689051432149160111366632227609254563803438153309944720182807931293984549364883195474022084627224964099663731354310040744450310844352244845232308451627076384048035719410271050014248106430162909575071624789621294017, 31626019671439539812466791378854017149942541309585662907218250783560614327893996667959827799266935814043493119516602806662692877008860031985147001524832232672521185759209107920131116448665392679202357815062110568109804527215980639262370802722786175353272883087889594053882910748742792001842757557357721029180, 14411525318374718411089175537774185382523583624356492663694002754455247851388682238761787997551621655464118231896420254053844052504597442664030989981120799001589082750560940922479348863081894050150161058680972184150574787309430003409611399955095671574752316161606809716947188471107944993773409616986208314506, 35132707033857181157241763039439987964704849892056087169154231696383866909243198167456944634558768936048940787262788836081618444645767206069017510376753366590929953970798954139204305360417053401438091296164125552930037014722160023460993012454423112980575809661443895908470075376124866781633965565931595569422, 8968049511854355147610634180388553293896909063961805663855250874024233650291652201495856119982598546939043208108779291014921145006296115378574465981480837060454559810661616002628205909872352003000516136937520423016331007658032901064672674573356077899368878482970202370826881220343868652082495218441314120222, 11315525674181374719381772262137489279403106878134723501207024202644062319435488502552317630874568633034848830526986144346870207635820930686471461922240325739098017469268169255412776243067589778529306763407229519032556002001967716447545701169668255743827172178063752433607334245454553984344823786663617236089, 28511842719802034062404032496867863822571527547633509326484831486502836877965890053908251727720297590566952027464600687880908056519557882844252620150143632556952088543705275857429157766126793779090370212482961182459399284714648278108402522566473587236243144159964532468596108817226800231746080208694654740329, 36132431159932128380153752355077719244945583291704452995976098380777273003041805936263925882646963451287295238001276788736842287379740620217338832726722993415279777920319283099106386265077953493881983169971829011308283819174764820101896346360540150394423623902105754692911186375415069695116182054918073715955, 38428534070339807801137513371422485655815118518587084930368671516797393786269368727495017820827964747405887477010236426158214728517288905307725748359379216817030550912808243036228069110693452400394778035924961564476969767922391924840897280106276223075163917027155987313902164623312193946972292252003976678121, 22956683431028013917944871395499119623954641035747679023846730511945179251249349598859541526426667627451058294071018061781936955206724783817610199965240230520639417730430834036146930394062534444937484770717147678104583112287071563141840898890228514790615572761600529329302812422508388629470905504331290333195, 18068732723471080938925373532712252817152536498520172815266521631677883177479604174303050966927254597096825218905400625214406738365446379412411786913246822742311415241809462693017461181344400937549290063436990306171098210320858094476775883316800940896738197241546962959571803996876880755891142393852164949762, 14915211448523570853898236859433689524182085532362131022614675619803278481541242945029019879624801176495324553321997962963538328501010830755184615774472439612044515499344035990757824489056450532526992808438481612386439222063484686150951890089157181423792411036326818486000465175863225811571565632283108025808, 49592224895810666486872327281872477802883995127330424975181174679095426782859985188436446690346850089542631364291078664864722957528400654468018129883460242161055718325093322595819475535974968864418228942166030813300775928652285360597651433806443191846103677929004914736818928024952677250536838055548608313034, 35251109759674494127230125436913363211227225874907684136556031830809099227022413335246169897632934452284535576710082773991190023239260624259929557091914695705362237206026886390495627036355783073323255630626004396415992736754127424794822362432709354066763668360862127704398960071022999458586911509688841074830, 27170667186270407139159050655159879735073415485401300877745521919791531293074492616344960861971214255018271103583462391297976325486275316736020439130593664316571014043425702729983582136888411209768070857099503446400592193783796450604323869236339194907287299239486629233446257693040131126276215968334670652530, 19160065994756632121907882757804251397030724173349039572822752295844389995074795636207186201278113818076489399279713482683467982705693913619084596417239480475668249504027417178002766492774729847941933284549275311182232422965739463302124974891545825349006084398184659906550706415808861338409004832870941190872, 41955826391301180261424621455566408080091844719307332943977828848669235922259858556285054589631891652434835778946608407090824918565714284355246777253357934673443960329481695941407257849147952022258350698693958418489537267872248595907023138716418027922066016587243026769425983873393124575482552201448540300949, 11784835716027798702813651206682479552121183817908576124014649234300615565862322800748010676574315900346299943922057189546413498850528931301413088470915028803125286264721215707238905735170437605863394251718198143883679190340653799967330576891685698093814403849693132985284324380033729132161426795811691141478, 46014142607596001396948855970548620558142884265588392292892186140006907364524539976358213685043623797380295527857127489551103592790427871838544273178658681697741004468967037431560802227123922665767117157530851411786225615163613116288817209934591346444022040892935342367000773116646723871854137165591676627446, 9586656176941130955567911552664289534535225376071322362522460145836671175519931325451856056664447716665071441409486403829923932448784610393215563538992287756276191533298685993838274893201258130938599712747559297676672714401467537978940874628686081801378866090358582005778696093086795509108777409348975120681, 13140108312645524895936751910621631936007447390350763476917796323610581498413394101465489339986123919819026173988966783125951649255123748717692117798988467375871467716673667980837612171534184025012976351457573339451581139565544724537002668109119011400085310004936893867761540705375182690125431837085979915785, 38836242859253282725082599762116169543603286868506195740028737227458577924224289616503907262625550866605271125652393124922199644563492576199489619677103506997122049262979190320516367709601371341739560284601894227668451568257954848204436346729563245276950976171764752275623556258953857261942259689025918234846, 21385444492433847810423192183669283395239775421441846846899920848656136766985600528616939825930834042179337929354190700338128880361473649240968952567580275433897719660712073531028584611026953780029294329449000965589015386240276008444552353845192048529047612257962987633257491475589010668203331443860771897409, 4710585788468584506421371663870614755101226901299733458190735408180655464653510030199770552596970120952647891164252585106418727994960390035310567934039629805746578120379007063742611660029163050791845339900662300320738495272876286469264553473661811546024773011303334242167934244287932211393342089312766995387, 39553094260247817469019910676621820133219036532043378750797076460254555843024738911218452305178427957649576191849445025805095834974359394934937290564924847315857944730853168123323411992929934903180884228790042097341829591550004063651390964545874990703202015577281586102360916908996982814939189744128514496089, 11892721157512872088186990529207571267695398934231215061271546977762117753647037097181488271137790911956645787155187675599965712924746892145450496481899851065776158373884552312458982619621609123972585380085765935834765894221307812163148189721528035406622179623984487017755003079956245553513464239655539947737, 6289307716037224733438507392205532743071602834501493983899363620585220680762801812675100615845397997764193897839354992715742728322747897428501337667124246266547732135132380882583385052679683160072997367908916572240683404341920428115379633099087672210299135288351928714469681845023671773817107438382555028373, 42986386297548501647028260180659970179668872344687977541259914587068261288739823958695192901018641599759796279469888804912346165620315171107843490706443514036686681518956302750706859610879557058621028748917013419363366420715902943137723031326078453655337461463265185526866823291432926065193455280347984307120, 56058374190324595101764713028048658128854616883967193896715179876710454076472563489497463469899377194716405638702039135958379030469449751442247341639142899993393637437567557389807127409160474485344060690886190191034790254571641736835098119924116173471433949518314162494045435800405934781303910975731713462406, 48888587227160708581531859320150628198681440674708436359334296606155696234516257087415050048844250208129857445021722743060633970343358994292903998486793081227760712126555923365398579262744671208539390328211773459566545447826637747409224871328696118908951388197303481491153567637387071477822798072266075932227, 260773792510095645089262288484487117864974281173703754516563219351929442529895443460215519124670101940114209925148614023729493080329661911265964483550167950257464943909947103634812423237111641697621682592873847243114000411122338805189424802248170903844555307166947130756614305157926638132512647142099364931, 1969929000227303899006890098713787306775013517554803958648594738044802081973547457807221152011115849231058402149064882061776982769558540499234544395779042272327078026807187719430154520511022060279756863321917829980331978671497962921196152764616865497585361431853436297268313477137161253299098532007504966986, 23617386427470615871633297247033921260160267609877974232727214434383736532814429775542865855818568335301315403803295523805107393984197226080218097141174627781976007354879896847015082976252774020480899808348875194630981564716351155491631392755099125428863901153693528242388552855486202802986413824222399081428, 15173038709641520612351423668300662293569673084773090336322815438685668380968808034579138531528843420642202216757812892414373719504274247911258603562283663547046876029855396107208410944427171262428640774203546173249749352085033629249083913289886840857658824860551603136833691063718486384779581367701734667085, 38854359948803001528917789214565835848142301882318203721407133399246638392240768826692118918287297931161133335737314369935476107703112614998414787073038397615692404371748240379429103231078697632801290155706448921479158229722726191886452409187208508560332819340252402536674295264599114262990050789894461812085, 1247754314280326967665708043451828069998706372905988971509077316346910375813028325969798236797181059575791662958045063079635022312890581007282782165602534305695873361534803107081358436267723897657130802309463969286197532164135899289896447136042964543423450704980802977405746515501646133941867180350723923476, 16766053722586873277834064639911325113500554633097518900434666635807827675977720021739226683845619339006943656777742724177012688575420018418576015557768220627793157650624336370118527839467651223860798144689021940936074663432760011988896580180489353672076489248199523522441133196566878604497233878745298331248, 50597593573183281010633123140749618416005836471605278946976564590724939335010213256932930646239840961877139755928515406753854216256707705846628009749943296618552151523986423435961914947387885271973024146378554943565367094652673173211146997908697909671508580916909960297001490119299164487262508691697805881325, 31397328506607927961751774942884139721841751290239714212767703850319209603564482926415731465293471847718184983098046519310777559658706015480382082566220687030530292892399096829879498787034146039339372162425479971364545509854824161663835199745755000827079315416274249052748154853767823633695969686494066155617, 2365451220704603713498958384005492336533693439550349375374837296901791116871817272119329756818369612869054152777631685004646290082373128574972295869066127763109558434808434008489853696739387793916439683975125504042286663689410210142453270922314968718813736714735262937947012307592993144574085221754990150061, 53364807803889862336281018014172117315387701198575115950253005691295111059018714888693378999070092967020257224486734109217294329119491711005441447335604011567799030895149240505389009684381764037076176013272100899485163565846518172268986886521023778640751610355881944197606108596888335871007900482332048692452, 55843794934691637771528151838194680172100305713664013188778980786889151806967470818210652169935311843247853994829839433984511331521476608850832172067829828707910018779178758982545681146075950909773778426292735693850859806503596307567622477691543123423187325706457645377608972302755559539375591367327763852636, 4671020192937752417769878031222216506894378070130349166319146381541040826617339215221948534454428463975024450696551127269684035620701423434716297922845378805844494293479751723306786791171119198307088683979786884090046660543276692186376561802561239113703812985428788419495903177462718454229031949030065953854, 2954340178944828410572957302361027931331889966565781700978737404767272459983744044264299989953954329636262624140453640764814194430287702348071858787089056375852071486328263988052930148015822089965506360206963138792740689136245903371300658205340565734526894469599165427195941508675525548428523140541764134885, 37528462608250576983070337766539968464167248660596324862038532061910265061638432820650519921057482716370633055340427505314194118130897891931470930729327068340082956304691707023026769048892357639033532190004426995825675591593196518122735994572542829946439030167145737442719940874823295873292863415433138089504, 30732741860076652594280339354204399067936015046522210947717654849062480880561640037210778324496822669360366734491822620898164722707932752159563440280874182439394408869384740392029103997437522143738781548855812672336519071226463030322373475889974504533430636354140642203649546859082445351915379834435711707871, 18038855951555735999886520418338130270035774427541877793966423571444715297959320441399556950639254875075783862519888658103859092514532906576592123923911009858349621546362969273057505527757792509411266986238857429285719118574166336728449498255385076907322802595108246177706594775321753302056458496128018002073, 22878682632440404188734968424185582987157387342909505112494049516536050282260903571120217801168161793589589061878934097768768607272173126311354567083100789471948707099121163258519423434701009134244580853471771291191432455485404730896959670189770697545915732663007511941759630520474047950234858008710798875939, 34279339607817315043790177243189278300837970353842379759438030652008919232752778987152447822064504821843951878454756472513605579171176154257886783842802758113832440663558961245847434360213053265396155853339945536125467695741184912869535790063291369072489765068939686811612971705628394862850508562869303996879, 32064488381795141957688652547221397875042935497588700175616244922296722786278625703314645113879950933488933325051042583513335543692153745822628252624592206986621033199002014467019429618271604675435185786699501198674130912982956046771953635013894217541511155617590203407625221428459421274572510932770572246757, 15088144864804471621390907125090451481572831161237756399272504463238561428377352668424969195516169339958384145217994518208225635762378967406118233174636825050931155793255911253541966278875833317407873767695494203885994114404255904097299233746083817079679086491257066440714357890784455790183281116081580859758, 41146109273193170134502551648232482953149918080367807314908927657376715138033650898378540457495203876014317631869374857567734804045505165442254702560409404396604226351622108386233528887970414864613041599275517865028154902897730446391203631436477503517619679964929506487968359041845375034656842255172078160252, 32386721148439807408869951400633238801733701098461659894406784774669101654641299269539344954318276766012809871734915783358241864828861275184251633549680987890521809968891709065033032354194462032346080720716072364082617705351973467268526209783376796023552196892510829625612341209525711474748644137503062319629, 44828399327901017382399054697225152350979110365679313980941028812899997487889203412551010824550316100724412356902058077929477888899300366947950967377879277444691215165387675442275690240287708869395474447472929837299798549022796240577257058344307568495025104603771861493778281832468665932162607618734765457282, 2813804865048682505279391957992683624531548883980258713607632085388792507194460791187950979004563081200084096221668834823140137278054622484148197160343807915974271677765222969259005501549191397571731373740077700495080407171889729741874015249028603589295100805522696136680292139248068842101361279702199821109, 5110002388092445540750467697789861144335584823826460469875561122223386384558822110790303085565569994016331283833121174276089318687755460234752069459786799574249460928110003585638338550287613254255486336294451686728812561274173269779684810508948771859045526688340946710856879584557544416208854412311498772127, 18790685374584113763783637549993176782552342504544572789193211034152118457364026112307159067966564580285886793286760244667914405418881521422042375393365999603568146076785797470415170783505228488008150183474637042452228663389567557517551550153821514428839474658335372182082109230740565546143560207440674737833, 33440465350394286558119006892347562259562203822231392538737693579526333236741555361837461187855885503066930786748253652213339916277606287042158739039592278471702395282356341234922516397696576992797101520007292747086471799497359344743327874536593646829362772162473597683042419585089813469201565614163013951398, 37159081988078058624946092558728893849688866991791858078408990800217993523927663296750492787745933478580030449347474267298640540844085499734428709705453587467982852877450087315439173339622856279099749088929788727095671832017024612338162569834818519026272420427296449718251343689755000081027418790002871636465, 14372119721690850572207013552285011672889552954951361499583749876039599783517813714521913264370173462697197258535716046449450317945161089473902886205045635365467923489652343846596462366781063670666514097471328832765489200016880100351736702623316192322957818338790397763238435550222578377297929771543184333312, 21699231215896951954207863442292127106434941805548593761693802878737250660024013023482681213043344092338397530608525393932906489515934241880282921575615327959507413997830261863789506118893894495662908114586521874178381453567061881353007969227197519731123244594902619016053218862339083428460070925626442746881, 10503289440544833577045238130185977331787486167845716494626761628780484615640431438409017276752900024901262197772467818980753104448202851248883555226846412529976985741759138199751811833708004308119332261798460328818403649195794519104563132841662989039281570367042622617364250366107796486218314404464222649230, 49303540728238100116001867566956281598192362054159829248532182945788988486041971983648068054199275884757254948046371104393574454224163815346388069821481690958398855978494102000153271031149401575331134892052495704309208480673188370805003977817595099605637194972387526867021040239047236146988426974973514283176, 35305811857148289838528543818361369504685330512211894842139213086619606260495398869920485785884478249666562733397273602820084600196647069634568266014936817306773626384316367943924806543921981680338781849323538403127128351186641983765827731495971478837365264674204570503387362633527302514450843464225077968056, 44426426825321818658666984787325573979024192230909682589960196118300265765355421835776190717886256384699874061472000074382142810625032521208062809640793216877874944007592952180982957212775977003069096993393298102443138360761456263477139355004836308968656325201496622607047047025607615865922959383218272879600, 51209145594742245206103507618743284102384006341314437181356181973838997134443636822167375903458477302640188564794066575706019204862023953118761236662906268369401641453367500907803601282109972872786196037184612351549091693708590805860602734217415572516232978137140162913945170521006317003227569210562314055210, 32773462879486332091333774088925211017568134837934389704018005126986190933177524829925905325537395211513289457854844781378399513654319034819203143118281684505732006354230687681851464358673794603457029326358790287825974793037960852896146244223031992738932200338162458406887209894680114770617798898633557487023, 40326566580402933588608951542406480745183446828942682126478842459559908740059187656677608730208765967923439312288345994542047196011359958330759277608943700896934997254755933813256389278450115060055704753422766228112023458662485906164849919879250227260355045680654011312996331578432563052023138470746888327177, 19395932000396255104028145447614159940964690878737869175282054346842197421974713632984989333742994260917118945855648574873492581373909438289890662880808505853183996168965302870007056122851197364959053807643000698047371251660922075212642168107893275130238573647375692383538434306496824359660381297764575488360, 42241798707565884119511731301035437536663556946440242048350318958754735580085201216142068062986700380810652447450243993736951534326268939157503075448142111172179305540385576663616444196086054609208250062880670649543248897299618146533607656823568613643251452229571399732728042777356150917823670063294537425659, 37256242985799706511125100602067430196205224876879665025303833458442469557298579056090607435979847585309012215564389328000102425682423981649147655363773489719295615613655166623283264941049827654638963683882528569782135961463816214035377933112938330936000684410539519935038129731826979001333024712110280843596, 7430560755673982165322115996382517048038150490432461291897446489906687284486201845542628940179797088526662403605465006921474553206420419060609307635899986715890390254921581128043360569652914918502292045267290578711358807156126328231062673397668225466327116628177628133648482468176789941613625550607736895110, 47491205948064783576252820815375001015364933428367931297011471187250122389358906753391258702150040002181336204126499984038695123270277892575855806183078057622741984568641156972653366975786580250189796906342807056521407738520573094270747129198649761590155896750921996622830033898807127719452188761246250552794, 5207275179102721519623035787238513761907363966554830157263516881532022015168020242884299115668753507852293638928486650839869019556484425418536593213139382114227265957396296297158549939470183685398684950755361197712671820431522626834773685608544215420245233263022654765169260926095878591091726490437133312700, 53623304619651804520823398636823598929539479983699327711063733761119922079218324517014908208594424778553525838877721571058421476259942513903730151735783113733680169328281911061265782178146221556101329214037810857033810789394627598026386105920271819690455813086103092056356038125096494692879522176459503361849, 50794509629782400566985268306982754641171527253449843081021142515798951806225987611100868300210139804737018777660101593914314925894562043346408133403666260034426006548915994269085060505796451600099191236948943670854087354229385563849681047622512705631405659952627232182020522029999618113119211154019276334667, 53079252682062993207962038712693449464194119009294056271595542308433001999729891317872554910904996993513600649420932237803785275083102273519958711244796474684440159810462398447491110344928423665543959557597977749648721174673122896222471923956134521289654648441841107994833542169062731309331796211867561565048, 28437168367105526048782871366093606472006119935600194486752038213977923619725630975838538964476731307111610233656023186198309971533385439901925293868202597603575303555380797965099894140029106970845305656872246326394620874189005049847734549237694020988867186719564150688206838577168953009088158546461296024208, 7272484751918608588209283639799007260181243185121683157407142285156569680069810145657971922921907632225046222488807677002147453041795033302887471422847835072998386931636000524685344384619002183885806031658289369771852791994925277659226081199261090771449832414144566723363632419088521150423647473283891170012, 17482905123581408021771375554416975703116304296634701911203005868603805594778169316453771726398496430051248722974794625059908878986286837154023686445589560946529053118498314172925572122796214785302122088877169810609452686724809227435851197996801099098327528653716357349178493846610004157494163933847894592491, 17890613912494882945716461945110659590904472646553812720863071579264989732733090205462661168196082549250632371616951323823893795032490508045787557763313851126620551468669261457213870721704133726646904337554102473800934487060372150799390264620088121300114587798325122310899885482251667472464131370869836149216, 18176092256443693164605255726105916743405406172610053570570099795437547033764748242947762542029233647408932755783272646766671355336162541376653513283443729796949481408665568685327449373955016836322561408157588901671156598770453525836110076972855643582632501715915852622070709581574777724130010598391192474415, 31094519420204951362771299287240709814024336684432228556842373122925968932847610201267241642764272481331834340826923476332473539454487105540319492742482280614163216769236893868866476258960578961374095825521709577123139207086156538970691612593657561263702364896776166263162132673186796997474079915857956335089, 34619916766937738792646111874241018140284649359592303889537940217325132858978445909474997775980703204318122318018662356049202034033845171473230384547077739984143688383647242629652433713503691631378774258892542164099522801415702194287279575499166824644155260230578490608748831243224777990976352697247370080456, 53953696762130087033355016932527652910185897725590548275856905799160592402130641660838349232205677683787465695849556064977462233467406284778541010253626940180541543946669070484952086135658198333125242689503938534235617591293353865497834273804049375656464768110745846686855037797970868274862338401118822677276, 50636325981658904864435169513099531570091869616741909003796711045454947466651338710822925642517330622292170842284629837126558743018082978246909958032693574813968815581594307712866164301473079623200444285957654305755814781884134524722289993849406133264166487087987772819108682761741902185221267059863816414106, 55750338129987732272591463756872294163496361761344388747036913268762567804478428293167387906953918301710956716576058772509959406571553094428639517760075196941626901530421349313536790324389656853550205762717904419514439006667644689652155250520086901801491269140440778839391612231733771386391369050135558373331, 4919440605777259890247975604090678757566075710409481946643680520705964710192503605964458994459594350609837459065530988669473866576649022777297531325122522074870170649343451710282370687983536464498566120721644759701832737122069071840768507775706753836092631909176146432038057986240806941129055376794039078029, 20186716822902562366700222961455426001774007873436444655255644715285110515960652996693753106377083845369224610625910961245266236170038793136174473395970074528371324461158221394335553567319632633159699203507235026969620435807999255538391198365824193980854880923375354931890863730148791724320241567955739111382, 52415226570606949276017411067812047228122967379702180307460303757395035030683720424524775382141840071669354408274688783299767916169888109372597123866866745564412902239812874802853934721823774645029749679167271887634472453102785790528749566544135352241069739304571675336422597724252787018100044119741389880765, 5524638353052290179868707009550390605548063911691054570210600580263431712776471321856810688813907491919501070967086156067793597655217370007105172719026807909225095832561510224356879326601134526942491136530120367423816900753378511790606497103851638743872844872853877442781528075564243306317212468854536492670, 11862356733416320312167728789329733901173865101176635046626134849772312555196587351854127987834910355787266687557414606972493614353024381293518788333465691849200598707197400219198610923109727886019456062760773462682682086419204459433605097622202907747874929579313751584972915886959366020650355555979802011617, 10636675882301739190425489131650971408980942681992373972171039062727511868110965155384716207809587224434540199217122160916630665074958816924238662480418196340220544061273740742296431646430834223583853835210084834239305926689612874525213886383275984727048856149668795768569972856984449932645654969275008947300, 3239895300771697538891936603839695782525472155846841379636200787629381519272567615085124078119050303142919199206255512178323248466677139833554594877896593259210942571015106045950829487469162461497722815881086288629183080309641179417815620770229823085623856383640001629968507936501130110104627411006251262289, 44365915475219471132853134104194256115539659862736078667659340205631820673061823116898792969733141148328906198684091993243580093979051660434593269415930115738185049708297248894671826448130267945410323761089719135619128521363002363755637720995917966270779372107733876841264184691527191081157085250453265857639, 40127404958218242274892153262682159407354547700224867489851864235225061623373493343508810290720495434947085715324013573360056407484822155692821822360456020205691592654400008643705364244612846562600408916416751525800310486737554702215013095173415082734418981836791793215205746934903484933279785200290930046687, 6640210139608031053308330239094726691727650815448505494485750877679216002257699881699907039239049230907099227107997187807903979961311007874170910512748258923696311990853332232345969689837134252741559527661964055884711726209725801616520130178561005264503182511583703063478568007501449697854557077849596214258, 3133671816216237082688363318295724008518764523825696307002444575579866247369371500893683190063025686410301545834871613386608281078404328909198981518118904814401347594531670070416714822349463782810669581606072699850220276244399705942392689457394246147005652594163131718328388719408290025377319887577211013012, 38143055726390997582248719590427228503314184992530844080661643300624836485237710690009916446994813649247587092843915103215437168213616871976859792839249338146701620972811935808114490458442569290719120965321475136606747656212310549804177467753508700792646003109565257002731340523989083695306413024482620352922, 19874136931030124117078579844021165860515740094307291018974597758446119742414784857534210469123796228452885494336362220651584270625172851628728829924331147099674383052091015050922535885257961925232849469705990560503405917624180446965508009230417851225808495406237137107415824542614146487361788844779698635678, 12512643627333895187651086349306862230093336910609422846556341869082511288657807257044169190270115479777235198526481304233593114599917222387319428418645099938775475496364003067465372055079261892514835802443710412563904948208001344617006447595329260332624868088151445745665874014295124078691659645193709217931, 35678699002674023187199027091929560036669240846102584556903346243534045373233518405312245171240332169870804818768798161289365899684681814386232022369490988959992087528615502143673541831131772482017252235080622499517521056315073800880452055518628408780359187276600467492776895153120899881266846549473815282434, 44534312266806892044040324109850665694598407347232321527217093861761767953140136132209668312449731396310219904705130560435695024699250482052100217651778039140525816116756288786203034097227148521178288121760865894394225064642110275672956967834678646281464100975787976639517725725530132287274996827062121685859, 29148480796564283607694924661373265511646175679739596773486221176270852225927966316612718127052833041638248745043725358684132198063504096617492866992099403627080088338051801763458357695509174917273611516379560591877312061198967625035963675490025149467991205585994480391355792412523730293160207654539142174807, 32488135105713535020820644537733001465981237752344711153459436353762800573540708944004528425814378662793529703832039886614019166595939190184746224153848514794324144224486876292564194624405664203883745798464542661877099726409061980281285996976741467737161872578896728605531996152325047550580544949709979501477, 42506379446779972316845098775890507674513348386124203368980936604969823194343217503134226124953077615993754274602768735173662276903050809469322961526094899887903026245935272129349691295941122721735219616478844266086612150481573249673038444078685097009120086510562510481003194686964306224379544829786792815057, 32701761555364074875220678069499223986559323555262923418504528661678646986188029157414813133205478961355204444823892226177001129565582187273295208981518440161675095026597607646426856856144812106560782565130188843646922690266412920148656151971265218946414603671787581382413497250077658616450009798651413745909, 55378223246501554231812755993772491158829674859072130567306365200242990629211343402928082781001460720260936442298970526467202315033616346476644687611684974168416290546941317045374973116852393475285294549728973651843942292055058455706489612100037286998213836710893366792129492530797829147232716049981612072239, 3736684494150154300484996539584374081385282053461106406961206654574894887780787082206629731885866197424785794309938875190891072101491536051790963509985793748382994861231598878369063889562016249603058556359324013813881813746706594145926047724919699523359044961752992556870309360960246566641047431738305013036, 13332761685286189099825715135873175067050718820452920109971828508994122230262634974262486088005405696896723569157298945069762357929464242245669815416249553906964420862521201742735080221518029068420653624562050618914537834266861132502564513400285890719941043362215924097935226814130935354242968342525828520217, 24693128311395150934387183937679128096777049855555234744013492312501769191108462264997851189757111482613026729110584943319415646540919381368366304597860835271129916622268396573310823383732193447839324558416953470168099727766783436377916742003578169022005621737591515570919139356821069417593666065516091798157, 36923215982438435642825829868918985305754900286403028475949688749220186097027745299972689655281053035739400902771539175108615942175869975063622643241884562090467106212512201623434883709546388762082628565836063340230533003321842000427645376618471069245039931178105417241263615799067037059776042325109237338977, 51648127789896938329084097285310928739825213095010548484912596714521342692385119717735730454569618832681495397930636622712424487929077989918797008199847689137806608087997752770135153041226466928734593689499277154187857594439487383453910982923803105261574691840052321205306146928101142965207391673843746873483]

n = 56319147982834690746853975316533145246719591165140897651231743096062383519002458932957678989024047296656519848627187749982108523549779413353513306122693067943651102381477504493441939832397586127041682373479064038277904254982764075640287544726364344375278504825481109624802050105563861419436423622873812827337
ct = 22560630408234666984622660623345600406581810801462944442925416534874150827364809064794374954441858113882177788546174341584373911768728976592365286999292769259538811140546781640416859788199247941294855485036387064352138049560948015416721112570424424100973923502360042557894202576799349475920730125529804597978

#c1 = t*p + e
#c2 = s*p + d
#c3 = u*p + (e + d)
#c1 + c2 - c3 = p * (t + s -u)

for i in tqdm(range(len(l))):
    for j in range(i + 1, len(l)):
        for k in range(j + 1, len(l)):
            c1 = l[i]
            c2 = l[j]
            c3 = l[k]
            if gcd(c1 + c2 - c3, n) != 1:
                p = gcd(c1 + c2 - c3, n)
                q = n // p
                assert n == p*q
                φ = (p-1) * (q-1)
                e = 65537
                d = pow(e, -1, φ)
                print(long_to_bytes(pow(ct, d, n)))
                exit()

#b'flag{sometimes_you_just_want_to_make_long_flags_because_you_want_to_and_also_because_you_dont_know_what_else_you_can_put_here}'

from random import randint
from tqdm import tqdm
from itertools import product
from multiprocessing import Pool
import time

def average(lst):
    return sum(lst) / len(lst)

def trial(guessList):

    b40m1k3HouseList = []

    houses = [i for i in range(8)]
    b40m1k3House = houses[randint(0, 7)]
    guessNumber = 1
    #print(f"{guessNumber=}, {b40m1k3House=}, guess={guessList[0]}")
    
    if (guessList[0] == b40m1k3House):
        #print(f"Correct!")
        return 1

    for i in range(1, 8):

        #Moving houses
        if b40m1k3House == 0:
            b40m1k3House = 1
        elif b40m1k3House == 7:
            b40m1k3House = 6
        else:
            b40m1k3House = b40m1k3House+pow(-1, randint(0,1))

        b40m1k3HouseList.append(b40m1k3House)

        guessNumber = i + 1
        #print(f"{guessNumber=}, {b40m1k3House=}, guess={guessList[i]}")

        if (guessList[i] == b40m1k3House):
            #print(f"Correct!")
            return 1
    
    return 0

tl = [i for i in range(8)]
possibleSols = [p for p in product(tl, repeat=8)]

def check(i):
    ps = possibleSols[i]
    ok = []
    for j in (range(10)):
        correctTrials = 0
        for i in (range(200)):
            correctTrials += trial(ps)
        if correctTrials < 150:
            return None
        ok.append(correctTrials)
    if average(ok) < 170:
        return None 
    else:
        ok = []
        got187Count = 0
        for j in (range(100)):
            correctTrials = 0
            for i in (range(200)):
                correctTrials += trial(ps)
            if (correctTrials >= 187):
                got187Count += 1
            ok.append(correctTrials)
        if average(ok) < 179 or got187Count == 0:
            return None
        print(average(ok), ps, got187Count)
        return ((average(ok), ps, got187Count))

if __name__ == '__main__':
    end = 0
    for j in range(16):
        start = end
        end = start + (1048576*1)
        time.sleep(1)
        with Pool(10) as p:
            temp = list(p.map(check, tqdm([i for i in range(start, end)])))

#Batch 1
#179.22 (3, 6, 1, 4, 4, 1, 6, 3) 4
#180.09 (4, 1, 6, 3, 3, 6, 1, 4) 5

from pwn import *
from tqdm import tqdm
import time

#20 loops since approx 5% chance of getting answer with optimal list [4, 7, 2, 5, 5, 2, 7, 4]
for i in range(20):
    debug = False
    prematureExit = False
    r = remote("tunnels.hsctf.com", 1337, level = 'debug' if debug else None)
    correct = 0
    incorrect = 0
    for trial in tqdm(range(200)):
        try:
            solved = False
            for guess in [4, 7, 2, 5, 5, 2, 7, 4]:
                r.sendlineafter(b"guess:", str(guess).encode())
                if r.recvline().decode().strip() == 'correct':
                    correct += 1
                    solved = True
                    break
            if not solved:
                incorrect += 1
        except EOFError:
            print(f"ERROR: {correct} correct out of {trial} trials")
        if (not trial%10):
            print(f"{correct=}, {incorrect=}")
        if (incorrect > 13):
            prematureExit = True
            print(f"Quiting trial: {correct=}, {incorrect=}")
            break
    if (not prematureExit):
        print(r.recvall().decode())
    r.close()
    time.sleep(5)

#flag{b4om1k3_15_4_v3ry_1nt3r35t1ng_p3r50n_924972020}

import random
from Crypto.Util.number import bytes_to_long

def secure_seed():
	x = 0
	# x is a random integer between 0 and 100000000000
	for i in range(10000000000):
		x += random.randint(0, random.randint(0, 10))
	return x

flag = open('flag.txt','rb').read()
flag = bytes_to_long(flag)

random.seed(secure_seed())

l = len(bin(flag)) - 1
print(l)

k = random.getrandbits(l)
flag = flag ^ k # super secure encryption
print(flag)

import random
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm
from multiprocessing import Pool
import time

l = 328
ct = 444466166004822947723119817789495250410386698442581656332222628158680136313528100177866881816893557

def check(s):
    random.seed(s)
    k = random.getrandbits(l)
    if b'flag{' in long_to_bytes(k ^ ct):
        print(f"{s=}")
        print(f"{k=}")
        print(long_to_bytes(k ^ ct))
        exit()

if __name__ == '__main__':
    end = 24900000000 #Will cluster around 24.9 billion - 25.1 billion
    for j in range(10):
        start = end
        end = start + 100000000
        print(f'Trying from {start // 1000000} million to {end // 1000000} million')
        time.sleep(1)
        with Pool(16) as p:
            p.map(check, tqdm([i for i in range(start, end)]))

#s=25000212790
#k=389765888090576570955475182141325089472464786538658752612177661365036722783693807156706073599907199
#b'flag{c3ntr4l_l1m1t_th30r3m_15431008597}\r\n'

from pwn import *
import re
from itertools import combinations, chain

debug = False
r = remote("vending-machine.hsctf.com", 1337, level = 'debug' if debug else None)

r.sendlineafter(b'== proof-of-work: disabled ==\n', "Display".encode())

r.recvuntil(b'Items: \n')
itemString = r.recvuntil(b'Coins: \n')[3:-10].decode()
items = list(map(int, (re.sub('\n.*?:', '', itemString).split())))
coinString = r.recvuntil(b'Balance: 0\n')[3:-13].decode()
coins = list(map(int, (re.sub('\n.*?:', '', coinString).split())))
coinMap = dict(map(reversed, enumerate(coins)))
itemMap = dict(map(reversed, enumerate(items)))
#print(f"{coinMap=}")

print(f"{coins=}")
print(f"{items=}")
print(f"Sum diff : {sum(coins)-sum(items)}")
print("-"*105)

instructionList = []
balanceList = []
dl = []

for i in range(len(items)):
    
    #Around 20k is max per coin, around 60k+ is max per item
    coinCombs = list(chain(*[list(combinations(coins, i)) for i in range(1, len(coins)+1)]))
    dl = [1<<20]*len(items)
    tdl = [0]*len(items)
    sols = []

    delta = dl[i]
    for possibleComb in coinCombs:
        if sum(possibleComb) - items[i] < delta and (sum(possibleComb) - items[i] > 0):
            dl[i] = possibleComb
            delta = abs(sum(possibleComb) - items[i])
            sols = possibleComb

    print("-"*105)
    print(f"{items[i]=}")
    print(f"Real delta : {sum(sols)-items[i]}")
    print(f"{sols=}")
    [coins.remove(coin) for coin in sols]
    print(f"{coins=}")
    print(f"sums : {sum(coins), sum(items[i+1:])}")
    print("-"*105)

    ts = 0

    for coin in sols:
        ts += coin
        #print(f"{ts=}")
        instructionList.append(b"Insert " + str(coinMap.get(coin) + 1).encode())
        balanceList.append(b"Balance: " + str((ts)).encode() + b"\n")

    instructionList.append(b"Buy " + str(itemMap.get(items[i]) + 1).encode())
    balanceList.append(b'Balance: 0\n')

#print(f"{instructionList=}")
#print(f"{balanceList=}")

for instruction, balance in zip(instructionList, balanceList):
    #print(f"{instruction=}, {balance=}")
    r.sendline(instruction)
    r.recvuntil(balance)

print(r.recvall())

#b'flag{b40m1k3_15_4_f4rm3r_663471478}\n\n'

import textwrap

fs = "20_a1qti0]n/5f642kb\\2`qq4\\0q"
assert len(fs) == (33-5) == 28
ro = fs[28//2:][::-1] + fs[:28//2]

tl = textwrap.wrap(ro, len(ro)//2)
h1, h2 = tl[1][::-1], tl[0]

stackOut = ""
for i in range(len(h1)):
    stackOut = h1[i] + h2[i] + stackOut

flag = ""
wrap = 0
for c in list(map(ord, list(stackOut))):
    flag = chr(c+wrap) + flag
    wrap += 1
    if wrap == 4: wrap = 0

print("flag{" + flag + "}")
#flag{th15_15nt_r0ck3t_sc1nc3_7272}

from Crypto.Util.number import *
import random
flag = open('flag.txt','rb').read()
pt = bytes_to_long(flag)
bits = 768
p,q = getPrime(bits),getPrime(bits)
n = p*q
e = 0x10001
print(pow(pt,e,n))
bit_p = bin(p)[2:]
bit_q = bin(q)[2:]
parts = [bit_p[0:bits//3],bit_p[bits//3:2*bits//3],bit_p[2*bits//3:bits],bit_q[0:bits//3],bit_q[bits//3:2*bits//3],bit_q[2*bits//3:bits]]
random.shuffle(parts)
print(parts)

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

ct = 54794426723900547461854843163768660308115034417111329528183606035659639395104723918632912086419836023341428265596988959206660015436864401403237748771765948022232575597127381504670391300908215025163138869313954305720403722718214862988965792884236612959443476803344992121865817757791519151566895512058656532409472494022672998848036223706004788146906885182892250477746430460414866512005225936680732094537985671236900243908114730784290372829952741399684135984046796
rb = ['0100101100001100010110110001000001001110010110110011101111100001101100000101000011111000101110011010010100101100011111000000101010011101100101010000101101110100100010101011100110001010001000000001000110000111011110011001101111110000100010000110000001110011', '1100001100001100111110011110110101001100100000000100000100011110110010010101000011111111000100001000111001100110010010010011110110110010010110110100010110100011011100101001100001010111000100000110101010101011011110110110101010110100011110010000101010000111', '1000100010110110010100111010100100111000100111100101100001011111100011000111110011101011011011100000101011000111010110010010011110100100110000001101110111001000000111100111011011000101010001111101000111100111110010011101011111100100111111011011110110101111', '1111001101111101111111111111001010001111100010100000010110011011100000000110010110000011011110101110001000001111110101101101111000000111101111111000011101011010000110111100000110000001001101101010100000010011000100010111100001011000101101111000101101110100', '1100100000100001010111110010000011000010100110101111100100011010111111110100011011111100001011101001010000100111100011100111000101110001001011110000000000000000000110111100000111100000111111010110010011000010011000110111001010000110011011111101011110000101', '0001101000011011010011100100000011010101110110111001111011000001010101101111110100011011010011111010001111011011100011111110101110101101111100100011111110011111010100001100011000111011010111110101000011110101011110110001011110001111011001101100110100000101']

possibleCombs = [i for i in permutations(rb, 3)]
possibleCombs = [int(''.join(i), 2) for i in possibleCombs]

for i in tqdm(range(len(possibleCombs))):
    for j in range(i+1, len(possibleCombs)):
        p, q = possibleCombs[i], possibleCombs[j]
        n = p * q
        φ = (p-1) * (q-1)
        e = 0x10001
        d = pow(e, -1, φ)
        pt = pow(ct, d, n)
        if pow(pt, e, n) == ct:
            print(long_to_bytes(pt))
            exit()

#b'flag{flbg{flcg{fldg{fleg}}}}'

import ast
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
from pwn import *

debug = False
r = remote("travelling-salesman.hsctf.com", 1337, level = 'debug' if debug else None)

def getDM(dl):
    dm = [[0] * len(dl) for i in range(len(dl))]
    for i in range(len(dm)):
        for j in range(len(dm)):
            dm[i][j] = abs(dl[i]-dl[j])
    #print(f"{dm=}")
    return dm

#https://developers.google.com/optimization/routing/tsp

def create_data_model(dl):
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = getDM(dl)
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

def get_routes(solution, routing, manager):
  """Get vehicle routes from a solution and store them in an array."""
  # Get vehicle routes and store them in a two dimensional array whose
  # i,j entry is the jth location visited by vehicle i along its route.
  routes = []
  for route_nbr in range(routing.vehicles()):
    index = routing.Start(route_nbr)
    route = [manager.IndexToNode(index)]
    while not routing.IsEnd(index):
      index = solution.Value(routing.NextVar(index))
      route.append(manager.IndexToNode(index))
    routes.append(route)
  return routes

r.recvuntil('\n')

for i in range(5):

    dl = [0] + ast.literal_eval(r.recvline().decode())
    #print(dl, type(dl))


    data = create_data_model(dl)
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                        data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)



    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)



    solution = routing.SolveWithParameters(search_parameters)
    routes = get_routes(solution, routing, manager)

    # Display the routes.
    solChosen = []
    for i, route in enumerate(routes):
    #print('Route', i, route)
        solChosen = route

    toSend = ""
    for i in solChosen[1:-1]:
        toSend += str(dl[i]) + " "

    #print(f"{toSend=}")
    r.sendlineafter('order: ', toSend[:-1].encode())

print(r.recvline())
#b'flag{the_fitness_gram_pacer_test_is_a_multistage_aerobic_capacity_test_8182295882010254837}\n'

state = 1
flag = "[REDACTED]"
alphabet = "abcdefghijklmnopqrstuvwxyz"
assert(flag[0:5]+flag[-1]=="flag{}")
ciphertext = ""
for character in flag[5:-1]:
    state = (15*state+18)%29
    ciphertext+=alphabet[(alphabet.index(character)+state)%26]
print(ciphertext)

ct = 'mawhxyovhiiupukqnzdekudetmjmefkqjgmqndgtnrxqxludegwovdcdmjjhw'
alphabet = "abcdefghijklmnopqrstuvwxyz"
flag = ''
state = 1

for character in ct:
    state = (15*state+18)%29
    for i in range(26): 
        if alphabet[(i+state)%26] == character: flag += alphabet[i]

print("flag{"+flag+"}")
#flag{iguessthisiswhatyouwouldcallalinearcongruentialvigenerecipher}