Tags: number_theory 

Rating:

In function "encrypt" (of the given file "encrypt.py"), we obtain that c is 5th power (modulo n) if and only if bin_msg==0.

Using SageMath, we solved as following:
```
from Crypto.Util.number import *

ct = [42562643920113780314383992973444790297800103805L, 270201072075946607048384842706374179998728033948L, 478696150572049854490380024972284640128204244133L, 192844167117548448623167075616273228287668196099L, 560792841716349679825902951279636180636145238250L, 609530546326083345244017170945258449548367476342L, 489678905487185887435192259665065793157044014172L, 304240005390453372970201668365849620502562510335L, 34740364038564867517367958320046869858974495288L, 354113555109471172653631381634279215113682434527L, 718863418577532883711655093137508949599751843969L, 787596421749282480717164478882637423554132800363L, 60720113008236309010337225519484549198276419459L, 375395201923408015626685085916186403723767481219L, 244943660867068328293332017974114669754460799950L, 245254377618599246752522270541215491846475305056L, 705460977796046179251314443682157178194595868596L, 643564235377169835300277024686733201282999002078L, 234607559505017773285254958409145178128337317081L, 262106729400567007422999522515963227780820148794L, 796797538124170595443577280466338638337631051917L, 671130571689483222411468470907489116985896909864L, 435111105901247188918896477824036572714870144108L, 188738259458513713348227390570323255976501894794L, 403664278827800051458795932069381383638039896912L, 450453923787928667025727490997218612598163453172L, 292277050504697818600132645594451578176163553728L, 396712586707424551591625597013523562315708771732L, 828540331627768530081785707127746956851775797537L, 306245019282101610448248764660903691388195345864L, 453025904791949452652850242819131133647931405938L, 498455466273080906354302937504490578475529510082L, 433859840721423539828281915899012036045501867638L, 4112471994028549942990159234057290220962191206L, 40112171061753634650048019681832930104362512193L, 506994066996892736157621420878132367834271023830L, 475973938071686707005969066843962965834158462383L, 483148946026593897799105539179028487395599456125L, 505268286307742621241742122018316818130514068358L, 51084013105707653358881704299907347959419162099L, 156674192162499653792974439867787206150121955892L, 116222523117951616298553926526606512146234488558L, 198838985683958200338238715473735852845718594403L, 552761077482623886613362536729637129504340314588L, 691926839330848205914573034974680099885594312359L, 533225574397822744447709196006479643432782746132L, 525069593329907206227192936432787959213477895494L, 574434273131566696574031958682215241461817125675L, 22971482101603880003567523316999669428901594086L, 415902134749361763242694778914875182215876697014L, 25481189327724499974328202975928332596342482407L, 806409749653502047630656641071162097281916027498L, 782739495150953778138488122166759366800784360878L, 94442051895289674789756899148894174046327631694L, 181641734203744708199456825173176266657123499807L, 60840903772324788098969124246794065320421213489L, 758393667796245465564567697624752663960576338728L, 6732911589183806346242718430982000627359130546L, 526538853135361065790441199485744413547707833102L, 13169452418822757462382920069838895938834788489L, 354264551159526034092752020219986483886957780091L, 763890973234725549738759266042572524218572268810L, 38915197197467524140953521263519944044015816676L, 356729012185507572094124074404303992692960763662L, 688935160710822672149080065664003093627178172074L, 390707470673135988461324074539218350756156234227L, 643234399905301583207285640240861813157651912695L, 206486526451835857688148677537562010548613380728L, 412547682212845496249004990275045182157219784000L, 586596463924160298483539472734795046471312794377L, 823573710837339354159625221299350410322401031709L, 699415995387530485085379798687393364287430406678L, 229385472079591809731148776566046688850677865912L, 409187618776725025866556179970352023362870372981L, 565122935290827580047237319222947875107451892822L, 793960543895031567094887608104418228949148881782L, 248282613526546833813841779078781073671096554161L, 184625905682457611988574304326798360600935828292L, 249163376695223358078209809278132837343403736414L, 346219945773967908894466481689718840158451686171L, 125348572697162313378337216926744739368205933652L, 360161339422686830433742299840394126403855057498L, 820661186304406524137071718374718559430977131504L, 271328514751805078696506404052237370921945990789L, 578924550192732328970864220370650951989184910362L, 790366482676934429301484856038963393930365397141L, 13174384137976706063457146620593936919423653154L, 669527535219694225761460923054950626237559513069L, 795644006931466412438436027675956386865843883078L, 94816506075556532038226354119900444345379903775L, 744956981517249057360969148911275811544442845027L, 559762794928370765077648338368130266624300230271L, 380155757610023881313542450314806157673664799112L, 19683776564375453605883964654879957698756254559L, 43383584999406070429416277350085499394109459126L, 144387263230719600281316819853134788477784762083L, 87949768501179906441288780703259946463864030018L, 431209645604478415485941369102530566991524490369L, 726222229627274684880162339685366010699968344905L, 112406592095148269917120485235753022005744988865L, 697437757471364977176040689280612791646014582160L, 288303739609623663737993183334403780500224944503L, 371441671537548617833261377684573395637718098377L, 73503179213393913023704937289223113070710436178L, 14278600014834517753559474524037832942635927659L, 95979312957862956641244586033112513755803077444L, 123611849060591463856666997035364759427112812349L, 250267505390780054373759212573794114332304420897L, 274331340187983766414970375369314382470309923528L, 530954278326398757599110590629998236194873705738L, 445063803639254844602118928332995402727991005526L, 477536316882356739806381795009989191971022494775L, 145806534277604580875808969952673951890456430994L, 338617094019005929131671762676393196161129291273L, 787986998792470243821397305866328174678704601832L, 797681956485293402755781130144373911193743174116L, 102568133699310747724426519505517138297342928702L, 485973235220253658819163335922664305614753222737L, 708864866282153909934399948843210933312918475225L, 308869644059764204860466118240550021785346378407L, 265134597784188972044817186771092475529959115280L, 658630862233825651846758771232193854753199783323L, 410299892119423701050427477155381392726923211285L, 6310556712134526086449137092667549852236480664L, 721490244153294996049060382571833870041784134677L, 189255620808066245253673434834382588149476325354L, 656660321216535035554868867584817446419376547800L, 227454614460719041137689443422767765867650838496L, 564044834979679073000283863743361202562615780677L, 819497725880056350642396338505462063661613081114L, 221608084786562734221253860081125113787049343286L, 65545019154510438233732307194863607751031185596L, 501764965357482269727888050687089193157839203155L, 12596049711442079696416208815415678242091492882L, 608335000655435283873776788164729624608624817344L, 769164412496263133567276017296030606229830101938L, 664392246067357098877579195261219487179986160723L, 75996028618380983622275289805057198859844565452L, 672253925254041921269524864028282672756772077887L, 10895374234330584911367787251440628566929185900L, 142938310359303082468235486875054184138048896491L, 580034759791051467570186991460531038900679165541L, 287969775416861410657459226277133443501613853261L, 283979020686970117242427425329619893769855354427L, 49347852309409910369201393348291141557656286601L, 624150486700256698789404049401551672419608893976L, 454233579238810112360216789636690941906069484L, 690476396562361518729054252655764072124449268089L, 364952245729150423326049996389508037748559889683L, 46898493332148283155094923745254689993163426686L, 721357617282368645994984755385188516191333854333L, 668358240156477324515019332670949254186522240400L, 530146560534258049207674282686131830473272127904L, 421240386903585887479293913607895739401770216131L, 131544157730297580532376112097192541317179941259L, 53769876913560242076228652083351431136553941165L, 324630132786079151774454244099857497319443044190L, 55914569733303855249647496460820458501426747612L, 356460015927961571935862199999992385930644898065L, 381970962369842965489276922281370450755149773458L, 377925988386382827724043815986127076122697666178L, 170391875451406681354914296500571079580495228122L, 500412216700342254882222529341044797546002378807L, 270482626136675206071126080144589222444978935258L, 510204515848361838813066544104229196649427634721L, 694801815446371547162777895975222045949858069418L, 739395372540171364253886631013817491306399454241L, 188905973397720824340314521621708188756348481623L, 487870658355564402820834450621197405413234278639L, 319933909357132234363354760423492914423939767405L, 263703052554121451143337156067968794709832976406L, 570885622346973806312331572767432345815012650994L, 613648216706507119609753855305736669966565489982L, 362055399017830857419118173194209585364129442109L, 464810998911591121288542168872550032794798575825L, 196427036821223400365200413058345761514591417071L, 25628609184402392719234409827173411591973261458L, 389660521648409036834014768969265025739038255604L, 384795004021400423555640099529367625348372390881L, 707289989717621963077194153935371259310016146498L, 670156226011236402401031750316704325477772529598L, 629478318010023990541972179492930924715945763382L, 420764775998999021307498556733386932841231547252L, 251295036637272900755099390296951302668662082535L, 169181615309865901082109507073231110967263343231L, 727702942882742898038421109217524091767497663579L, 83024833885016173065293040667506410015938527209L, 590299697981360913335337981554769685232278816484L, 839249169584760629344409812254395370637808942355L, 2532976737131698067709154159037178901016309877L, 827937908618358796220690459011146862691362111002L, 207856757362656702785928558342235732619155859448L, 769440512853837881195823544868309771285163168637L, 150792348186937950818307794770276348445131352633L, 406447664606606744239239241303236797113232638462L, 684929378565763960066686307141328078651822393408L, 224654949657621819479575791369530594184155735377L, 359668158337346821455429069306126150792495076312L, 426060019926904837328971794380434549817610220732L, 505900793827530726062521493253102791728579635544L, 574338323217068317021970616387654890577373082437L, 488642086812332277755648129901622844016014181036L, 782798139277588726443102861877502720631068154149L, 324941005837173666916146304702575016292154648894L, 599252796763371419729714377145026171271223602258L, 288626676593421098489763933781298880420148163084L, 467935558547944283971065855963398198551871488940L, 761714358296754159904539604281904852153669298518L, 276446988966064634125865380166049029609802351898L, 369023293814293814154164274667350587946664894323L, 717575431771607488393572799869825518074253493155L, 118574849771069306281658344868625779723252233598L, 12370452420955837433680686183877312882669690356L, 302301431161391687343955867699420163562587859945L, 195371671757690146983317782756160228746356628053L, 398747732493308984681571661499786666875939301584L, 698066685291591126425888078294753343383201876605L, 740615239592232339016993695884773933922478083470L, 106890365483452085129238401357149755728096568181L, 675424749894236876558905109629365681327887392939L, 201302679654677994076085404830210315546203833631L, 44180267617276864922134072223207783121823083760L, 124456735968311732522942481244765035866893530651L, 417097239834755904408684513793979044196227705274L, 233788505090359270398498540249276534994456393509L, 784883544295792169888524547442249976612414385390L, 263927032662315532641804497592590261948623275544L, 230408128635809022368695431658123209759525446197L, 828438163544123004635226007093619116738969501455L, 131177833362897071821531267320249645985720757061L, 282559114644612791250228142178864990076027445349L, 51535753100637770749762754865965551911906842650L, 75639553057595587596260623277885037750125179263L, 58473575929726038902167525004493155853338472174L, 644200156245117800830127150551293667263711884010L, 59336566770535954402402035001334688195109558183L, 325545043540004593614133895407411121346920176287L, 386730240555902975565127557492240699320716883276L, 107832757107482266991355321046790326277959386133L, 828353615833264639624534978723116154197590072611L, 437040243883858950708846625114604220964420978147L, 803398029066860857025331241486964965031131551855L, 576964537171426515123456361528143227570520116021L, 809583738378871906451344170063186991235371039023L, 823305093786540109619869220762083224118345164231L, 411621562624640152400201282326942360790677410663L, 231940523067486950068748404474658124358585742451L, 604140702068928167426636914613216363264491139925L, 182549530248750772516328059170083331367736115014L, 351272332765569839425323248007300819393087347081L, 808051965718020879122522501107824643411794084717L, 435313223797686028005157782836052182346489443562L, 773290097747317561689672554732697061093259735422L, 494807743119295726369579141007071491416325582655L, 374920928368387309057243128392752000439621200886L, 20308207759197365626061325015796899552114404367L, 219468272654429509419082815650800497195671108828L, 81139930848333886667752156803811140821451629059L, 569841453048534459795682040530849453115831698992L, 219815172001382756213076518296618693861215663555L, 315228832309928783802974983540753584930582247996L, 521351457638018908013070218723655643353193350239L, 837078355322582540009573068258668145024145790857L, 305949280410779965167795125684763760979096567656L, 752734535504843782529733381847990120498024803199L, 130979635848607595450001756874180120833056339272L, 127380462105684333862449267491349897546937670062L, 831464164576028236819157664155629321588853884506L, 458553646896923021292508986645409497433444903480L, 331547581789456197823262914448841887743389126588L, 687438850344432414366519941161325929797010982058L, 46814190784385113831609191671871870377062343969L, 367204250911005382086630700883675824898695572800L, 837950709225208622477048636848957743414279375406L, 755979086689398053301176627949234797669290978111L, 463929034563763591426239863240035335944307807918L, 388056079877348208051659258366423130180840108779L, 481802465454467461901032139782822670524640782774L, 701079443559078618728078108282845476374731501563L, 334745542222185197153180834408788144100538013756L, 253145560380270643162860828610515679311935720072L, 395630118318640218770711387893972244901063806635L, 208106342863019937023658673932614122363417212569L, 800934699010135610598225595151405276781918908874L, 696336112960889233518724992191716194527976985507L, 300286054927681941643313635323094504882574668063L, 458789329000502799100156566567758633503913820978L, 708175590579955723202930994812768283855064465047L, 587984734773590846183205937392451653174439236906L, 823762034931564176090815640023005894001280083927L, 524050296443714423381097945460586696978946512362L, 826146010460282803089280095111726046618296418403L, 738059115420803411392019151234924442822894137372L, 785923027603124246693527973036116119960741214026L, 252991902280292538077710740416727662292106903638L, 612730418549786530304086962840101299076730718334L, 69668983448626635123547735831825182040773807879L, 739161334792019562944848789255480347264595497250L, 426088326883952707470818191951397422806811512699L, 609894411725117311887748173369827266668614691266L, 165292756235797442318361854602140226544694739311L, 589667800107858677593289168022975113313550682848L, 640857564932560426034113458302923984027810983424L, 433295904246129548439611855874554726964056196739L, 295736828268442704674230280994652730936476162079L, 362750821004685893453136326523511170789437995781L, 589336117631319830914706810245178694288089137894L, 811399758747533046016039717227711274741061322838L, 27580861145202333471323495462147840357753419133L, 470227706417198698085667542317817787181959330535L, 584323275788057749480505550524460240732635160625L, 237827904233525417474165042101078126135986675291L, 185838249618402980174158400553291130995482918982L, 716717904900153456374864913024565035802728872046L, 299928293393029561935406197987330775735773835320L, 610584168172650199159224372380373439956634978704L, 690408099401618105598728398222166520124608190031L, 283306897206518288330461379029998212937266204548L, 817789019703352399202811822660012332372841442630L, 220127609791912011108106028754496869303560001849L, 246504269062014401534735358881601032162158759689L, 46082991319083955224175960690398710532164487906L, 212751399833511915627540175127168811177001660515L, 385250717564324096772476620548142926475688319557L, 61365581213548006550836975224755122334454850567L, 500463428035823554224310567250695080325995136096L, 61899143940365444140145428783315450062301530480L, 203025377470260666449657924180136421473514357156L, 123908476681846473673931773788947788317808065213L, 195215144275960912638932735284434043560100707418L, 133310257625037249927206630090100662665907910449L, 276367955374261543252723006408725695641217591135L, 663820798437396723050278496454824751706073882376L, 627376994406926072818386443662506537498856251729L, 807263912057381638138372982429348018327576023228L, 818554198814274015966753870605601199174333968563L, 529245620163810217622982543182351257311767464391L, 546398992629494812601212735149228626834119169658L, 788234766026477342751189473804919448998384347820L, 167271976519951808827353512125697808810338462380L, 430534784945777772222546078201421648977639348392L, 566978025835009408463135989978297395594607030631L, 727029425844280750981029116965799959144058594190L, 448139533138455217978527391597808802026293321469L, 151729712152759812390167470675728297857929105951L, 657791674324077339300884249739164923180072401180L, 424404948439217017610243837136383380191856871586L, 455777852150250746502732696760882431897002125490L, 118395806165479611207400242952156754708902219616L, 651998890970295878824168089404549122037582504955L, 318053786402730632110007904507392367956281607521L, 89256996994847882782731727353769430635891555271L, 191640633961245854939398057878203554179178922625L, 776093243824038694002940702752259227273873370266L, 604808053552832309560700585581226890424168461228L, 696457148711375718900956512475692076017562220382L, 225740711410466953926721086553814924866335860229L, 779384895686875556285208428413344125970531184120L, 80036196428413356900967644789298317424533638010L, 822496368697611448419908595847938425766407310386L, 834931499492006898642424172352707198872177553902L, 698414105277227047734122275193896168604649888702L, 529758554002809089081465457150468189507830589413L, 717258925424201058322126193594043182379350820121L, 545320778959010102117304312285631032420173177586L, 198810957950627600434822289656001469986862095348L, 396686025175354098156566844871532163846424230341L, 695402937231760183954791141361421552844300447983L, 616359789228266349699343794021003938187153822056L, 605577098887398262759634549331644256082166532624L, 601338707988632159208727568593686398013820974578L, 602334758345704224480697812073862084189082659829L, 199993895840217594422160437717413997273424537729L, 301172881601039569961892167965346000465469196938L, 270479627692150358469747722957892647453928511135L, 326335212710487507108472271822639699064648093691L, 106777921739243304370773085119576780949295942475L, 167071874552627084471353729657264563338026693956L, 197386913819707750998548688666241780705209642981L, 333989154944272765126437456969009498043248355518L, 434050250540343912275467215058298016032888176906L, 725401040393076792082841393446779306613460301273L, 727195206457435913302519991149583073712130944332L, 71590043050251237974379603651300783856190315391L, 793139264226788841507794442559678297202409093836L, 378525088022847526633162652098970409025974176857L, 64801404877308530110643631000410492805816851806L, 643972961663258149439837603423804897541649156072L, 157478292833194737519619595267874394324268309984L, 134041615706387295807480733390897871749463349268L, 461258613878623602622274059869770203247750228227L, 625872418231109115583561800171823884770612992316L, 237401566421194941434761956019939328673784029053L, 352405224268011659966413741974587740202212965590L, 116884396815801319245874245933296320636289143041L, 283195867540544834172532403440934521697373549015L, 689140484289234758370348531544928691906949176271L, 193196143026619464739760509606724898405753196236L, 67085710038260071732180539591066081368573964447L, 791794421731500760432508508849445876352096030071L, 432475128267108313460692996087695700599634295795L, 685073149783887985113269353340454247763263219124L, 335833908379012325847781848040473707739024530929L, 220612931303802409528417426553183475490460728373L, 291854819805074338140207394148645955031098744378L, 714515251507395673121930785122395634981321413798L, 724693143577584941911193410692637232099404458917L, 611243364076247112840263509691315114388391971369L, 229795860797995375715782537388782018888177477019L, 296341917462921514026327489596409707263895273191L, 309740425030881907897587814686626624055404447246L, 671631272527133996290893591609221360527257103885L, 218905811821960994832449103806857649781424376178L, 429772382896991457674660590568850053767362874075L, 250175727687874743892420590416583480995866963574L, 220396487416821216308222497372918137375558487785L, 248632603454655733234736595964105946950230116916L, 227496926861674027230311767436572791705586083714L, 519824104424885904393303337198605448578756909808L, 795103589371838503191297936262867047859443076904L, 244542828172213041199894799012547508435456165435L, 50052840614934527554894507145108176434868736721L, 539864968707154388655261925196382978215459738283L, 273582666961051735607824388845532732241288761719L, 531514886312313973773063924153516924192418657044L, 101484196383889500114457151515690119406749520478L, 404547795626034292311498435162286213193191412452L, 250171257240814875397420693184875445138996688633L, 211239841284623887225478944285253370693514862872L, 33702581727268200448000963472643896415286212021L, 727954030308555513888383002365701074524660686267L, 296372634680510180045698528854832499158025138767L, 103639178450743820451116640692980921644914754181L, 381056138816946574321553076345557659912184128071L, 220363775860108926430412133120609969043172885719L, 828380089804826191248904060499310291984337292267L, 240818837128375459115613365004393187326689178106L, 599714327776873507299886356592570412302353344127L, 514039904560736346483340269688580936191901954975L, 838405528426499141475985982949569190893885957871L, 67178744880390923276819786579857611880328181620L, 821336351518183360948635849459228489892497850605L, 465122017037822859400169939428274438908366165072L, 95264823246420773240792527458136208743710928871L, 158144519740001444337707734860202573635872827543L, 689985808396255471137327738486051869204812470986L, 550134662580703482270292485064392354509835320583L]
n = 839647959743379757835423741637185376972991646369

#by factorDB:
p1 = 716158806799958648435521
p2 = 1172432638921544069685089
assert(p1*p2)==n

R1.<x> = PolynomialRing(GF(p1))
R2.<y> = PolynomialRing(GF(p2))

res = "0b"
for c in ct:
c1 = c % p1
c2 = c % p2
f1 = x^5 - c1
f2 = y^5 - c2
if f1.roots()==[] or f2.roots()==[]: #c is NOT 5th power
res += "1"
else: #c is 5th power
res += "0"

print(long_to_bytes(int(res,2)).decode())
#shaktictf{Awesome!!YouAreANumberTheoryExpert!!KeepGoing}
```