Rating:
# RSA Small
##### Something is too small in that RSA encryption.
##### Can you decipher the flag?
We have the following output:
```
e = 5
n = 848679985797447869399955772819127213061137842373015804903762494359645720791040778076619433302674004347484565791581642609473387655735195295365279289016435642019259985990645911733119485800890708230053795033609181332000447274578889940499411197562111094428807949016438566888871179849827432797743465183571439731186111884712225698892368979349739206606593045379047207591044512475303068095583610049728424692564119172882065602439029603348602584135304945650000715210121217415159672068653299460404758884228046013042562965080049653891004083434176688089444298777532346069082024899343877834584938045202455200048186554846026727297621240451214798525048971378675972260019196481887830771437670138972634154814409503426355185620129053316128528423087492174694811793403655971666568345076618727967344075031994286240815344178567441153634038071947827327700917234091487142266390015552941979817722214984014258022713900663398969526301690250025575483527895147735655625252139228855555368584244676794350771701435632552963431752523714399310405951557242368697834717565197145134464156785931396734151509020243119926355165138086318689699700337185418254990682421255569532070095700384447469238825430018975257552596722400439696783949509883005145800952113577752688735953731
c = 1290693983568973212241774157251029501916031181300587856502104425060400825645233474412159795041070912725774295993070287999705559436744356587070331473154201672194895706660927805733716209570278752107616017153539788802992400477319421895132265308353914269512736230439032250634773967478099458568504291012797867556104874614937296951446237815056114697267646832399584346738180717835541698802244926455470361437886629916832531228754210088056426885624615069977138458285217304667225248399707130072871824121756788726012791836940206537928157363946715031682108412776344952206447795443691414126211540976228231813721934019177491660030885807301520689365508821556490894213716812362105926718336768325044896559692102465835491500325292511210492266786815154645636848969136539759596476855914079053513055397814403086420614976446006354782596760766518849838306525291408721775119110961750623361977018207968
```
And the following code:
```python
#! /usr/bin/env python3
from Crypto.PublicKey import RSA
from 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 = c
where 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**)
```python
import time
import sys
import binascii
from 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.sage
Potential 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}.'
```
