I'm trying to understand the working of RSA algorithm. I am getting confused in the decryption part.
I'm assuming
$$n = pq$$
$$m = \phi(n) = (p – 1)(q – 1)$$
E is the encryption key $\gcd(\phi(n), E) = 1$
D is the decryption key, and
$DE = 1 \mod \phi(n)$
$x$ is the plain text
Encryption works as ($y = x^E \mod n$) and decryption works as ($x = y^D \mod n$)
The explanation for why the decryption works is that since $DE = 1 + k\phi(n)$,
$$y^D = x^{ED} = x^{1 + k \phi(n)} = x(x^{\phi(n)})^k = x \mod n$$
The reason why last expression works is $x^{\phi(n)} = 1 \mod n$ ?
According to Eulers theorem this is true only if $x \text{ and }\phi(n)$ are coprimes. But $x$ is only restricted to be $0 < x < n$ and $\phi(n) < n$. So $x$ should be chosen to be coprime with $\phi(n)$?
Help me clear out the confusion!
Best Answer
Even if the plaintext $x$ is not pairwise coprime with $p$ or $q$, RSA still works as advertised. Here is why:
$p$ and $q$ are prime, so $x$ is a multiple of either $p$ or $q$, given the restriction that $x < pq$.
Assume that $x \equiv 0 \pmod p$. If it is congruent to $0$ mod $q$ the below still applies, just switch the name assigned to the two primes.
$x^k \equiv 0 \pmod p$ for all $k > 0$, i.e $x^k \equiv x \pmod p$.
$$ \begin{align*} x^{1+ z \phi(n)} & \equiv x^{1+ z \phi(p) \phi(q) } \\ &\equiv x^1 \cdot x^{\phi(q) \phi(p) z} \\ &\equiv x \pmod q \end{align*} $$
Combining both equations with the Chinese Remainder Theorem yields $x$, the plaintext.