1
$\begingroup$

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?

$\endgroup$
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$
    – Mikero
    Oct 3, 2021 at 1:59
  • $\begingroup$ Related, almost duplicate question: How many points in RSA, such that $m^e = m \bmod n$ $\endgroup$ Oct 3, 2021 at 15:42

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\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$
    – Robbie
    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$
    – poncho
    2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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