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

Jake

4/2/24, 12:17 PM

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?

288

0 + 7

prime-numbers

fgrieu

4/2/24, 12:30 PM

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.

Daniel S

4/2/24, 7:41 PM

HINT: There is more than one possible solution to $M^8= C^d\mod N$, but not too many more.

Samuel Neves

4/3/24, 12:07 AM

[This paper by Daniel Shumow](https://eprint.iacr.org/2020/1059) covers this precise scenario.

Jake

4/4/24, 10:39 AM

@fgrieu Thanks a lot, I was able to find the right solution!

fgrieu

4/4/24, 11:23 AM

@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

4/7/24, 1:00 AM

@Jake could you share your solution? I'm doing a similar thing but i'm struggling to find the solution.

Rohit Gupta

4/7/24, 2:13 AM

@Jake - for the sake of others please answer your own question and then tick it.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

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.