# RSA Small #####  Something is too small in that RSA encryption.##### Can you decipher the flag?
We have the following output:```e = 5n = 848679985797447869399955772819127213061137842373015804903762494359645720791040778076619433302674004347484565791581642609473387655735195295365279289016435642019259985990645911733119485800890708230053795033609181332000447274578889940499411197562111094428807949016438566888871179849827432797743465183571439731186111884712225698892368979349739206606593045379047207591044512475303068095583610049728424692564119172882065602439029603348602584135304945650000715210121217415159672068653299460404758884228046013042562965080049653891004083434176688089444298777532346069082024899343877834584938045202455200048186554846026727297621240451214798525048971378675972260019196481887830771437670138972634154814409503426355185620129053316128528423087492174694811793403655971666568345076618727967344075031994286240815344178567441153634038071947827327700917234091487142266390015552941979817722214984014258022713900663398969526301690250025575483527895147735655625252139228855555368584244676794350771701435632552963431752523714399310405951557242368697834717565197145134464156785931396734151509020243119926355165138086318689699700337185418254990682421255569532070095700384447469238825430018975257552596722400439696783949509883005145800952113577752688735953731c = 1290693983568973212241774157251029501916031181300587856502104425060400825645233474412159795041070912725774295993070287999705559436744356587070331473154201672194895706660927805733716209570278752107616017153539788802992400477319421895132265308353914269512736230439032250634773967478099458568504291012797867556104874614937296951446237815056114697267646832399584346738180717835541698802244926455470361437886629916832531228754210088056426885624615069977138458285217304667225248399707130072871824121756788726012791836940206537928157363946715031682108412776344952206447795443691414126211540976228231813721934019177491660030885807301520689365508821556490894213716812362105926718336768325044896559692102465835491500325292511210492266786815154645636848969136539759596476855914079053513055397814403086420614976446006354782596760766518849838306525291408721775119110961750623361977018207968```And the following code:```python#! /usr/bin/env python3from Crypto.PublicKey import RSAfrom Crypto.Util.number import bytes_to_long, long_to_bytes
key = RSA.generate(4096, e = 5)msg = b"Congrats! Your flag is: OFPPT-CTF{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}."m = bytes_to_long(msg)print("e = ".format(key.e))print("n = ".format(key.n))c = pow(m, key.e, key.n)print("c = ".format(c))```At this point i didn't know how to break it because i'd never dealt with a challenge like this, luckily found this [git page](https://gsdt.github.io/blog/2018/07/20/stereotyped-message-attack/) that explains it in an easy and understandable way.
So we have the following equation.```(m+x)^e mod n = cwhere x is the part we need to find.```The attack we need to implement is a **Coppersmith attack.**
We can implement this attack because: * We know a part of the plaintext.```Congrats! Your flag is: OFPPT-CTF{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}.```* **e** is small (e=5).* x < N^(1/e).
We can solve it with the code provided by the page mentioned above.
(Note: You have to replace the **x's** of the plaintext with **\x00**)
```pythonimport timeimport sysimport binasciifrom Crypto.Util.number import bytes_to_long, long_to_bytes# def long_to_bytes(data):#     data = str(hex(long(data)))[2:-1]#     return "".join([chr(int(data[i:i + 2], 16)) for i in range(0, len(data), 2)])#     # def bytes_to_long(data):#     return int(binascii.hexlify(bytes(data, 'utf-8')), 16)
def main():    e,N = (5, 848679985797447869399955772819127213061137842373015804903762494359645720791040778076619433302674004347484565791581642609473387655735195295365279289016435642019259985990645911733119485800890708230053795033609181332000447274578889940499411197562111094428807949016438566888871179849827432797743465183571439731186111884712225698892368979349739206606593045379047207591044512475303068095583610049728424692564119172882065602439029603348602584135304945650000715210121217415159672068653299460404758884228046013042562965080049653891004083434176688089444298777532346069082024899343877834584938045202455200048186554846026727297621240451214798525048971378675972260019196481887830771437670138972634154814409503426355185620129053316128528423087492174694811793403655971666568345076618727967344075031994286240815344178567441153634038071947827327700917234091487142266390015552941979817722214984014258022713900663398969526301690250025575483527895147735655625252139228855555368584244676794350771701435632552963431752523714399310405951557242368697834717565197145134464156785931396734151509020243119926355165138086318689699700337185418254990682421255569532070095700384447469238825430018975257552596722400439696783949509883005145800952113577752688735953731)
    c = 1290693983568973212241774157251029501916031181300587856502104425060400825645233474412159795041070912725774295993070287999705559436744356587070331473154201672194895706660927805733716209570278752107616017153539788802992400477319421895132265308353914269512736230439032250634773967478099458568504291012797867556104874614937296951446237815056114697267646832399584346738180717835541698802244926455470361437886629916832531228754210088056426885624615069977138458285217304667225248399707130072871824121756788726012791836940206537928157363946715031682108412776344952206447795443691414126211540976228231813721934019177491660030885807301520689365508821556490894213716812362105926718336768325044896559692102465835491500325292511210492266786815154645636848969136539759596476855914079053513055397814403086420614976446006354782596760766518849838306525291408721775119110961750623361977018207968    m = bytes_to_long(b'Congrats! Your flag is: OFPPT-CTF{\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00}.')    P.<x> = PolynomialRing(Zmod(N), implementation='NTL')    pol = (m + x)^e - c    roots = pol.small_roots(epsilon=1/50)    print("Potential solutions:")    for root in roots:      #print("a")      a = root+m      print(root+m)      #print(long_to_bytes(a))      #print(long_to_bytes(root)) main()```After running it this was the output.```shell❯ sage solve.sagePotential solutions:16678794475845394497046381611277332634514263199780369350752104914618457519327167866737907944182739806871082540078368532323763163281817777410175160943379020961054807436578487598```I converted it to bytes and got the flag.```python>>> from Crypto.Util.number import long_to_bytes>>> long_to_bytes(16678794475845394497046381611277332634514263199780369350752104914618457519327167866737907944182739806871082540078368532323763163281817777410175160943379020961054807436578487598)b'Congrats! Your flag is: OFPPT-CTF{Sm4ll_3xp0n3nts_1n_RS4_4re_n0t_s3cur3}.'```