# RSA Jam
## OverviewFrom 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)``. 
## ResearchWith 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.
## SolvingNow 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() # RSArsa = 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