## [Original/Source Writeup](https://bigpick.github.io/TodayILearned/articles/2020-10/b01lersbootcamp#dream-stealing)
We’re given:
```Modulus: 98570307780590287344989641660271563150943084591122129236101184963953890610515286342182643236514124325672053304374355281945455993001454145469449640602102808287018619896494144221889411960418829067000944408910977857246549239617540588105788633268030690222998939690024329717050066864773464183557939988832150357227One factor of N:  9695477612097814143634685975895486365012211256067236988184151482923787800058653259439240377630508988251817608592320391742708529901158658812320088090921919Public key: 65537Ciphertext: 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>>> q10166627341555233885462189686170129966199363862865327417835599922534140147190891310884780246710738772334481095318744300242272851264697786771596673112818133```
Now that we have p and q, we can simply proceed to finding the private exponent, d, via the Extended Euclidean algorithm:
```pythondef 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 egcd, d, b = egcd(e, phi)print("d:  " + str(d) );```Which we can then use to decrypt like so:
```python# Decryptpt = 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 46327402297734345668136112664627609061622411859278517910287191659094499226493flag{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}`.