Tags: elgamal crypto 

Rating: 2.3

We are given the output of
```py
from Crypto.Util.number import getStrongPrime, getRandomRange

N = 1024

def generateKey():
p = getStrongPrime(N)
q = (p - 1) // 2
x = getRandomRange(2, q)
g = 2
h = pow(g, x, p)
pk = (p, q, g, h)
sk = x
return (pk, sk)

def encrypt(m, pk):
(p, q, g, h) = pk
r = getRandomRange(2, q)
c1 = pow(g, r, p)
c2 = m * pow(h, r, p) % p
return (c1, c2)

def main():
with open("flag.txt") as f:
flag = f.read().strip()

pk, sk = generateKey()
with open("publickey.txt", "w") as f:
f.write(f"p = {pk[0]}\n")
f.write(f"q = {pk[1]}\n")
f.write(f"g = {pk[2]}\n")
f.write(f"h = {pk[3]}\n")

with open("ciphertext.txt", "w") as f:
for m in flag:
c = encrypt(ord(m), pk)
f.write(f"{c}\n")

if __name__ == "__main__":
main()
```

ciphtertext.txt:
```
(154594131236051398122469778674138421851072318148432545602664759228646453695729674311681424753645618679517395903930492631941130791297634184855370872601937155835855399931404858876498502490971762078520838098150077954031394997911747109750793797863354276535722232891507004167970283006377848824998711061097675972218, 44363748852203092481535090819925442943776371649509378079183111298453163707363171448578299980822071179578617152535486347808109590331077296945968878436807278919266866276172289482428101111587636201322370148862719096134783164024267642688236493728148654119723119581859726215294971873348339078960280196561670517429)
(84581978416525791849148562109631600481559587882783144138074505460391478244164016351172739701550626217181704287463929319453198566689747659920581061296702729960317090461192475301910315496099902975969694048544133009199654331203816236940170563143526464713673996671415457557762604298026222009810749692906636292773, 113346947560627547454811755108107964087931289217648601745104433683412100078708281088005827737868742243060165637708122072192488321359896177217868008149291396521433805443943446504450819296012549293834549966837826298450366621860069395636949650182911128160406486935322032990615242532666787150863095710833689094034)
(83123711882636327452350034248751542397560023144190203881835758930531648440668475475508215209977428748361853980736643188087100572870886034288704114287841561833872411588323573658194896985651067037423287073926704285029950422210263815337552634616738644386787067440771598546988191179056423303981023231832669523407, 121910846540994469406666155350803978148618607458664260477560949884691408201397231961476369803474328565614948069502682169005206527201816006111836767177058315358848673417344199398840929495778488255098835253071109983091696974872386963948710793023572230780512698272597225067606884128220154541585868915133241046408)
(119469333089951634424434703388863165083702315862427640441213027659681237172285104638016368215372001464638875552995692636200540555053732731837755902171137859684950669527477527651017781655806523188335501982845894048587670232079667107988716591837831676737961970600001770434587293231589791845450617078952936027765, 97556816704601122206058874622264661177659648061129152273602748426093356393502265338248101905057302126859997817073709453085067099131776573825659857488995124659481373593306075872213589108789249007933394214907988480372520810922841761150365922782754567406830213970979830114992763640950612609950943842842830472548)
(65521981756823948573587157650182583024818624488253141827788913602398448557391048980158801079544224810709626006617254797603031358513609919665785482377490958353806809541971599432186820054225433780632124813756875665353098589687103087770131700064134421033083202252243449761980929252753576644101317122821649657426, 74886385991186973168553223799964175838112157336927723801135051549586092913485664284540459151175839877274840150253936604267568006704887056439198131195174400089554187867617610896006810843083740312583052960473939956564378265885684381554074154428452906319594139478641253467070949184235419204049152699837464017772)
(2523565031347545588306200964965122998877204912167823850702143125420546246762531235607188103998294294871108312956034404147320096202994255351685153528007848323900147750875166192081016309532465193197819102599525786527158819635508713997299340276379919992500313419289605032902940625878811437753068054382417708075, 108015665083700233231740913155609215302725278856993860419775264420762920507907502983570613938585747292576515603810894684413176015441324230602394469104007306725725139568537618959680715084359857403832399885857624370375218598790033230643140989011183998020799838560082537180825446625491098373992423901133610140295)
(88781656801539498309118997276498388590672637027191083281249963997705694933052386839743250074205626205488184536189344944926911453866363695558890663165826992655739888743750317338118720837474844434906535297925772427881479338447612678452907074840784781258879829221927932982373405499345521069602471178707261033102, 107861325312776396920647244495033406332054655253501189879668625179139981023788658429456713651042013524098603464741628098818035735177718924448570435005852587955650667306758813752915141638939757236288802868465106847850148397866699841750173711053282972101118068093480673405533027047157895641368285386156801987251)
(55395714120242618020730064372359106464143250780226864226273837591299398227731882536373197487643693704239680478844165962468789265883320716335753722202465332198416136300993875778020310192473861098853614956877261779156556242153275597969212339119342001920479240103764114910231373149835723227733535417024318034359, 105426171627222455245855397195085521886133861275304373691251009950792329848433698162374598704152478336999601050203223586977341508585859285668689614979388658481828719783815788114519045733793350300787190437857205526520705505872979564698953151387481845186846804979503166195672038862861351498357457942585149198344)
(8642104426829673431078853658782321221582974557527701057859746659442726983957882322247933998419378931657483440432885603344483047632749077297796614661770152955979899193211127935611999944633368227236436556442362556276281039534333816394136856817064864830316579702657602376656407586946621056533506581916360426218, 161808664765907299136476829780534629986697821301585729811109913518744190502601352024162128966072984477991613651924404022178262541276372826769987274045692683479282970790731503303999986308225062363507910086830357160929571189664481769364505595735559714180107750922779735401379345458963773584335808483918195457281)
(36981047228164671081044204325154459307342130689468814608464928785359446320735241620380690353922545693443817975246590119260247992928766321622745844018255206143230435348922893081404078041822280770481222873522572535018849805084104137501316815205757724679417230914700388003965536372454477707558707910912979947861, 62991188725377507664132162101886148678326012123891355794133123335138351740468072956325756565712591569458813279033231651725648192747050119434056521982826772829372064703054023037371002209282807263996342760516810457049754164176161061371502331442686660505808762304048978615775439246360339375868874696178902543996)
(57679671417585297961185841191925168669282046674488520101018442405072897927083057336331302511021320924396102293334574895886322543220089474154278438091257880664059932261527355373381952626950103022925727804111592221383176963653346921128292877577986954130444040156840900325038865806856509069447445502272958789318, 101353226064500827560061085619329559091383337401747542292180168349821019218999129845317267316090184600756428173641289033720460462022821077358662117160015996461254312182250935503233602855506754636411347953832834662977612375747729951410839839928390063658100674991286197571189435466916237563950255610304762704921)
(69802306299260678317179499287171259321940389306709206245822636833181330355788857187558578800606038940405032863067583087902259472787556442490420626068734329478158612023216037892039960995169873142849496123210555212199036046685068968850117381719254810792793384651251643298224226592178377808942523250105695988826, 102136232075027584255018740192514452281529371020120854448972188777937350512971677848524151335601859998235281688259791578863543930285803398030022090523395377812094199069657759537291086685272191170813603084976933349149366697016557372542710681122101903685306304182825357875442331126132756054955858149440039156853)
(39595153196016259018280354260509753640881529539762866146347223921960762350108861352726448578859514878767002449672982244940116676593297719213466121663863526918695670751799469261029722251548050895696175491751693154794328556781338579491975270896564260173253615298184138775818953190212118471795200451855056447409, 94084465158533987476422486122335461598247902528747143408229625664167501184831233480215822653745466618068278313518621426079951864611254068589094705088417512890244306274822989027969348151329547062475692610110062779267489144377154512793006698809779370753694489316361937704241597456954006081609702534340569291481)
(75394464839043403437783930663482521549412455814010404807928391619248092923302666934349591353780937271900670490565973994260941289948705876396851597059033239064178885750211791264888534276934860511854587800059655608528094728945333819043518211035304080662260756281885300132771897388581231387354966252386377045238, 138618614787337627945256033229672266364705950650007136805020789787212799447566817020178805659321516262913647068819207148892490942363622125582619296518876359853525775583923111340890750939089244992063211936618676712067568543380237981077231025289049706530443148229328205684906951402113927216884677454769304196699)
(132032563192394073150530909025269843683161307472924445278559083347163097069830735300257308566742780487816143606749045368310691290737413182433344202428026959248481341762440550344509735519535592208846802935367004862758170410016004883904992974950838685978929874514342728686439881142199624626750918529469635563321, 9065900051198229086773004439743978515341322292301983634410489124276260880997938626617629716235646690592074326557516047817116230304656587966554479812628729995890305060347371873654866171180248278169958045138525339976773894617793070276063579653663022802943272573093450676521291181073872623090488910340088077629)
(97565760879291700001499336741578901511981812089605838288695387443979926491039126098889846265592966682400865112311263815725933675971642893573859499847168808450636883055230959362432087485985221941722500394953685473278187120919941821292992506059426814247373197041763342550762451139424785216435844001157956841244, 134002655762880290549769287373315987568889667948277144708231176775587522686407255215354893377943002907866056189483709344142570235156619619794992947439612636840957845086264360847439668970471700595788115399742977192091561172540407118851550668822234495139367318963325524367434896177003350114092706012356569740066)
(103529768145022263938137577627359972339409801500956207697928756808910757835139356771322609020268295532051096133078048184639676527529990950128410978714606212424500058575200389693139314410066490675831711135633224386353159707572855954791544392479459389447394769379533016572389253079986576520265185626659952494958, 151351383848355089235825918026149330837514022155698833043458586769911933423913980092515888634181212557981820914607071440792981907912128303421883310548622137137667370385814662753188450744301550629281176816146598030613664355321705780818764328757057708623838727036657203212483948689327896189025641288640584412919)
(120945140879144973166003149737080975878014113156197154815734553362662321567662897021321657650150030644134145880972604736780172869055461191299364930096563795999225422403310352719820812091453560053745869425158400148159510566147468013781330671141984428019521259752582202424709445327612683633437549044443375371428, 73296563210868626477778848061494285610835612464717405107450241946563034822555394999629787460198908388653510540555688025896870655943938359940382235224823876084414993225524666400190733126593664556550666146878117942398348288493942675465210314159323583910526333015656290955102336688101456040829644843875631349432)
(116968088309142255086178103146819784046830034880566988985981886205104002367586508999123574266611433239268777053038150371931633137389917504904961875211207570085130381332966037945571483768486120688529240632091267401140892184360269802487236603280311498610072991600797656110467043629743647708461958885162143468707, 123366124374059370843999848160729655260151778356264633835177214345073089393967721257176413258975336472914210267670747028664491109235708088996526620737999500733289463935573078989389939336123237841937542574316038181245793844529141559949472267233846567066052106066460307950478082103931657397795865557821293676936)
(143341934276362038844073332332734384029414312479996952240738356251479376286454747460172185441084727201353730701521243145889262698990362360306552718865359580371918908996123384755458385813247701865019323944280101197470965504871468681619368779290683999921211756869992281731500423127944157567673270980132331330062, 52834141498083844394464495371654901457632588643645374732530014279925327791317557442462849515815234936421207906717612701376348274565224712890182729166343117654998931773789495866398459218647474735093908105258773875242009284904391463558708275326964868748158793390046054583856548480657972448045717994076708549473)
(123198978637594842976767955461502603885870536629500365430144624887278651751266476244812165776706173780263132739477811598035546222252222837619265487344523076266818993385568310220256616460012023658034477688980063588563876268117503465667498984794126151310970765962221822138340724090157163652559917545078781877595, 3640015615942159973285516273418933593102387716512596985884945666930171259274068658427803905904263687276476607752986107788949612103284293175404820611170347132951858266014167042304618019417282558493494597379740448175389791125195454319470288701234418320322342917167572161799872891355311743634907977495164235449)
(105788410973293493662821259434306645885639250856306304321531664441660025221120938340158758175890007083264940949990179950495266247703770600144152533899970412310474968605979502400544829126298355006572679993031474646754081452769459990708035297065232726123419191805199700375391024381206232259395934588182517795123, 132463544290196419468622335184582422447149391267271743220872673662688758800784836854422040021745707951534156624153334532576638640709143455051507167092003993755148423888236289078026609719953433043281514665466607826435582250450936715666723142521253236703714658012425801811409343980541684980211575491168667283068)
(109193012134882727823826510835873060971431727180920029300488468524219984166993248017025358444974139286476831654025419383723291030111734091252136169103942902211649517429999404540152103138782367950948765628140305328289789304963900029816436722146444783797447352387859899752049179555559345198285639717628645618191, 149920750857568016345552546767213856034718690954457411278380372560247413245052296376873879230916701071130083568647989819905365916636738600376369011205648536473529843849125461023969717158901785179501893088197109451619041220274466444763626146545571867908452034818340569413646773483706390704458688235413927774245)
(7098265481794598273330703803005026984546646460313483890050046187250107293124202734109658705435567582959055473163056642618798899655077325264122284026806478131845513109708746834911871400363583412025887652048009969084728374775898433425313108936119339093584684785815762493040632376353928522109599704036648149846, 12875080291375266509341885497202972056098058623358381689023178913162848826045714338851035801665826325186373293970580443999816478442948154720361232047000041262321914389220403457845871321811801763960570353638411389324583485114927878662636274583368378922481393190274391692840754043092426047172839717083564535277)
(93758968693559531882710747404672482353593333867625041400112607275561741029525332684917973659131867895857319280089363529016968195611825090755249714034826122374476356302084152598836472453385716666793950550852684912509054282509483618535814207784546094508468777865479654519353024145520952869943717496096022326586, 112034672441025916320622986793341727335560900191430325144259651289293314589668834595701767867368292951977999740170134058510158877879761867647677007248845732351691584185187069555594008950379581651061937634518255456689904357373714829503182450211898827545801448643247656358140580737160049491053413346702455534774)
(3055032410347634341204576278426247402474381969151120110103930491628238274065261043406803870780073098604369520673129191092233586673095330313917077083298352247343294284324117003207053888959414190811097239856907967233288611063247496462352491685627214428705799297242875315373515636789042231816666533808745061984, 118693670882992028768097216443608593045057192354274204779313183539991556007263567599750161271511491733075472427140130195127714658147914360082039403727530045063847891685174565783835661452909725684120522566035018006601723915352738967375154618275544091895934991444661708948578800607823945837421761361008752012534)
(84811631445469397421235226094439761313793864765732194300122886504333057777601851311663848638922114313270784580759163743616055455154864273576825496867496170354880880228990531238075872096817854201016317036741777433538613158426133101994414595983273248700138345952515871234437503805423345629143001108945777974447, 15724480325404832981193726624183361885761238249388276367226628153475535901691312090455799230056690564416877382303886933659365918355771732829530929018770267182300287154651416209679715339902257795407491492438677838913124981572904117128946456472260397376162386605706344441791634410443894581541557341387745881484)
(140666514291544951845301528430565246372749111622554716678948759243201758949269724993684696146498382214160763733959959594166143599555609487776652823087011612871841839344564538672938058739670192639890586179606293671266933101701007721841920263503668190405390518967887120706325536786675302759681721773014298952302, 158725887594128820074422720427412300209589962947147437399038873445926989777486725634962055596039724613203664111933988395148937529482190726355355347314159111913317708493691792008367314184278304191517471617053477901375291053349346586448476059534059544732516395032916561206671441362468399296088483759630852434453)
(120553030992641945265663835234040708082086256090807935385759821031531180617105557861413817323476535929945588753085102202000691573149957481525269286373128292282128832317372386439711153942288533396308111221042918649915179088618984256288206830956906845158025815252550445399418631020453115181594757351336921093901, 27869942295856554253014638523369302143969130442944245215495814322450778321797274345427790791778503148645582276506849101656089604547143937745168653032233914611869013181223694832705833918626580879647142338101145251952788775811631453663408615378531115338326600133194851103139581728391070834872415484543735973632)
(35635872423088087506832743649310576252122605630102597418389006309248513305164278073978230841092564331869804713099382714012467053211423533523486624652506062720888459266162783228312751458688294243433717478440219681601310239658363977361581766479443032365881544670223649480314006791473045439454895922948679771255, 136800097531495601417679910799281887799281364078222180955774334712396147212229851421022735280503360643224610893118004898143876155557896035257059829461734588037740271636378142718120170741006591172108599902515306585752624916123103563841649436464601336355458339459629477707342535597252853018771409934975595793500)
(151896265422901254674819227148293638093660658088411751524100037576323433893467708249034199298365742137527166632266370086997839638430255122050660228789216754423183702466040250688225339464741855678127439689330681844203984649791094140711112636544655083358235924509637800274344509980242192799595983890420679108413, 140261181384454904491176257077369183535478448489716977976117892271599659492128215878829818848307037753006821082896294438205678878134469208055132245752814418716976639733402079478990671897164331034243170568772173562948635246904528587971840708103601046308393964942861483298377282652277330357369461886484041172122)
(116820810751414697924466032067332327847731451753286258580113851089045377688125527555188982374520715079410169822202877682844219040671157640445701537375683180316744526698745905968935963849947533206878881585825489326335307107078930378135041393151339792658127235370845201425239018123893576142931529014903422691670, 89689646021678849678350583413897698060768133262723028461620283143435746296845854553815647065348986736912130286504453411777602434844749699042804008079449146070406173567981037175058766307843616451461715995991320837154441561167658640651766198063028636339605702033693140005902774181798222987772275472488063114309)
(59849604197527516274109586313863419807891248251398359101465810390490851589920399847500336508342857905077775731704879581785301940929097410504238469581171935748188967835122366282057025466769031448756462573514161501939577597618925152797546892757476683117169355373879700139586713312186365770511858019758362346491, 45181653090338528619928928230444517546907894359110504770739278681333389069376474450264941967992100515149716892046415724101381637058801525282208283766547017551624009970908501515235355397668164942817672820944031216852299434729624709371360057664482393257477997154154515026043285503770468076610611437001709339167)
(57792582061526001339349590010493810469599698853543195640264303382096303864716673810891344892321132278591882089199897797735947459003361344544495846137321371880373232063980201996888104188471620674056294351067751445051526266491733406565984340562624280173255031035428985258332839640719190871134802330708033661378, 12341617301299884646371766724285245021003174792806234047329519087418933801543813602159105488358365246436512450409221993121441514623760143282031483744255460856381267820012128187076909715726759991930258268891843343550931007057688221811916506496581324011491482071132079286090569004658019763260592541755916915458)
(117495379423341092994615587275930076141513083545390630587452811969318932769394048128681364137235497452313955491198199478192825103168352509703147849562162296564853360466930901824627583839412980384308322222247172622833980010896269425391888156785886941125116288068360606698050772326270544162717186535406273050795, 68057960744862104087732399736275647739388138675586714568210271728910102382303740279161567993613289911524707361820741240073483275037061115376987717678732711598648512376650631489102355094133273027481453332915409094184704074544014474289714019960505478825780421587042120836372440324615934435695692169544578211825)
(20585641714624873137572423423094184527478456079378630978816208395095488253065881986498553723299825623610950515398932583819410175986206858220581630504061890277936668232708921503764778301577175762898126959011614709656904425761704194166577870504369829943754955047795494468466613632362830172689504166495960292225, 115230456431600875296771931001094702152598918496410485928638983826694359798339364651603229007892451976693196284462868231185889721860836216297362243874511237949704526622699600077343514808481927220770864777293585548688447787765197228430604402835444508848680541724927937990266175469320028315455130137057292338111)
(146656883867569566845094385797856728037334266322147107310276283267635898614553746609515175800069919624097736312587516804562117347412749163238376248381468399118457157955323670921774665392973195636623516214324386873055791889505406905473369852689326839776109365958975780413603173051470960848347867638696105377209, 109539117456570133111602283670938441506631964210782229176505717805827394181507452017087961633258685758931999859172467889257825704492556637314265216040845120379127195473295608257900108647546498946826452873372745101569867190973486824207319540015594164952744167324295930170973318917308801872252279364788666883391)
(129432459007763280706881805985983339542743075491537980969631524089159539396459575310052894085678284245804445958268539018142649546710061215946096408139314417049273072440976521633081410743310074470569016787299700565419176201410348712153046942243064591259874123548119730547584365134580972177035606940619910780619, 58682881956778753107398183315886547483967346182724906657992954880155559140860945383848683623192577692326472082121211761051576315024633143442320998518110301565041382312093727307957243498669996840539510903416039142336089962289864156909151920240930745450615606506221223940817883392817889296202313691535918974307)
(127231649301857541741933096935613371249533227212448764816075795695098612460738272852146144551229942749913938256437176736544212339589187765441552236377937327397398697087397388525801551934706462483687995998083572412151950387884830933111077150730107625534943054526068997280134513866768456401931385759905092219101, 1171922948948998100619180827678261157161854888257328818499197895286981037604686802024624625307215518553909965439273407589159879101535090818413690332304677779273895621023669469240284201802452732417273158004433698295549952252107857469965279959362364571486790002960456883622842937755286757479027024345274850477)
(146338862223370816232153151611486624919084420541412497832202829620460734490748811834316786036544720161676918215319399659178130191554981104905254409101890663170446596836101974586696639192192610111547736199821970450384091568092574673695775785084808996436094026090445647326849005828535687286605650513281319491805, 49064722531053728080331877826568616723598230176398522225184887348933798100021767047634599611152712306236381897647424794541299967888508376523353407084921686094222505931936286363571016276419955834455736527485951672266665790111497022870877740179388065470138223634819714209444619023957270301867223850316219445082)
(115419093779094038235019841326957166889916065696317936634859822560004336149456843350707830118497658726767542697133260400057539488704991177715943187377250207728099981552803703578086707150285746765165806111550492055210102416772607526289519439592816764135322110116200605223138454469408193849211255004536863649263, 17864652861710933985178169823274492895711564946785811547342618079423941329537426085303363105145236721075827801961695877729392650028055044113112542100738742396148105511891463799440476505688237649869857924542396892887855612357242985432823137840589950793395437498515420657406115425080671908529660230900219720240)
(140740352308788058090493143586681251570601935381785705797581095519634908997976824892578701304307639870233555947511425437704626906748766078161453223407813217883441859819369358327703352767467031341000355221880633244108470952407906912747478525079380223385215446823852775442779431121200351154365010285556471652628, 92116929679591666827272951394172422940169073630667156533393339005259842951816422462722090045643296443855302740906979401389205194227636972201216764802351328441254402927331431113005740302838911417655208411610740716184891633395734467052371347720818434430155321983763829596868938815593125443517806571026276024197)
(141342609761486446213601392516714356307543927129615928226520204216476264406647060536052391013288502035483184419287252373632842174595789920058735183073283014989123552499380675398339388858606434904914090747116668260486182321593039728374639710730375458055987142180111295328154326853668155152523983381253260625673, 10794480359969278837964551913878832363858072907197261114286688711455592489220686451014862860586719177548316197552889238736479473087480156317155383737574195540121019666681611307857960788768110412194206059704769091990550577538918079670395214172682386351860389646039888992774391817614615444362585312329452317686)
(62004410894939962544271129802814967555279288142552395587608453562599803630653343858646741807830194827679662272049629233273518401309783015292863034288653327957868607087422655832440292976491806846933447325497497677582399735244599078109333905718286526408999039998951993624826442446829323264403041647301870621431, 152979663549637514432867537628032686711438941718112767123030410165768790471181786078334685515142364109951739258806232677057637197633156973728886058937677028179826940026504836925002877727133732429944798462168796747794998733639251741723000549137183963359463689610080006564774550422376879095222571135855113647388)
(20038755851802059289547411234200210328292543431141827093569854458331419063511848850740098040286302630606612110463656004057571460567760483318078318513421104188951944574953439394170556012180727950458561188060603088676199437238048841691688811840538249190557861364743682026686259635574463596655413885565907335193, 27881619008761711703631317474823867570110913924216472429805154619344754622757315181325879303496238686661814357126357594236805248930447286336205650119376816262074270156030738927045059537178161038331186871670287058264537060068906713395498852406029938110873692125805216869306989186627463660574137841623489460124)
(108378744322597712446677197294300180417328518790137121261304826544668902077337201989026581107553676047344528879253447085800287645092167835711779757347260073666235778487538248839603873769519047388797297976494877546010908899326175906218387554335718117430458961050690402779211695417136933795716121702346841617280, 70859681954413872282060123341836795766894478205721795077178430598501005481383021979099242020129220640495498789268479756674123094395779941412502791135275434524551672429190210617750436813810890489883473124684850139451269563318841888390307453892691337582170348977778797244339839204988256537990273761450689339277)
(119841171787343326390239990940034171953472334479255354944793291078195191980360055083821123662164256584391339802541700964926747059828430178282844528083852683296272488514516275346747432810137302650303084174615601885587568371727999297355909836064051473624485952139763048036035334632664268698714950048927782283456, 144833366502183263033077705550394544372205061060106930087050778837999901242007878291097313707362428425966235908602907454017563492301395455221809308608973214072238656949359528998437689101992261641206215150998850987167654176897056512078459317003716365227583609539283805952508608926530437852968299764544476982930)
(13738735538526218610475911112697867643942577661856493106150196838443619331981487082061268056602655349954061365156667473916658338339424554277998504813438083337153079125498135237811368006522545753895593289547125356219877680204830546251163949286301984659471585016402577150776638415715735342430003925720872364494, 13390021164698662764505803643460774127050040096210664618202424644027121858012103813958576656897394869775430199974942389668147357283201580793921659615566092730070762189755985112295602158574553354261104872438768039971462004427294889480192146723811273839427033540100389974215795961640059679078534010275137106630)
(3150039013183848677831485352109235365677188875756836022060597336995551374130449094633717935582803890606322873119819375712304677083953460886409249339696976891175258749014356765903395490560137969589375251568266417916043849388148959523085388964895518374869884741627481072356862250536852863226741008881499342569, 21125710656316321890918209864527185653629702949959796515445683697345013177757298524810352708940780669619987489545742717424565456265578850579249895867763979298799221886523170611940641590728475595415356528823155263658740282769524101667996350586216236843444998716341057238350777856596191740322942126207146053205)
(26464385602461411165080154827749097079702292155710868556032045098145511679541409075644181460702015637654374557758270266660867383928236389810175699024233526375947020191719464748196529177534554341939924614150315598278972729544741796267703144036554585046239646510930800586130958532137825403637870748774440222521, 26565163504247799270039086511878262655925127093027341883327206806886367830044560460752857235720023945098408702992039672828864073150501759375666065944137300586423579949562438185044759180549930859217500952921705433113938676840572018477199850714589679212884703369073412437398139340649443886994283651634906296925)
(61166647923038356432612003934532415879355662326310424041824825339572350672975847278934148816026889921078229147050505882423282282366428802172468503124774295898120662532183528776918304416107928026674190717853428717174562877738052377007284563704868323487327067701568371888721387894229424379524245669264368855875, 33448852708522208062358859727933394206854852114940871055389612245970573253138470442952086196798020558494274089047116607030310880258375914643333309604290836588437012960943829785759495063532768753094629827407791948195101966527088192804893197765375622527814603718414979824730054068897658778883870227994644008068)
(90878388307319580784872456481401919808781069311071608430297514160335127444404764556432164179264237249115031812058483264929452725559190370448647848358209720134933732330728398330080435519080250897045328093572093229709728395637906735190609706420543826209819175824825499167010259291273115299338515107136048887487, 85383985252792101089981105638274908994850835594403924427146285991411137186172649878521039040087461770670712982671306252698214016689272924023022074049092085874392848862995521395386186262741302119140930185885792535897543859412026478181670398573044340282470823184549221255220652199877626770048433978089212554379)
(146490083065673552012706985554096139351309343687189370518192874032208610031320452053430129467484622032280618621917407042816180009958656865923345113522181085470059431546454218424310258280144081401575068562029329625153938872001986620046795065387109385267866114463334214895222885119239012882989276128107785650061, 104409520838124313357488462171322869694755717198542661367520640602902199184690105639553171123292272760958017496069309952668498150588846820302434184020218781728775605080895263186300107293704616661912759358000040628997324540481289302021008155436120619534548297597507985106058086672227223982763078841107102560375)
(3647049597173105269770523850014664620416833777086632199202272599126545712345520652224644745010355094549516763226403409963216990965131140154759840613942417611418858250276155267785849585826541686302564119662254977526726579926569015815100567091605666432678799298716456167400345601517500588984248646653223656629, 49535772217299786278654386101221181801728818704713574708993139877888721874318843695988695968336594422702009274687377988598024110900938398527487081977993280927836069969777471294171111030810839372816250656150115579902112801808937080695143463534890427667396807700572073899129801961219607778323937923179995825356)
(105372396028917022785116007341819664362697031593635617185708303614783267729132251411703053778219877506559944878375482943658474062743895034070775557724722127978037428615282691709669531495459510218886832509371731778391354272301887123656891464915639283726796876115840791516935675952286992710570528645594505772020, 141937472617856074433523304720225158981834599743709248954077273079604422821351362250866226354709455275203471109351230620985786278965567223284721270682258003006203976678536854093867091413944490638681801510530716707344229080947724265978203029521937292524572470889045533841984200823689223511345055375841379477028)
(71929836487828283933844798312248228823257940293158917610147992723679356198058643433405001376183220857635898954195326893223396398984927188070746258452835958161437436187204573395605497151711356428590217930193735006866638515579054233863666542834509538238757938170024142337012680731262233808688799678566671187060, 4309461013784518277764976602428177369904105140442379932257210399940026899700166351922350954799336384657060214230423523274762494988359525050542210702691361574373019304872698829904759892483476555111035814368920509648318740956348797394210949418101038899662947274499147071922586206379331389433530895805425815175)
(98811907562450623851274092837809466919224338219044115729218365506871490538181859303653940239876474699164554788069608754410248206818856015640088541420840931191946515671759279927990448786500292909725336130026829955730477115385265540892509952306951442518883789093067915681055055217417453179491344936940034271480, 84143515899496116188572113192956599180605800840583245499558378243129551645054180526055740867850212838153732376534522755264502845106155319362772564088947736715818142141386150312406464719188138565952813892981635683358727735077665428343353532858311885576150172493246357296786729463740630558259221006065710943501)
(26708737974612276419922995162192492010511419226590145035950025586061621611259219947224375750113155159643901054215416965695705156598018072720635611537237065998373851678691541340989433509236606144831612537895993812365637315589275631025792039990287807141000570322621413702392098952115460208182011936510846562207, 87901373774417838880214066349936457615092546021356297667848807737620026567747745459679183049363243466909335843651016514924416545099248010626761146828045201541022376344959906988598168639020804604491706613660588967437590390806716793860609305334009439169482642211756505764611602001883105007307478590330498547242)
(146228803439093971820808193766117171244427085304883778075026034125166600588010260299842786837511869251660559330189223385217075162184553167318562222415559055120833544873707022961372703097200523802972523991190823578991375231521760712112760544288269950810926160300334194835046357777757230869852863726507855678915, 167480304235996443055255759453438063453563073467499452336588285845734119883452453662859194339871886917451228490472707892284938448832620996251066814997425932053307695472790403686713653164418967893130800046172289403778052809807179586084096217390522709149374897321050210709359938389600024556229365102683195684174)
(147193349057010313568073091303650091084413011626739513111445678749936148009895760111430589635514339703072878652858517154276039191719332708977400824904283917822602277193527486680879118687582434726226978414832051811168982139564680023399692632036712492973829722144259616731877492844363125437809543718977077459086, 146084265797822316406316746693979455674734040949827132573720418487380124168241258690229342350123964958339210983851557172825329877815687976647778017423147989068018853060571219726119906157412160354052367907223775899759452351906939288834516186994159326970635757529144960353585418010592927867535353922147451984878)
(92819518855081475760443095985615771901409019051807350965975972979805795389986448134441936058029650361572345759476376254452103235379928412842801268881653185079667538383738815438268943142667054667820205690407480959439139363571023994210623313845855467952067877773408021424755370040529631825411114163069344422407, 46190864327906453154611266064375776586334219588391329679304794595736675656175748273553563201549527474891258814280378307941789756595542784601646510175697737756889919309479769607660042409418056106801321534848079023022267572588104342592592398158699567730318958361885411809544161995545855589660626065463740407771)
(167421647267342232276260618810765757844969973638630104591364840548026828626549964933856060113426562057417612575744609090267213155911030131957555444216107129394952471286820309567448048470152499493454605616189910456930770182818996818491437531387770152748239962886689498888395694085300623113905217931497509389689, 26718510726692414470313828281340834947123503722812889003158226782887742601516852075878907197839819350811199621848257910275462818343717768939741763296168491009301152747353575517403674820346102642710417072536162527628295659047823421110809522697010455743946461817451923373433185526165223247754054953124685431369)
(40476616511457751786233544603755926127927532186060663729479110303790321524100736778252856011458314623565481959334278117908052328408321150823199419072367518000347063514046176855968498503959119606640680281841923600382914216220112943548704298940114099524627362876381796579789791827385789886230420691371474973471, 101364468917449777887732700115592955967787320454406254340451191577471091479692400260814121698519258809780036630826827604061290378943661109123156527499395488921061814512520056607918669711042768972514778337813223263629741548786012900177462585732744353347749583848249679591301430724242720499516727783673133853192)
(51374977617042798309547437698820705159102830277228800018000387276714921885101246042628607417939456322822951770362952989257537092293105388949007456002523613601165569556601401339361267086033577669719471759347223720152892636178336665053405881062402955894642828622564202122157526037570609192607799757488229873625, 123885371224757097679222099441433542536754114212216764666183883669017288884505871547392887797352016271261958692154627325391473158582613752515244794384499733039295218507792070225385607859342907932808430198775513724409520360876998567053350536209939028010470567979966788875200515713430527591354948563623886967728)
(147399908594819912891143422636078272238826292945788707924225819651238365763869276517354537103874153143796410858959832351771475255824024608583818026226238616325888767928642514522031346822597755011972413529898226803309643097634474325724031263338566924224504144530616822473038266918488089741561764092574680297274, 92028574479890468322147036104197595982614881169297982196963758758067652136178653493514758929480828274185743082273133749362558356674921889616357033026578559807279827574874693407571370425931042959838038149188791394524515532996182016321373277283267279895228894122394122992497648260359490875507384276707968029329)
(76716895196361799400806555751148886290937575841319629970564874559631244854514133775873118954116054483213041146604736174295546500831092692738118144677293822819702882664649381059941382402728595268557131055973352029256503005376277470504449856840274621705143082893139607386767739608591514747896298646213393826931, 48302806150553532282620722785658566665588519045592032922799422261343434466464403544202608793337241082150394695109228730391710232827342386548954386238365950748819130750706340379861054433700592461128968617379540856442891995675465221405142633303931751206095791322416001212786614565125035570721092889703451799745)
(859901368382621807584998989700435906046261678240075937581753883645400139044052970563747710380770995139113933517363145427558711146716907158218158967826103172485657986026725610702474603568927412492865436056020988104454463817234326958483148618155578616526519200556491703653189753233643164947909302278707178497, 67589283973069491277707924116093523725865874511581975700460494525276615256848972360647741149342010410353886528722797585938049951055795417351946598196928710938299310594694517288676852382681683443541174632705145177451072965584298249723786499941936132886906909331194625937016793606736836308639522996671045453341)
(19057276229764804637933817668387882444500553270368209610670986738110420408432057106236499567403074189842716454823528257550315612718126592567474987393385984074350687895423237589357951744549989208481612373502920747064946336829119771979421560971599831689813860552978809043110713390417668836989184510237258437065, 45753693853945544687865888971663426601472043910306747579297661450806580677534647084885241250319557756395039313112700114884219763941783122194507214925982263623410345259089340254606157541864372728323111859841440188370753194169067221448317252335167884382432153001258661199044143639061689436546620067070381840310)
(88037086461413901628497884884649307584295199664364180105053407254704230290284052187039554821497241143270341575902496498118192115686526375737864302867070001996049941402657125133599867036406021155384941605412107372887772147088296372192040482038435186137844029216586340504532391649350936747821458909363451266244, 47016682195208184445133658602308050899699511344592243090038940676018943774668906014616442429659346207807136147962103933019388547995203759363365821254933700500838070311200880578495817923768403650004374278556817840877798677572955867316863350792778593920000583906270668972117138228527114624089423859662690400799)
(22309584425291737783594756719512207832911575317055719684567318323862520092872108059761137636294787806485741764026735447733355265284481339489133102294530736855941062238055835891716868389941747463288042188003244355177120207591068639582358537963676254014286595819435901383967056900881192683567748603236980779626, 121505795083438865635206805773383564651662522482121670809231422542713169665637173935081614506491623638498518564174103716741699347261730566390972385730538451356647382290484667817808814549027939175338025888088279281815225113828950087062198183909590808735145539304730770926307094559162826630298174296269669291510)
```

The script encrypts the flag chars separately using [ElGamal](https://en.wikipedia.org/wiki/ElGamal_encryption).
But they make the mistake of not using a generator $g$ with prime order.

Factoring $p-1$ partially using sage
```py
(p-1).factor(limit=2**30) # 2 * 3 * 5 * 19 * 29499078....
```
gives prime factors $F=\{2,3,5,9\}$.
We know the order $o$ of $g$ divides $p-1$.
It seems $o=p-1$ because $g^{(p-1)/m}$ for $m\in F$ does not equal $1$.

Given $x=g^a$, we can compute $a\bmod m$ for $m\in F$ by multiplying $x$ with $g$ until $x^{(p-1)/m} = 1$, because then $g^{a(p-1)/m} = 1$ and therefore $(p-1) \mid a(p-1)/m$ and thus $m\mid a$.

```py
def res(x, m):
for i in range(m):
if pow(x, (p-1)//m, p) == 1:
return (e - i) % m
x = x * g % p
```

We build a table of `res(c, m)` for all printable chars `c` and $m\in F$.
Unfortunately, there are some collisions.

```py
char_tab = {}
for c in range(0x20, 0x7f):
k = (res(c, 2), res(c, 3), res(c, 5), res(c, 19))
if k in char_tab:
char_tab[k].append(c)
else:
char_tab[k] = [c]
```

It remains to compute `res` for the plaintext chars.
The ElGamal ciphertext for plaintext $p=g^s$ consists of $c_1 = g^r$ and $c_2 = ph^r = pg^{xr}$.
$h=g^x$ is given as part of the public key.
We can easily obtain $r\bmod m$ and $x\bmod m$ from $c_1$ and $h$.
From $c_2$ we obtain $s+xr \mod m$.
Hence, we can compute $s\bmod m$.

```py
def decode(c1, c2):
k = []
for m in facs:
a = res(c1, m)
b = res(h, m)
c = res(c2, m)
k.append((c - a * b % m) % m)
return char_tab[tuple(k)]
```

And finally compute the flag.
```py
flag = ""
for c1, c2 in C:
d = decode(c1, c2)
if len(d) == 1:
flag += chr(d[0])
else:
flag += f"[{d[0]:c}{d[1]:c}]"
print(flag)
```

```
TWCTF[G{]8d560108444cc[+3]60[+3]74[!e][Vf]544[+3][+3]d218[!e][9:]_[Vf]o[rt]_[rt]h[!e]_[Vf]i[rt]s[rt]_[rt]im[!e]_in_[9:]_[Uy][!e]a[rt]s[!e]}
```

To resolve the ambiguities, we guess that the first part is some hex string and the second part a correct sentence.

```
TWCTF{8d560108444cc360374ef54433d218e9_for_the_first_time_in_9_years!}
```