# 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](https://github.com/HHousen/PicoCTF-2021/blob/master/Cryptography/Scrambled:%20RSA/script.py) 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](https://github.com/HHousen/PicoCTF-2021/blob/master/Cryptography/Scrambled:%20RSA/script.py) will print the flag character by character.

### Flag

`picoCTF{bad_1d3a5_3525501}`