# How to decrypt c when e is not co-prime with phi(n) and e is non-prime

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)$$?

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.

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