How many points in RSA, such that $m^e = m \bmod n$

Question

For every RSA-cryptosystem, there exist some messages $m$, for which it holds that $m^e \equiv m \pmod n$

As to the question, how many such messages exist, this question has already been asked and answered here: https://math.stackexchange.com/questions/1298664/rsa-fixed-point

However, I do only understand the answer up to a certain point

Suppose that $n$ is only 1 prime. Then it holds that the number of unconcealable messages is $\gcd(e-1, p-1)+1$

This is because in $m^e \equiv m \pmod p$ , either $m = 0$ or $m \not= 0$. In the latter case $m$ can be expressed as $g^t$, where $g$ is a Generator in $\mathbb{Z_p}$

$g^{t*e} \equiv g^t \pmod p$

$g^{t(e-1) \bmod p -1 } \equiv g^{0 \bmod p -1} \pmod p$

$t(e-1) \equiv 0 \pmod {p-1} $ has exactly $\gcd(e-1, p-1)$ solutions, so the total number of unconcealable messages is, together with $m=0$ , $\gcd(e-1, p-1)+1$

When we now look at real RSA, which has two prime factors in its modulus, it holds that the number of unconcealable messages is $(\gcd(e-1, p-1)+1)\cdot(\gcd(e-1, q-1)+1)$

Why is that so? I suppose it has to do with CRT, but I just cant understand why.

Answer 1

Why is that so?

Well, we have $m^e \equiv m \pmod n$ if and only if both of the following hold:

$$m^e \equiv m \pmod p$$ $$m^e \equiv m \pmod q$$

We know (because of reasoning you accepted) that the number of solutions to the first equation (for $0 \le m < p$) is $\gcd( p-1, e-1) + 1$; we can write out the list as $m_0, m_1, ..., m_{k-1}$ (for $k = \gcd( p-1, e-1) + 1$).

Similarly, we can write out the solutions to the second equation (from $0 \le m' < q$) as $m'_0, m'_1, ..., m'_{k'-1}$ (for $k' = \gcd( q-1, e-1 ) + 1$).

Then, the question comes down; how many ways can we paste $m \equiv m_i \pmod p$ and $m \equiv m'_j \pmod q$ so to satisfy both equations (for $0 \le m < n$). It turns out (because $p$ and $q$ are relatively prime) that for a specific $m_i, m'_j$ pair, there is a unique value $m$ that satisfies both (and that's the Chinese Remainder Theorem). Each $m$ which corresponds a solution is formed by such a joining, and so the total number of solutions is the number of $m_i$'s times the number of $m'_j$'s; that is, $(\gcd( p-1, e-1) + 1) \cdot (\gcd( q-1, e-1) + 1)$