Leveled RSA

Challenge Description :

In the sequel to our cryptography challenge, John embarks on a deeper cryptographic journey as he discovers a second email with an even more intricate code. Unraveling this complex puzzle will lead him closer to unveiling the secrets of his uncle's legacy. Can John decipher the cryptic message to unlock the next chapter of his mysterious inheritance?

Author : im._.a.p

Solution :

-level 1 has a list of n,c given and e = 3. Decrypt it using hastad's broadcast attack.

#in sage
n1 = [545394152327813975627251662356063105606316337974491997295378647690615887382846479574222185770313742991341817138659024468087374639702799222795556980078412962871135642157208399755482893225016908344756760491148399064668808613965264647043153983156823158636642122298187635003705135140416384581106771445445866838902215564606282991513088309620556665381025025077916298564022149696039923514239198973728381470562114128511630255098428951603896126507814349986286926299244531906473181800300109162638238425365871862174757398704874277001803426284087704842667837102348645251524380992176692460217226318601343620321244741213250926827952549075857522163537194435684637120568449074357324295022484230373598477863999323833862106064897506150597864275794923075772562581941862580276891765425279394836654380941144060430751699947857452011664910772780374627419328270996247879965712854608282668964275936077835284502503260344526481151382108658947074683831482875758666328986700498636060663311023268378542535072919283647316207318477573989884722754317180757739484913355973631155066950443165796733672505675792650175851365294681518613533477273329114690324131488216531322890892222791915850987021015618865944951297243631358908253993350646886504460532427533372119310733737, 654433017204931030393884251520668374328578502112329065499245002616657014281719335786661515789130219785304265108980804249440767555248681599614916682862272298566529629627370058286372109201394638823768116811457370204225849129591845722537128484986632895594026295390672059538422169297165462771536815309040021941791147092890195692716368835665525512092613874164553286901414066296758277717935130187674237865068581278223382549707919786219467251565941643651468471324264919504851327570536807893676184593090369615446336982200250817405654069585848798291148949544030544445912464576019279805438673487595098987607957982360753492118751134083284569552862643696493090952715189939962405267741340948977001347141197668825546928450773716052590827997930067536828145658744783093287603067336353184698270363381995904498903929951342498169674677772505915917892511524738459697953768204999886007331374287802745911404315520429855768037418781115835733069095398879654230545925889303904167613219754390016014663223711153223936017132539402888384500403173770229974411277713123372655880066512684146667611520206481203450395544265475048082006895566549778942122244442242417697935029036598682099155322609869957736346608794418286642437622221202523419761127578473141962865846981, 656664159253722329929053881846462282075700945358858129208163124111724072395742290938901013857620037064931120187061472360789962188087748211386276211901416888383522524828300057143223768825016771396971405385977912296701653205241363268791119945482193984563702209525916146980620192041687172777300282327706567918940719192625941352443318030308174187644070886142676567420030750535823957313466487841300401041422312228995354355116513411090417618210002201895595206258178569925039733524631945374780219509872794291728386593162704950971804719827413175600084072124550356629242037519156657560708729000058763994398372598969230222262774288107534066249394374210874463105135829436822421427018885352909669880400889642929021806274477907311812473931225976972461016710112993815116030458360517452892106914594396142581080010693210638806241950845753726815623138324369459420597573301222406254185141834168861479275626072566314488512744029700973260213116392570734584708047885637360800801490671987526484030544293507014652255465525769171257967153971904160956737038424454788046814707288145060839042763689179027536837547505707225949731157318193576213129317450470898141922981363516190463218148241380489513924308008187442535923844636042242167172741489445988199453019921]
c1 = [444531112929450459543429140289809619352043140696583900318472311192993219071404501187225377975892835377730046816730541364621576305148629413991072596416292771499353626694086109818825865726561717859290674936479379440924953869745802497198353628780558684040197810639946952446639846962370059860407555603707651647445778690443133041719452682307467799060452350349846151164547227915641440300614643291938358486050614365721847936496784822258945006602953910612408639602112132517355286459246759783844187587029129096933840481577127362013009336024160313155443733324065758746009769735152099454707980327657814044803785801085482527034056357955160912732839285613124640764692992125257747489943274775114507962485142119292818757934178722138157136000746473824670613239038580653315516058082689116313140371701861770391559241728912292295215566353290045617070525565808471805444285287360342155382284563438231306291727245828528779139146737448817803780592932460624820150332962163306763031728808752839666587984335901666270888268651506139805275362721042665537581020335832830312410994318025927058132047888203625481749363694992617336832831079339525064060849711014591696245478262814362615528649645003743928560170024829080375009621610610446758724714824314537539746597741, 319541171989767532755446000602097166896225347200196626508743093402224140241867314191827751378242432733903693226457027547172503513933644166879063390329737707053155660757120607000703717090604353573894803135999560634581998758344371067183496223789431710697723602791123843074248253528892325344824181541637266688749341322598016032961231749993023923925501083482721050000006912410382928977367058736582134488933487634182532948789845269245093447032949294945953727446820372956158776372159289907796522559644584267443854722343476196620885856835627994133495481903950973851962721072743126089395885542852494215551897217409794422711378515783590466394064265338734779437741278799845955991252819063591202033217363086007574680196274165659224036333800913376109841217065565944940099457568618294430030095355884383382620667834498951427954543736556654626809376215414457341164441165372685161034593542013658661053119879650343936895500400491819128442035398244226052712196047030270555306649842215320932928786690145149666668756759100776180801452219969527645958383675069449971323519557391283337465707916843374943797043686423669161710845415697699772587416614436574937381832178519103680075944054520762887757080554038678298312886042341215497149413336248405537740328940, 314059908879839211743982439271947937059807107675462631896947556928279511925709829725602844671587815181775555286443980486387392531683739236166178663508657548957709154052374595822650982768844981478766720967344389614442017880959614694423922004567205566409635186367201016881524545082953206432499470253544887989860186642066374631166504114896535230649898364765325911535379956436163079714333598585317335075342554480091881378075222805824727370003715132887676286327411075743285417931887601252064259088917354520893665152873809394053950846283996475555707043676223754046397879429722459056943614882288569319981732491865180790710996858877015686532952528110893476920835586760432230084065755668348503681437690885155192082177180849600427339431813823500295186150265147541408632605773035109157963829065124156123974842756493976775470713420070192912392424914257865130407451159134318747464239487223402412696929008760074058516565325359822843045675745818560106446225149438122412842575979293252239333514491444976586504031796450972462559975537317488157352723320981150068008900320412564599483826236513029115763658081363396644662285620153927069676732549015641908133201340628720125625078457933298534083623439395740137790446325852716936206960839127509897673926901]
e = 3
x = crt(c,n)
n = iroot(c,n)[0]
 n = 21284549846899107163445266790069890489991766265066670117740041673053919433107553508736672406349162607834712235414792600330386554613938596730990993650228249618342847405389708543298197387911282471331025034644981636516993425782156213795010982329683961515138961682735155467657695586525945578095454261918922311836296600612187601289109443231935663736544987443493636386113682960035165643727531720204063689518635839344581600837981515952908211440547342952709768315171970291853909284296553715095794156732971673185553914520950928429581557743320550954650663202465307154008283469516141679229332899580353656780903791407729488546711

-level 2 has ct,e and n which is the decrypted number in level 1. -level 2 is solved using the formula p = (c + (kn))*(1/3). Its bruteforced, thus getting the flag.

import gmpy2
n = 21284549846899107163445266790069890489991766265066670117740041673053919433107553508736672406349162607834712235414792600330386554613938596730990993650228249618342847405389708543298197387911282471331025034644981636516993425782156213795010982329683961515138961682735155467657695586525945578095454261918922311836296600612187601289109443231935663736544987443493636386113682960035165643727531720204063689518635839344581600837981515952908211440547342952709768315171970291853909284296553715095794156732971673185553914520950928429581557743320550954650663202465307154008283469516141679229332899580353656780903791407729488546711
c = 342185266855114790359426885033581315593099955970036139517231529585950600555880051526820737905498278660912142151418345314592007444924168095881727789313561844641872100681118669581612313061299477186676980038806404561173793514218086839641140591501320999312295486673483495546104061992211790913192728847973015672049545306681308733429256105324538780037196172237009273964542874625981132228600376842040977550844851046491374354106145415555991822246390203219904043617856757335634834737185790806266054565239504497260172140438968677
e = 3

for i in range(1000000000000000000000000000000000000):
    m, is_true_root = gmpy2.iroot(i*n + c, e)
    if is_true_root:
        print(f"Found i = {i}")
        print("Message: {}".format(bytearray.fromhex(format(m, 'x')).decode()))
        break

#Found i = 0
# Message: Here you go, great mathematician: shaktictf{H4st4d_C0pp3rsmith_r3v34l3d}

Flag : shaktictf{H4st4d_C0pp3rsmith_r3v34l3d}