I'm really new in this whole cryptography thing. And while I was going through some articles about RSA I stumble upon a really weird thing and it goes like this:

If $n = pq$ is a RSA modulus, and d is the encryption exponent. There are at least 9 distinct cleartexts m that are invariant under encryption, i.e. $m^d\ ≡\ m\ (mod\ n)$ ?

Why is it at least 9, can it be more ? And is there any proof for this ?

I seem really interesting and I would like to know the answer on this. If anyone can answer it would be so helpful.


Why is it at least 9?

Actually, we have to assume that $p$ and $q$ are distinct odd primes, and that $d$ is odd; this is presumably covered by the assertion that $n = pq$ is an RSA modulus.

With that assumption, we can proceed as follows: we have $m^d \equiv m \pmod n$ iff both these hold:

$$m^d \equiv m \pmod p$$

$$m^d \equiv m \pmod q$$

This is a consequence of the Chinese Remainder Theorem, which we'll be using a lot.

For the relation $m^d \equiv m \pmod p$, for odd prime $p$, we have at least 3 values of $m \bmod p$ that satistify it, namely $m \equiv 0, 1, p-1 \bmod p$ (and the later is often written as $-1$, as $p-1 \equiv -1 \pmod p$).

Similarly, we have at least 3 values of $m \bmod q$ that satify $m^d \equiv m \pmod q$, $0, 1, -1 \pmod q$.

Now, by the Chinese Remainder Theorem, and because $p, q$ are relatively prime, then for any pair of integers $a, b$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$.

As a consequence, for any one if the values $a \in \{0, 1, -1\}$, and any one of the values $b \in \{0, 1, -1\}$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$. Such an $m$ satisfies both of our original relations modulo $p, q$, and hence satisifies $m^d \equiv m \pmod n$.

There are a total of 9 such sets of $a, b$ values, and hence 9 such values of $m$.

can it be more ?

Actually, if we have $d = 3$ (or if $d$ is the decryption exponent corresponding to $e = 3$), then no, we can't; for the relation $m^3 = m \pmod p$, there can only be at most 3 solutions (as $p$ is prime); as we have listed 3 such solutions, that must be all of them (and similarly for $q$).

However, if we consider larger values of $d$, then yes, there can certainly be more. As an example, if we have $pq = 65$ and $d = 5$, there happens to be 25 such 'value preserving cleartexts' (and it should be easy to reconstruct why this is).

And is there any proof for this ?

The above explination can be expanded to a formal proof; if you want, you can find explicit representations of all 9.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.