c = 7404228387482887479261869746749991746176804495927055118318206683570516448983801743960459361546161134428690426222368709863453442050071171756423599377401597984440754435058668926603178633761668515076496069751847161724033187368679875259918093224187811267691876198273870870578467510184510086298582204521702946045220312770122458237518246424165432296119053607094777200284200814236416350304918483690156578148133652864328594441673632360773823893061942585188618198600179924877899949396771723157015085683434661302154230334257765610040158570863416499816053904560634890245995407176180498179848769133967582005361790108725945277949845769358752674332269800138008126120486961174643630274131401283073800170609863393091462716402062974615038997250596862336175333249971111165958082179351116528188875511999901288868170989351009565637749016012554778609401305705599425503266370571838403199592830285591168821852287944019050110517938219347052153238370382065390639346971764343981632465382255796047103032366703706122266986406432114737513202337430860123189821063638894815952679576109060674029276361130756827095433943772560556432939992933276440340090287373085788774415087792787958810051460428461265815708830858361853853472340042568141996425244740239642623958541083311687869085046368156034023773742764525490982352637357523475031768768619981883253061696021829604666466769997506990572364386730754183019245389791086458671560767393577689687174730155049027616849606316072012661663516661756810877578172095321431600121667891545760511844723167476314345937930753837239733394626157660380103339672690094231220365695508657679602754981411231543816566131037225152153015287164171129157814773590352342570677841639550177097704155982858059402540582839885549452130954935219771327861980762934458786390322073771612324195542640000816993296528925039288704714097937261854536340516727095307316259517387188619927408613685678242056200319636422554100280245820480283675364454021450870487344889261

e = 13

n = 837917991769817577099012858825043621439213393871252844184979143910022524665671746602033029786023400433980514546629884581070744355689675763666508582252088828336924157749612209014889798515986173078208184754981795265662261842068905222827399564640144963128801139395796907701088410729066096137184440573421894772846045250248226091711068783212073177802193557566732778100268394356790682062456906959788743362210379401423535444525939728151667129504959830208526123546957556889283083581734912767972489983318516797227332478600714538982071161963953471654008548598246996313896916161004417438148442053930427087178288301473873771267043032108101234501286979031395712339766724573338499408682922730210577055275465276811470172087601022043782018881104279890437569498230432244397712025970070994445552972576397913895088998909430090498162946747146709060268409076950347457571143038273647606330163595503230091907284565794253522490082339734195106133656568716794333492666967976788137101200644004640875673427498791194131638628285387189590496770144399069058630809147864111103005630384267243174723849875440874051189832648459109654330667011182386029537517946818489763504068519418479235039609249657040932116571322456746937825562723191742969350269742764928019773872655997514685823345785593778177914410266921555772305917518342736602786506239943483718833147502399174119273706267989794743323453341270677651833756515276300780889945005843378419789785755964602424049487996273030559729998579320003022026012169170756243210875022349453719909707526819866788940417579036998409368889704976468401933659085076477273032105120174993716693076572343027837623362830713551644289977603365587775424056182440140341005047813911467857712984538734035633260200124997431814616249669697973673513017080190965691930706971760860838330533546270898422881086782063363261264280624362790220393789505232131697879477509091714676947365439957840022803585980625882512790227093632255528715511265481468505483068508181500109488305246795806995427468892264010844553567221536144953578155424249128909052513176778178654506486133170644063222100527446383175999827697870276841687611144943654545506727720248414639860806897890562101808858749326453026743114964063800055769094420192530529001467099574177760703374169013786982484830879286377761264314511485639468290983092824341143500913548984348616191729249357491193126972767067188932864381336421728813959570587022959510266364684005422083875532496993455885332373073970918142938158505991915407398011722450726211

Huge RSA or is it?

Solution

As listed in the article describing RSA, RSA is a really cool method of encryption with the help of a one-way function.

The entire security of RSA, however can be broken if the user has chosen very small public exponent.

If pow(m, e) == pow(m, e, n), that is… the message can be obtained from the above, simply by taking the eth root of c, and seeing if it is a perfect integer. In our case, we use this method, and proceed with the rest of the challenge.

m = ZZ(c).nth_root(e)
print(m)

This prints 81853434768608021893043463500993934123661304673976831287892017162307134089813344283570054883218082574214775885995246308395092741794058348818909130621

We convert this to hex and to ascii, to get the flag.

flag{with a really small exponent, you can even forego modulo}

Flag

flag{with a really small exponent, you can even forego modulo}