Does RSA work for any message M?

Question

I decided to read the original RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystem because of a question I had about RSA (which is not the question I'm about to ask, but may be a question on here at some time) and came across something I had never seen before in any textbook description of RSA (Note: this comes from the beginning of Section VI of the paper).

for any integer (message) $M$ which is relatively prime to $n$, $M^{\phi(n)} \equiv 1\pmod{n}$

The part I don't recall ever hearing in class, or coming across in a text book, or seeing in any description of RSA I've ever read is that $M$ and $n$ must be relatively prime.

So, I decided to play around with a toy example of RSA to see what would happen. I use $p=13$, $q=31$, $e=7$ and $M=2p=26$ (for completeness: $d=103$, $\phi(n)=360$, $n=403$).

I observed the following using my toy instance of RSA: $M^e\equiv M\pmod{n}$, $M^e\equiv 0\pmod{p}$ and $M^e\equiv M\pmod{q}$.

Do these equivalences hold for all $M,p,q$ when $M$ and $n$ are not relatively prime? How would I prove this? What is the real-world effect of this?

Answer 1

Yes, RSA 'works' for any message $M \in [0..n-1]$, in the sense that the decryption procedure recovers the original message; or in other words $((M^e\mod n)^d\mod n)=M$.

An easy proof is to consider $Z=(M^e)^d -M$; show $Z\equiv 0\pmod{p}$ and $Z\equiv 0\pmod{q}$; from which it follows that $Z\equiv 0\pmod{n}$.

Note: in general, $M^e\equiv M\pmod{n}$ does not hold.

Answer 2

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.

Answer 3

Yes, RSA works for every M. Remember Fermat's Little Theorem:

$x ^ p = x \mod p$ (for all $x$, and all prime $p$).

A bit of induction gives this simple extension:

$a = 1 \mod p-1$ implies $x ^ a = x \mod p$ (for all $x$ and all prime $p$).

Now, we know that $d$ and $e$ are related by:

$d·e = 1 \mod lcm(p-1,q-1)$

Because $p-1$ is a factor of $lcm(p-1, q-1)$ this implies

$d·e = 1 \mod p-1$

and hence

$M ^ {d·e} = M \mod p$

By symmetry, this also implies

$M ^ {d·e} = M \mod q$

and so, by the Chinese Remainder Theorem (and because $p$ and $q$ are relatively prime):

$M ^ {d·e} = M \mod p·q$

QED

Answer 4

By the Chinese Remainder Theorem, RSA "works" as long as it works modulo $p$ and modulo $q$; i.e. that $(M^e)^d = M$ modulo $p$ and modulo $q$. If $M$ is not relatively prime to $p$ then $p$ divides $M$ (because $p$ is prime); in that situation, that equation becomes $0 = 0$, which holds.

Even if it did not work for any $M$, it would not be a problem, because finding a $M$ between 1 and $n-1$ and not relatively prime to $n$ is equivalent to factoring $n$, and factoring $n$ is meant to be very hard. But anyway, RSA still works for those integers.