# RSA Jam

## Overview
From having a look at the script, this is definitely RSA encryption.
And we even have the private key ``(N, d)``.
This won't be enough tho, we somehow have to find a second ``d``, that also decrypts ciphers created with the public key ``(N, e)``.

## Research
With the power of google and wiki, I found out that besides [Euler's Φ(n) function](https://en.wikipedia.org/wiki/Euler%27s_totient_function)
(i.e. how many numbers < n are coprime), the [Carmichael λ(n) function](https://en.wikipedia.org/wiki/Carmichael_function) also can calculate a valid modulo to then calculate ``d`` from ``e``.
So there is ``e = 65537; d = e^-1 % Φ(n)`` and ``d2 = e^-1 % λ(n)``. Done yet? No.
Although we have a 2nd d (with a different value most of the time), to get d2 we have to calculate λ(n).
This might work without the primes, but I don't know how and didn't find something on the fast.
So, again after some searching, I found a nice algorithm from this [site](https://www.di-mgt.com.au/rsa_factorize_n.html) to recover the primes from ``N, e, d``:
```
# [Initialize] Set k = d*e − 1.
# [Try a random g] Choose g at random from {2,…,N−1} and set t = k.
# [Next t] If t is divisible by 2, set t = t/2 and x = g^t % N. Otherwise go to step 2.
# [Finished?] If x>1 and y=gcd(x−1,N)>1 then set p = y and q = N/y, output (p,q) and terminate the algorithm. Otherwise go to step 3.
```
It only works in about 50% of the time as I understand it, so keep that in mind.

## Solving
Now that we all the pieces, we can get to solving.
I used pwntools to connect to the given IP and port.
After some dirty parsing...
```
rsa = r.recvline().decode().strip() # RSA
rsa = rsa.split(": ")
e, d, N = int(rsa[1][:-5]), int(rsa[2][:-5]), int(rsa[3][:-1])
```
...we then recover the primes ``p, q`` with the algorithm shown above, get the Carmichael λ(n) with ``l = lcm(p-1,q-1)``, get the other d with ``d2 = pow(e, -1, l)`` and finally send this to HTB.
They are kind enough and respond with the flag. :D