# Small Inscription

Description :

```text
I came across a strange inscription on the gate that connects two circles, but I cannot read the last part. Can you help me?

Attached files : [SmallInscription.py] [SmallInscription.output]
```

SmallInscription.py

```python
#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, getPrime
from secret import FLAG
assert len(FLAG) < 30
if __name__ == '__main__':
msg = bytes_to_long(b'There is something reeeally important you should know, the flag is '+FLAG)
N = getPrime(1024)*getPrime(1024)
e = 3
ct = pow(msg, e, N)
print(f'{ct=}')
print(f'{N=}')
```

SmallInscription.output

```text
ct=747861028284745583986165203504322648396510749839398405070811323707600711491863944680330526354962376022146478962637944671170833980881833864618493670661754856280282476606632288562133960228178540799118953209069757642578754327847269832940273765635707176669208611276095564465950147643941533690293945372328223742576232667549253123094054598941291288949397775419176103429124455420699502573739842580940268711628697334920678442711510187864949808113210697096786732976916002133678253353848775265650016864896187184151924272716863071499925744529203583206734774883138969347565787210674308042083803787880001925683349235960512445949
N=20948184905072216948549865445605798631663501453911333956435737119029531982149517142273321144075961800694876109056203145122426451759388059831044529163118093342195028080582365702020138256379699270302368673086923715628087508705525518656689253472590622223905341942685751355443776992006890500774938631896675247850244098414397183590972496171655304801215957299268404242039713841456437577844606152809639584428764129318729971500384064454823140992681760685982999247885351122505154646928804561614506313946302901152432476414517575301827992421830229939161942896560958118364164451179787855749084154517490249401036072261469298158281
```

The `e=3` which is too small for the encryption. There is an attack existed called `Low Exponent Attack` on RSA when `e` was small.

When the e=3, we can get the plaintext by finding the `cube root` of the `ct`. Because the ciphertext was just the message rised to the e.

There is a catch to note. When `pow(m,e)` is less than the modulus, we can just calculate the cube root of the `ct` to get message. If not, we have to find the cube root of `(ct+kN)` where `k` is some integer in the field.

As the message in the challenge already about 50 chars, the `pow(m,e)` might be greater than the `N`. So, I implemented the second case to get the flag.

solve.py

```python
from gmpy2 import iroot
from Crypto.Util.number import *

n = 20948184905072216948549865445605798631663501453911333956435737119029531982149517142273321144075961800694876109056203145122426451759388059831044529163118093342195028080582365702020138256379699270302368673086923715628087508705525518656689253472590622223905341942685751355443776992006890500774938631896675247850244098414397183590972496171655304801215957299268404242039713841456437577844606152809639584428764129318729971500384064454823140992681760685982999247885351122505154646928804561614506313946302901152432476414517575301827992421830229939161942896560958118364164451179787855749084154517490249401036072261469298158281
e = 3
ct = 747861028284745583986165203504322648396510749839398405070811323707600711491863944680330526354962376022146478962637944671170833980881833864618493670661754856280282476606632288562133960228178540799118953209069757642578754327847269832940273765635707176669208611276095564465950147643941533690293945372328223742576232667549253123094054598941291288949397775419176103429124455420699502573739842580940268711628697334920678442711510187864949808113210697096786732976916002133678253353848775265650016864896187184151924272716863071499925744529203583206734774883138969347565787210674308042083803787880001925683349235960512445949

c = ct
while True:
m = iroot(c, 3)[0]
if pow(m, 3, n) == ct:
print(long_to_bytes(int(m)))
break
c += n

# There is something reeeally important you should know, the flag is DANTE{sM4ll_R00tzz}
```

> `Flag : DANTE{sM4ll_R00tzz}`

# [Original Writeup](https://themj0ln1r.github.io/posts/dantectf23)

Original writeup (https://themj0ln1r.github.io/posts/dantectf23).