# 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}`


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://picoctf2021.haydenhousen.com/cryptography/scrambled-rsa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.