Score:1

# How can I decrypt a message with RSA if $e = 65536$ and $\gcd(e,\phi(N)) = 8$?

In a message exchange with RSA, an unusual public exponent $$e = 65536$$ is used.
Since $$N$$ is easily factored, I am able to derive $$p$$ and $$q$$. Consequently $$\phi(N) = (p-1)*(q-1)$$.
However, since $$2^3$$ is present among the factors of $$\phi(N), \gcd(e,\phi(N)) = 8$$. It is not possible to compute the private exponent d directly.
I tried to reduce the problem to the calculation of $$d = (\frac{e}{8})^{-1} \mod \phi(N)$$, from which I would have obtained $$M^{8} = C^d\mod N$$.
I don't think this is the correct solution, because since $$e$$ is a power of two, $$\gcd((\frac{e}{8}), \phi(N)) = 8$$, so we are right where we started.
Am I a bit off road?

Since $e$ is even, that's not [RSA](https://pkcs1.grieu.fr) per se. Hint: since you have $p$ and $q$, solve the problem modulo each of these and then combine the solution(s) by the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Existence_(constructive_proof)). Since $e$ is even, $M^e=C\bmod p$ is equivalent to $\bigl(M^{e/2}\bigr)^2\bmod p$ and we know [how to solve that](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) for $M^{e/2}\bmod p$. That can be applied several times.
HINT: There is more than one possible solution to $M^8= C^d\mod N$, but not too many more.
[This paper by Daniel Shumow](https://eprint.iacr.org/2020/1059) covers this precise scenario.
@fgrieu Thanks a lot, I was able to find the right solution!
@Jake: glad you worked it out. I gave hints rather than a detailed an answer because this look like a CTF / challenge / homework. But if you determine that's ethical, feel free to answer your own question.
@Jake could you share your solution? I'm doing a similar thing but i'm struggling to find the solution.