# Specific case of RSA where cipher text equals plain text

How did they arrive at the conclusion that there are 4 messages where plain text equals cipher text from "It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ciphertext is equal to the plaintext and gcd(m, n) = 1. Two of these messages are 1 and −1."? Also, how to find the other 2 messages when there is no clue about n,p,q?

• "How did they arrive at the conclusion" --> Who is "they"? The other messages depend on n,p,q, so you have no chance of finding them without knowing n,p,q. Oct 3, 2021 at 1:59
• Related, almost duplicate question: How many points in RSA, such that $m^e = m \bmod n$ Oct 3, 2021 at 15:42

It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ciphertext is equal to the plaintext and gcd(m, n) = 1

Well, if $$m^3 = m \pmod n$$ (and assuming $$n$$ is a conventional RSA modulus, that is, it is $$n = pq$$, for $$p, q$$ distinct odd primes), this is equivalent to both of the below holding simultaneously:

$$m^3 = m \pmod p$$ $$m^3 = m \pmod q$$

If $$p, q$$ are prime, these are cubic equations in fields; such cubic equations have (at most) 3 solutions. A moment's reflection (or a bit of algebra) yields the solutions $$m = 0, 1, -1$$ (with the later being equivalent to $$p-1, q-1$$) - since there are at most 3 solutions, this must be all of them.

Now, $$m=0$$ (in either case) is inconsistent with $$\gcd(m, n)=1$$, hence we can discard those solutions; this yields the solutions $$m = 1, -1 \pmod p$$ and $$m = 1, -1 \bmod q$$. By the Chinese Remainder Theorem (and the fact that $$p, q$$ are relatively prime), all four possible combinations correspond to a single $$m$$ in the range $$(0, n-1)$$.

The combination $$m = 1 \pmod p$$ and $$m = 1 \pmod q$$ yields the value $$m = 1$$; similarly the combination $$m = -1 \pmod p$$ and $$m = -1 \pmod q$$ yields the value $$m = n-1$$ (the quote gives this as $$-1$$, however that's not in the range, and modular cubing will never return the value -1); these are the two trivial solutions.

The other two combinations, both $$m = 1 \bmod p$$ and $$m = -1 \pmod q$$, and $$m = -1 \bmod p$$ and $$m = 1 \pmod q$$ are the nontrivial solutions.

This logic shows there are no other possibilities.

Also, how to find the other 2 messages when there is no clue about n,p,q?

Even if you were given the value of $$n$$, knowing one of the two nontrivial values immediately leads to a factorization of $$n$$, for example, by computing $$\gcd(m-1, n)$$, hence there is no easy way (without knowing the factorizatoin apriori).

• thank you so much for the detailed explanation. Just one question, what do you mean by a non-trivial solution? Does it mean the solution does not exist? Oct 3, 2021 at 2:56