## [Original/Source Writeup](https://bigpick.github.io/TodayILearned/articles/2020-10/b01lersbootcamp#dream-stealing)

We’re given:

```
Modulus: 98570307780590287344989641660271563150943084591122129236101184963953890610515286342182643236514124325672053304374355281945455993001454145469449640602102808287018619896494144221889411960418829067000944408910977857246549239617540588105788633268030690222998939690024329717050066864773464183557939988832150357227
One factor of N: 9695477612097814143634685975895486365012211256067236988184151482923787800058653259439240377630508988251817608592320391742708529901158658812320088090921919
Public key: 65537
Ciphertext: 75665489286663825011389014693118717144564492910496517817351278852753259053052732535663285501814281678158913989615919776491777945945627147232073116295758400365665526264438202825171012874266519752207522580833300789271016065464767771248100896706714555420620455039240658817899104768781122292162714745754316687483
```

So it looks like RSA, where we are given N, one factor of it (i.e either p, or q, your choice), e, and a ciphertext.

Since we’re given N and one of it’s factor, finding the other is easy, just divide N by the one given factor to get the other:

```python
>>> N = 98570307780590287344989641660271563150943084591122129236101184963953890610515286342182643236514124325672053304374355281945455993001454145469449640602102808287018619896494144221889411960418829067000944408910977857246549239617540588105788633268030690222998939690024329717050066864773464183557939988832150357227
>>> p = 9695477612097814143634685975895486365012211256067236988184151482923787800058653259439240377630508988251817608592320391742708529901158658812320088090921919
>>> q = N // p
>>> q
10166627341555233885462189686170129966199363862865327417835599922534140147190891310884780246710738772334481095318744300242272851264697786771596673112818133
```

Now that we have p and q, we can simply proceed to finding the private exponent, d, via the Extended Euclidean algorithm:

```python
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y

# Compute modular inverse of e
gcd, d, b = egcd(e, phi)
print("d: " + str(d) );
```
Which we can then use to decrypt like so:

```python
# Decrypt
pt = pow(ct, d, N)
print("Plaintext: ", pt)
```

A full python snub to do so [can be found here, in part of my “Go To” CTF tools repository](https://github.com/bigpick/CaptureTheFlagCode/blob/master/tools/crypto/normal_rsa_python/normal_rsa.py) (minor modifications for this case required, hard code in p and then compute q and phi manually, vs the FactorDB code).

The code gives us:

> Plaintext: 46327402297734345668136112664627609061622411859278517910287191659094499226493

Which after translating to ascii, gives us our flag:

```
decimal_to_ascii 46327402297734345668136112664627609061622411859278517910287191659094499226493
flag{4cce551ng_th3_subc0nsc10us}
```

Protip: If you use zsh, add this function to your ~/.zshrc (otherwise add it to your shell’s appropriate user config file):

```
function decimal_to_ascii(){ local decimal=$1
echo "obase=16; $decimal" | bc | xxd -r -p; echo ""
}
```

Flag is `flag{4cce551ng_th3_subc0nsc10us}`.