Tags: wiener's_attack rsa 

Rating: 5.0

# Challenge Description

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

Author:SolarDebris
```

# Challenge Solution
In this challenge I used Wiener's attack method to get the decryption exponent `d`. The attack uses the continued fraction method to expose the private key `d` when `d` is small (If `e` is large enough, we can't get the `d` using Wiener's attack, No matter how small the `d` is). Using the Euclidean algorithm, one can efficiently recover the secret key d if one knows the factorization of N. But in our case we don't know the factorization of N (`http://factordb.com/`).

I used PyPI module `owiener` to implement Wiener's attack. In case if you don't have this module installed, execute this command `python3 -m pip install owiener` or `curl -O https://raw.githubusercontent.com/orisano/owiener/master/owiener.py`

```py
#!/usr/bin/env python3
import re
import owiener
from Crypto.Util.number import long_to_bytes

with open("description.txt", "r") as file:
text = file.read()[:-1]

pattern = r'(\w)\s=\s(\d+)'
valueRegex = re.compile(pattern)
matches = valueRegex.finditer(text) # Just some regex practice :))

variables = []
values = []
for match in matches:
variables.append(match.group(1))
values.append(int(match.group(2)))
print(variables)
C, n, e = values

d = owiener.attack(e, n) # The actual script itself is this small lol
if d:
m = pow(C, d, n)
flag = long_to_bytes(m).decode()
print(flag)
else:
print("Wiener's Attack failed.")
```