0
$\begingroup$

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.

$\endgroup$
1
2
$\begingroup$

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)$

$\endgroup$
4
  • $\begingroup$ Is it really "if and only if?" Suppose $p=61$ , $q=37$, $n=2257$, $e=31$ , then $47^{31} \equiv 47 \mod 61$ , but $47^{31} \not\equiv 47 \mod 37$ , however $47^{31} \equiv 47 \mod 2257$ $\endgroup$ – Fluctuation10111 May 5 at 15:37
  • $\begingroup$ @Fluctuation10111: actually, in this case, we do have $47^{31} \equiv 47 \pmod{37}$ (both sides are equivalent to 10); however it doesn't make our list of $p=37$ because $47 > p$; we're limiting the list to values $0 \le m_i < p$. The value 47 corresponds to the combination $m_i = 10, m'_j = 47$ $\endgroup$ – poncho May 5 at 15:49
  • $\begingroup$ Im apparantly blind, thank you ^^ $\endgroup$ – Fluctuation10111 May 5 at 20:18
  • $\begingroup$ @Fluctuation10111: actually, I also stared at your comment for 10 minutes before I realized what was going on - you weren't the only blind guy/gal here... $\endgroup$ – poncho May 5 at 21:05

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.