# Description
In and out morty a 20 second adventure
```python
C = 9763756615749453697711832780290994218209540404092892743938023440562066399337084806157794233931635560977303517688862942257802526956879788034993931726625296410536964617856623732243706473693892876612392958249751369450647924807557768944650776039737608599803384984393221357912052309688764443108728369555676864557154290341642297847267177703428571478156111473165047499325994426058207523594208311563026561922495973859252628019530188566290941667031627386907620019898570109210940914849323148182914949910332546487694304519512036993844651268173759652768515378113523432311285558813699594606327838489283405761035709838557940909309
n = 25886873815836479531102333881328256781823746377127140122698729076485535125711666889354560018621629598913480717734088432525491694576333336789245603514248141818159233105461757115009985693551920113198731562587185893937220809465123357884500614412967739550998756643760039322502299417470414994227318221114452157902944737622386655242568227060393806757218477070728859359570853449231546318892600962043047963934362830601068072327572283570635649379318478675132647932890596210095121862798891396418206480147312633875596896359215713337014482857089996281525920299938916154923799963866283612072794046640286442045137533183412128422223
e = 3412227947038934182478852627564512970725877639428828744897413324202816073614248101081376540697482845313507125163089428254245096018283445899452858022211718628390653483026409446914537083191082941622293729786517851124468666633780447090080209520381218492938112166177839174421554838099214223129604698311531540363994640048732628930103674878115331383263452987483186144997440066159073515630319057855626746004248806849195662788941903776396118558065192757367266853647652706247900976106843337363721026272734784391404675859060134421742669727121306927682580867089725963848606261214171291213498225968719857795306299660931604391979

```


# Solution
## Recon

- This looks like a typical RSA challenge where we have the ciphertext `C`, the modulus `n` and the public exponent `e`. However, I noticed that `e` has almost the same bitlength as `n`, so this may be vulnerable to the Wiener's Attack

## Execution

- I had already uploaded a script that decrypts RSA cryptosystems that are vulnerable to the Wiener's attack, check https://github.com/not1cyyy/RSA-Wieners-Attack.

- I modified the code a little bit :
```python
from owiener import attack
import os

e = 3412227947038934182478852627564512970725877639428828744897413324202816073614248101081376540697482845313507125163089428254245096018283445899452858022211718628390653483026409446914537083191082941622293729786517851124468666633780447090080209520381218492938112166177839174421554838099214223129604698311531540363994640048732628930103674878115331383263452987483186144997440066159073515630319057855626746004248806849195662788941903776396118558065192757367266853647652706247900976106843337363721026272734784391404675859060134421742669727121306927682580867089725963848606261214171291213498225968719857795306299660931604391979
n = 25886873815836479531102333881328256781823746377127140122698729076485535125711666889354560018621629598913480717734088432525491694576333336789245603514248141818159233105461757115009985693551920113198731562587185893937220809465123357884500614412967739550998756643760039322502299417470414994227318221114452157902944737622386655242568227060393806757218477070728859359570853449231546318892600962043047963934362830601068072327572283570635649379318478675132647932890596210095121862798891396418206480147312633875596896359215713337014482857089996281525920299938916154923799963866283612072794046640286442045137533183412128422223
d = attack(e, n)

if d == None:

print("cannot retrieve the private key, exiting...")

os._exit(1)
else:
choice = input("Do you want to decrypt a ciphertext ? y/n : ")

match choice:
case "y":
c = 9763756615749453697711832780290994218209540404092892743938023440562066399337084806157794233931635560977303517688862942257802526956879788034993931726625296410536964617856623732243706473693892876612392958249751369450647924807557768944650776039737608599803384984393221357912052309688764443108728369555676864557154290341642297847267177703428571478156111473165047499325994426058207523594208311563026561922495973859252628019530188566290941667031627386907620019898570109210940914849323148182914949910332546487694304519512036993844651268173759652768515378113523432311285558813699594606327838489283405761035709838557940909309
#m = pow(c, d, n)
plain = bytearray.fromhex(hex(pow(c, d, n))[2:]).decode()

print(f'Here is the plain text: {plain}')

os._exit(0)

case "n":

print(f'Here is the private key: {d}, exiting....')
os._exit(0)

```

- Running the script, we get this output :
```
┌─[not1cyyy@0x45] - [~/Desktop/space-heroes-CTF/2023/Rick_Sanchez_Algorithm_FINISHED] - [mar. avril 25, 23:12]
└─[$] <> python3 solve.py
Do you want to decrypt a ciphertext ? y/n : y
Here is the plain text: shctf{1_w4n7_thA7_mCnu99E7_5auc3_M0R7Y}
```
# Flag

shctf{1_w4n7_thA7_mCnu99E7_5auc3_M0R7Y}

Original writeup (https://github.com/not1cyyy/CTF-Writeups/blob/master/Space-Heroes-CTF/Space-Heroes-CTF-2023/Rick_Sanchez_Algorithm.md).