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

mm flag

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?

fgrieu avatar
ng flag
Since $e$ is even, that's not [RSA]( 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]( 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]( for $M^{e/2}\bmod p$. That can be applied several times.
Daniel S avatar
ru flag
HINT: There is more than one possible solution to $M^8= C^d\mod N$, but not too many more.
pe flag
[This paper by Daniel Shumow]( covers this precise scenario.
Jake avatar
mm flag
@fgrieu Thanks a lot, I was able to find the right solution!
fgrieu avatar
ng flag
@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.
Bob Evans avatar
sr flag
@Jake could you share your solution? I'm doing a similar thing but i'm struggling to find the solution.
Rohit Gupta avatar
pg flag
@Jake - for the sake of others please answer your own question and then tick it.
I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.