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?
2
-
$\begingroup$ "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. $\endgroup$– MikeroCommented Oct 3, 2021 at 1:59
-
$\begingroup$ Related, almost duplicate question: How many points in RSA, such that $m^e = m \bmod n$ $\endgroup$– Ilmari KaronenCommented Oct 3, 2021 at 15:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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).
-
$\begingroup$ 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? $\endgroup$– RobbieCommented Oct 3, 2021 at 2:56
-
$\begingroup$ @Robbie: "non-trivial" means "not trivial", not "nonexistent". Trivial solutions are solutions that meet the specified criteria, but in an uninteresting way; in this case, $m=1$ and $m=n-1$ are the trivial solutions. A non-trivial solution is any solution which isn't a trivial solution - in this case, there does exist two such non-trivial solutions (and in this case, knowledge of either is equivalent to the knowledge of factorization of $n$) $\endgroup$– ponchoCommented May 27 at 14:17