Scrambled: RSA

Problem

Hmmm I wonder if you have learned your lesson... Let's see if you understand RSA and how the encryption works. Connect with nc mercury.picoctf.net 4572.

Solution

1. Connecting to the service outputs some ciphertext, the public modulus, and the exponent:

   flag: 829028241414792642507307826831663208770782000165302776091323486634533383163139982214729846016025284837263836848583288388036808723365272269374409326069679076649201723360893031764011387138355824548171873485635608161243375260927981949336509520141137169022338640786310700427489718775334908850531280732655757912149775588417272069541148241553877755047291205390139861932620167055938267788782478538844883659061026557071165461098073737285184582478161366889031938458549826904906157795544413651112130389109709980362633677196927274113397820122232320152129992299622675348524516094041914082485255268881691319530972736813279316247629409768979299697157880169723660759231019289614621522537275963878618648640608513438710611998547237969328656189218195019134224761904962610058732809220902452016454514501677119010007204756938370523179822859871127842382734190087375914538445032594442557115142261300074746395896699537345282672474280091005130678768771589033799460612570377030464710823878983234017970536086466847160465918791501471668477294815511769578303214398835677839494738685865471490662519939641130681622392263735960048404503730145824229660677151753185376112245767177029697765453285569886880219081574818153292490999105413132163461562354068839227200875436561104081855844269769366595212283592259433304215481293556592702584026906882235681389613767824901848201583325692213183289219553156914197921171679127981087454198147385506653181504819897068189274278580177790435196296051323439445109300731795387566545343813670947675352585303590084461697590029856284734952942607650777732921284206728028962929472900744212951787283928762377081906464571836713874116373828629694503702858884663002573613676737598905751327210362380332342965219778425317624372546272168579835996415278069667758879856639490422806713086038602412593011684822767416013331740084621457223842212109860901764104696660804750100041982142417895400161498587800409307992607545575130268963919916237164404767200032335270642459921882971782481133226580690319730499893206122439675583054188273998416353762784253328265511749645152387938225839341425475107654222457212524858031184449092646822914757506950430612081485075338295429624578988200371412210343642662356218935983256329622266210613549878533920089604647339420473611502389485022290113753974034955834894727280591245652310443115595992708900999302392912136686954688739308909631505113118537188408169646941615413596109579538207173608709483510370451117806788264197775283041131333975272549345972178919221380338819680105935827386132437931746677392997044372569189162330449213747470393006167724063497159333130171960825112619142045501318787488733587633679360705874377108233700744058498609914593513281910884527151698880480973628959738545075353562312878735967543793723782842087764917990083270104358061964937656723193218454356021244450799847814575115212187871883731051230716667274457785374778572053704779839280899285186287300286962218941185113712970343285660141892188835147229863371282150073428268057420049886631457124627256741133998140180471399095550786981407326847897396233459166338607446801050368752123846489785389621759352722794233101631794036919439683124827102879926654119323939306422085807647048088896946348926452923996775984053751696371730899860477054315516202193685483983120060753333982604256896319466312387831924950348415175862467002820850523597402360492292950723463420907859846335865828212801571681680256748673493015511898229313901543523818086041096966080214151654980400706365863592863372316060867931437118825221445956874766597886064034837404604327225152915134040693400978874711987267492928633747158273528381191393833223704639143779824336752883248354034328038081211523812643669611182902069319468546476447300544436798389329458882728981533450595283808885721929990102322288361243152102255447002880668792046256565299866763381198483513720763708754606646048428060682989791850576454813353668884338568503983917279647151430869319548950482343599992544922831172520352645906250549092476746580313311951026818728228135217459034694332378421089831956904762843954750136939951441275606931231366770747805691189717627295753897963099466380134875892476225318440092895276072237402965293153607958338864957287530069501915846932042162535696720715097216830408325754166579819365329838572808820384796717537219700072331468840719350893273932457363299759749776796246269379160003503955985483223866860365163457942499625047054578759271446763581035576155385160885329517550135667289135249898525522445331611976183916111024473264584922292766732811248576607998808655945342463439173881085090864530027551979979287988782841472330751179628542999701643546592623947910853340911269694854423740879861121880413591458215526784666223777012448894480628886858362007258137450131989810116115997343978697239164261018018575767608627668151399185995798953813118380428027509583520491481969005699802796002150425828830701015707323146484647073780102168286848486981799814937374889485497376508717215900369564950258921259359231714385758364264322670422884704710089860498375690539762841827638290340353218854890810544436947908533301994041421110628688604641401606304315184932924527237185605709643330666906312592271131322328331281660480557707515924662637222805356143740839786462027677665639077695086996597720949989225892002810520250867834888098263550494678147628360129832549650652223516979623383589448975007941393596773040645104028940071572239590801440732940347514300135177320219270466928062500118758739811803728946650507046457008621244904824968435122468890167598001930546972404745720795260588009672443376499948145311210331215202913246324137385121599260013411792417162541318987632303438412641821436393510664999559494246944560731647318511562470196428122460736442343121215821798166320633912152026370101285569364883840917364084295934743243182831526482781208248181372297273264639926268474513174116671371008612249603202204046065722658585945370386836176491753503616383663028351409234015505032027062957121405360884638529055626285983359635642777606591084083334462342142568971193712619770344920133662952692224000340133822368629835892977643174261338437727246143413220069668655193035621027953248076624495063123632317543531921249840341270080758989047661895476109954675952158384917800500819149560659277278253395262765465288096893697159371049857046286661400527783285559787956720396536352501239532315990320650960558650490706040029459586178043661323108325875232944926735678553641575388848710699695430932837638263617697948338428733994098467060453027087436377459267357299444851207046433452709929421488353752130377203557043977194729530812561942943149735331760536519695876885555347625187906312209697935573384345922136157529025549613426055663319758070554398597066082962836583212905328865121810123462379921216557554735761454004403995860780380864596966971080722082516434610353423803263690258483955444304759293662522620005483820877563240328274667172917226182113965144589719892713567723917715286156329411386462243537429492625060536384744760851227510832641038587694115744150445762578642463315472208070395310251211601408033032118013359958643339502045651523875894299835256299973758902941168582969165420745685208402511573614685549254057492691461218757573240832681000801827232528499800346984318679900883605302142917535595136652228893889368128421709863671322444225187905564667959480703872654100460623414745840184237493231253050624705776664251623070086795580373907789624206310007470069761970837469610823074979029870771598093206126474194850603284443686651159949610736931137294724439063148825283762109557322332749483984437100262645130452675548027610864153967151209471427542118452567031495198078277733522516061115444370292603329333588786241060964341421189850622428328304270629082955819718548276837912480888976612279188357523887354670560909546452989041735236661237507143787895712228699088598933478522485521953995213706883506246072191763012498458677982237789632227281412811401582748110438508658836600069202370690268483664373697853475094597837606990663620653258871038949307483925333231849735065323755504510347709152200749220676506787584072999632
   n: 106393877387061674780269443416122033957470775377538503986525156853344106645258943831036053499392577287359309204310519147714363669430556595918051924362857879883648386846033045170831033578612419189879345630099664288981304224208850344812969488431038558262641627552457836197084966102117701680185682779525658336377
   e: 65537

   The service will also encrypt any input we give it and show the corresponding ciphertext.

2. In textbook RSA, a 1 should encrypt to 1. But, when we try encrypting a 1 we get 13589787814203979735997344432080802832776008984701751529073256623683835560426019268055662727723878817162581242623884397426411415725347741008962849580645219519573984615300484601979495080932024787662131004577978449903745252490885056468740446181188019506761784393355054186218263954234491000582090477859332982836.

3. Encrypting some input (aaa) multiple times produces different outputs, which means the algorithm is not deterministic. Strangely, encrypting a multiple times produces the same output. Essentially, the number of possible encrypted outputs is equal to the length of the input text. For example, there is only one character in 1 so there is only one ciphertext while there are three characters in aaa and thus three valid ciphertexts exist.

4. Encrypting aa produces 1358978781420397973599734443208080283277600898470175152907325662368383556042601926805566272772387881716258124262388439742641141572534774100896284958064521951957398461530048460197949508093202478766213100457797844990374525249088505646874044618118801950676178439335505418621826395423449100058209047785933298283673561024996000428515785201807310147438746525988645885310370799314417341170352572980373936820027773998706009446119059121725998847299152732140652261734547503673358211949690790453350635511909487532110430283112659904909965978120113482426195268318329751292020654211499572883335268473019408057847129211754745164317, which is 616 characters long. Let's use E to denote the encryption function and E1(m) to denote the first ciphertext of message m. The E1('a') from before is 308 characters long. This is exactly double which indicates that the encryption algorithm uses some kind of concatenation. Reconnecting and sending a and aa again does not produce ciphertexts where the length is exactly double, but the length of E1('aa') is always close to double that of E1('a').

5. After looking at E1('a') and E1('aa'), I realized that E1('aa') includes E1('a'). Encrypting abc also includes E1('a'). In other words, a's ciphertext is in abc's ciphertext. However, b's ciphertext is not in abc's ciphertext. Despite this, E1('ab') is in E1('abc'). The encryption algorithm appears to randomize the order of the encrypted letters. In E1('abc'), E1('a') is sometimes first, sometimes second, and sometimes last.

   abc=271953687857601736339083552904408774529821861339217741980803450071393655028017345773163047354951416488304617393809242400662357092747891809532714395072664254858990687744486233795969830251406701849913159123284337691527352146721503198133759455441462637260709997401631987030913436263691591879934071550195232191178685902232048456694042584177267000654535464923783918412780414336779867930010284739751323219223776660770812496183924438714338672738366499145034968921787900909129598711148263548089562634901771222008888762727848339279204526898850916328823759734432853894637539124733502648246102694842895698870118328274369707698331546135353308483550444450122435972802245634665513942914748396795997183276329787455598017534244331690210048685573287997160532456827095028700181796345979576316846010711849823875755590899611384778544516784181452755961838624741675075308984412698197633017728875870962833140824001078480025964191306078537911293954
   a=86859022320484566940425841772670006545354649237839184127804143367798679300102847397513232192237766607708124961839244387143386727383664991450349689217879009091295987111482635480895626349017712220088887627278483392792045268988509163288237597344328538946375391247335026482461026948428956988701183282743697076983
   b=55695574875445968150529730197356495722866366967023410322162548137649935387387235169570208245319243740096519760093562978525393278492587302601216782626990728181786766864073479388711316406275931148007229102205280783269061828433978729949772199402721636147043178001668467016428952377438506075898115979502366068405
   c=98381552146740643928947668777021758778868259491372885573995035167182205393536813037537261030285097568831905111560975562781614863047280982672718224915204651864849935612587103028254546444191547296768531225260821176499577451585056258023509591051216797619537421884577750644822210595060177427771540241791446435223
   ab=3154613535330848355044445012243597280224563466551394291474839679599718327632978745559801753424433169021004868557328799716053245682709502870018179634597957631684601071184982387575559089961138477854451678418145275596183862474167507530898441269819763301772887587096283314082400107848002596419130607853791129395486859022320484566940425841772670006545354649237839184127804143367798679300102847397513232192237766607708124961839244387143386727383664991450349689217879009091295987111482635480895626349017712220088887627278483392792045268988509163288237597344328538946375391247335026482461026948428956988701183282743697076983

6. Taking all of this information into account, E1('a') and some value that represents E1('b') are always in E1('abc'). This also applies to the flag ciphertext. Since the flag format begins with picoCTF{, E1('p') is in E1(flag) and a representation of E1('i') is also in the flag. We can encrypt p and then encrypt pi. We can then remove E1('p') from E1('pi') to obtain the representation of E1('i') that is in the encrypted flag. We repeat this process until the { character when we don't know the next character. At this point we can loop through every printable ascii character, c, and encrypt 'picoCTF{'+c.

7. So, in summary, our exploit script does the following:

   1. Create a string, decoded_flag, to hold the flag's characters as the loop runs.

   2. While decoded_flag[-1] is not } then for each printable ascii character, c:

      1. Encrypt decoded_flag+c and store to current_encrypt_test.

      2. Remove the previous encrypted input (previous_encrypt_test) from current_encrypt_test to obtain the representation of E(c) and save to current_char_rep.

      3. If current_char_rep is in E1(flag) then append c to decoded_flag and break to the next iteration.

      4. Set previous_encrypt_test to current_encrypt_test.

8. Running the script will print the flag character by character.

Flag

picoCTF{bad_1d3a5_3525501}