In RSA, I want to know a way to be able to retrieve all possible plaintexts $m$ given a ciphertext $c$, $\phi(n)$, $n$ and $e$. The decryption exponent $d$ can not be generated due to the fact that $e$ is not co-prime with $\phi(n)$.

In fact, the $e$ I have is not even prime(it is specifically $1024$ in this case and thus it is even so it is certainly guaranteed to have a gcd greater than $1$ with both $p - 1$ and $q - 1$), which is the main reason I am asking, as every single method that I have found online that can be used to find possible plaintext when $gcd(e, \phi(n)) > 1$ assumes that $e$ is prime, which is completely invalid in my scenario. Anyone knows how to get all plaintexts when $e$ is not relatively prime to $\phi(n)$?


1 Answer 1


Contrary to what the question states, in RSA, $e$ needs not be prime. Indeed, customary $e$ like $65537$ and $3$ are prime; but as long as $\gcd(e,\phi(n))=1$, we can compute a working $d$ as $e^{-1}\bmod\phi(n)$.

Hint if indeed $\gcd(e,\phi(n))\ne1$: knowing $n$ and $\phi(n)$, factor $n$ (see e.g. this). Then, using the Chinese Remainder Theorem, transform the problem of finding all the solutions $m\in[0,n)$ to $m^e\bmod n=c$ into several simpler such problems with $n$ replaced by ${p_i}^{r_i}$, where the $p_i$ and $r_i$ are the primes dividing $n$ and their respective multiplicities, so that $n=\prod{p_i}^{r_i}$.

Additional hint: in the specific case of $e=2^k$ (as in the question), and if $n$ is the product of $\ell$ distinct odd primes (that is all the $r_i$ are $1$, and $n$ is odd), there will be up to $e^\ell$ solutions. They can be obtained as sketched above, additionally using Tonelli-Shanks recursively to depth $k$ for each of the $\ell$ sub-problems obtained by CRT, then recombining the $\ell$ sets of up to $e$ solutions to these sub-problems, using the CRT.

  • 1
    $\begingroup$ This gives hints rather than a detailed answer, because the question could be an exercise, homework, or a CTF. $\endgroup$
    – fgrieu
    Jan 20, 2023 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.