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

2
$\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$
1
  • $\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

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.