# Does RSA work for any message M?

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?

-

Yes, RSA works for any message $M \in \{0\dots n-1\}$, in the sense that the decryption procedure recovers the original message. In other words, $((M^e\bmod n)^d\bmod n)=M$. That is assuming $p\ne q$. That requirement is unstated in A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, but true with overwhelming odds given the method suggested to generate $p$ and $q$, and always true when following the recommendation given that $p$ and $q$ differ in length by a few digits.

An easy proof is to consider $Z=(M^e)^d-M$; show $Z\equiv 0\pmod{p}$ and $Z\equiv 0\pmod{q}$, by using Fermat's Little Theorem and the assumed relation between $e,d,p,q$; since $p$ and $q$ are distinct and prime, and divide $Z$, their product $n$ divides $Z$; thus $Z\equiv 0\pmod{n}$. Q.E.D., thanks K.G.

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

Note: if $p=q$, the cryptosystem is totally unsafe. Independently, those rare $M$ that are a non-zero multiple of $p$ are modified by encryption followed by decryption.

-
Concise and ingenious. Thanks for your answer! –  Juto Dec 8 '13 at 21:34
One really minor nitpick: Don't use CRT. It is sufficient to note that if $p$ and $q$ both divide $Z$, then $pq$ divides $Z$. –  K.G. Feb 14 '14 at 9:55

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.

-
Do you know where I can find the reductions between finding $M$ not relatively prime to $n$ and factoring? –  mikeazo Oct 20 '11 at 22:12
@mikeazo: that's easy: if $M$ is not relatively prime to $n$, then a simple GCD between $M$ and $n$ reveals a factor of $n$. In the other direction, if you can factor $n = pq$ then $M = xp$ for any $1 < x < q$ is an integer which is smaller than $n$ but not relatively prime to $n$. –  Thomas Pornin Oct 20 '11 at 22:22
yeah that was easy and once I read it I thought "Yeah I should have known that!" Thanks. –  mikeazo Oct 20 '11 at 22:26

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$

$\blacksquare$

-

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.

-

I've found an nice explanation with example on Udacity so I will copy the post a bit modified and formatted.

Taking an example of RSA with numbers small enough to reason with:

primes $p_1=11$, $p_2=13$ $N = p_1 \times p_2 = 143$
$\phi(N) = (p_1-1) \times (p_2-1) = 120$
$e = 7$ // chosen to be relatively prime to $\phi(N)$ so it has an inverse
$d = 103$ // derived from $e$ and $\phi(N)$ by extended Euclidean algorithm
$e \times d = 721 = 6 \times \phi(N) + 1 = 1 \pmod{\phi(N)}$

As it happens, for any $i \in [0,142]$, $i^{721} \pmod{143} = i$. That's a good thing, because decryption wouldn't work otherwise.

For a number that's relatively prime to the modulus, that's explainable by Euler's theorem -$x^{\phi(N)}= 1 \pmod{N}$ - and taking those powers out of the equation leaves you with $x$ by itself.

For a number like $26$ that has a common factor with the modulus, the encryption/decryption happens to work in this example: $26^{721} \pmod{143} = 26 \pmod{143}$. But it's not explainable by the Euler's theorem, since $gcd(26,143)=13$.

So why does this work? Should it work? Does RSA require it to work?

Forget about Euler's theorem - it looks promising but it's a dead end in this case.
We'll use Fermat's little theorem.
We also need to use the following fact
$a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b \pmod{p_1\times p_2}$. Let's call that FACT X.
Remember that $e\times d = 1 \pmod{\phi{N}} \Leftrightarrow e\times d - 1 = k\times(p_1-1)\times(p_2-1) \Leftrightarrow e\times d -1 = 6(11-1)(13-1)$.
The $(p_1-1)$ and $(p_2-1)$ parts of the equation will be eaten by Fermat's theorem.

$m^{ed}=m^{ed−1} \times m=m^{k(p1−1)(p2−1)}\times m$
If $m \equiv 0 \pmod p_1$, then Fermat's little theorem doesn't apply. But $m ^{ed} \equiv 0 \pmod p_1$.
Example: $22 \equiv 0 \pmod{11}$. $22^{721} \equiv 0 \pmod{11}$.
If $m \neq 0 \pmod{p_{1}}$, then Fermat does apply (we're working in $\pmod{p_1}$ here): $m^{ed}=m^{k(p_1−1)(p_2−1)}\times m=(m^{(p_1−1)})^{k(p_2−1)}\times m=1^{k(p_2−1)}m=m$.
The two cases above give us the result that $m^{ed} \equiv m \pmod{p_1}$.
Apply the same reasoning for $p_2$.
Then use FACT X above to show that $m^{ed} \equiv m \pmod{p_1 \times p_2}$.

Back to the example:

$m^{ed}=m\times m^{ed−1}= m\times m^{720}=m\times m^{6\times 10\times 12}=m\times(m^{10})^{72}=m\times(m^{12})^{60}$. So if $gcd(m,11)=1$, then Fermat shows that taking $m^{ed} \pmod{11}$ is like multiplying by $1$. If $gcd(m,11)\neq 1$, then you're multiplying $0 \pmod{11}$ and end up with zero.

Similarly for mod 13.

And then FACT X combines the two and shows that taking $m^{ed}$ leaves the message unchanged $\pmod{11\times 13}$.

-
It's nice that you care and downvote when someone does not comply the rules, but when I update my answer you should remove the punishment. –  Pio Nov 9 '13 at 11:30
I agree. That said, just wanted to make you aware that SE does not notify downvoters when you edit. I'm assuming that is the reason why some have not changed their vote. Could be a nice feature though. –  mikeazo Nov 12 '13 at 13:52