Proof related to RSA decryption

Question

Can someone help me with this proof: Show that RSA decryption works for all messages a as long as the modulus m is a product of distinct primes. Thank you.

Answer 1

The proof of RSA is as follows. $a$ is the plaintext, $e$ and $d$ are the public and private exponents respectively, $m$ is the modulus, and $\phi$ is Euler's totient function.

$$d_k(e_k(a)) \equiv (a^e)^d \pmod m$$ $$\equiv a^{ed} \pmod m$$

By definition, $ed \equiv 1 \pmod{\phi(m)}$, and so

$$d_k(e_k(a)) \equiv a^{1+k\phi(m)} \pmod m$$

Where $k$ is some positive integer. Continuing

$$d_k(e_k(a)) \equiv a^1 \cdot a^{k\phi(m)} \pmod m$$ $$\equiv a \cdot (a^{\phi(m)})^k \pmod m$$

If $gcd(a, m)=1$, then by Euler's Theorem, $a^{\phi(m)} \equiv 1 \pmod m$, and so

$$d_k(e_k(a)) \equiv a \cdot 1^k \pmod m$$ $$\equiv a \cdot 1 \pmod m$$ $$\equiv a \pmod m$$

However, consider if $gcd(a, m) \neq 1$. By the Chinese Remainder Theorem, if $p$ and $q$ are relatively prime then the system of linear congruences

$$x \equiv a_1 \pmod p$$ $$x \equiv a_2 \pmod q$$

has a unique solution modulo $m = p \cdot q$. As such we can alternatively determine the plaintext by solving

$$a \equiv (a^e)^d \pmod p$$ $$a \equiv (a^e)^d \pmod q$$

Suppose without loss of generalization that $p \mid a$. Our system of linear congruences is now

$$0 \equiv 0 \pmod p$$ $$a \equiv (a^e)^d \pmod q$$

And therefore the proof follows as previously, except modulo $q$ instead of modulo $m$.

Now suppose the modulus is a prime power, i.e. $m = p^x$, and consider the earlier equation

$$d_k(e_k(a)) \equiv a \cdot (a^{\phi(m)})^k \pmod{p^x}$$

Clearly we must have that

$$a^{k\phi(m)} \equiv 1 \pmod{p^x}$$ $$a \cdot a^{k\phi(m) - 1} \equiv 1 \pmod{p^x}$$

However, as $gcd(a, p^x) \neq 1$, there does not exist a $b$ such that $ab \equiv 1 \pmod{p^x}$, and therefore the second equation cannot be the case. As such, $m$ cannot be a prime power.

Although the proof only fails if $gcd(a, p) \neq 1$ and the probability of it is extremely negligible (see my comment), using a prime power as a modulus must still be avoided, as if it is not then factoring $m = p^k$ becomes trivial (the attacker simply needs to take $k$ roots to determine $p$), using which an attacker can compute $\phi(m)$ and therefore $d$ and can decrypt the plaintext.