Легко показать, что в RSA при e = 3 есть 4 сообщения m, для которых зашифрованный текст равен открытому тексту и gcd(m, n) = 1.
Ну если $m^3 = m \pmod n$ (и предполагая $n$ является обычным модулем RSA, т. е. $n = pq$, за $р, д$ различные нечетные простые числа), это эквивалентно одновременному выполнению обоих следующих условий:
$$m^3 = м \pmod p$$
$$m^3 = m \pmod q$$
Если $р, д$ простые, это кубические уравнения в полях; такие кубические уравнения имеют (не более) 3 решений. Мгновенное размышление (или немного алгебры) дает решения $м = 0, 1, -1$ (последний эквивалентен $p-1, q-1$) - поскольку существует не более 3 решений, это должны быть все они.
В настоящее время, $м=0$ (в любом случае) не соответствует $\НОД(м, п)=1$, следовательно, мы можем отбросить эти решения; это дает решения $m = 1, -1 \pmod p$ и $m = 1, -1 \bmod q$. Согласно китайской теореме об остатках (и тому факту, что $р, д$ взаимно просты), все четыре возможные комбинации соответствуют одному $м$ В диапазоне $(0, n-1)$.
Комбинация $m = 1 \pmod p$ и $m = 1 \pmod q$ дает значение $м = 1$; аналогично сочетание $m = -1 \pmod p$ и $m = -1 \pmod q$ дает значение $м = n-1$ (цитата дает это как $-1$, однако это не входит в диапазон, и модульное кубирование никогда не вернет значение -1); это два тривиальных решения.
Две другие комбинации, обе $m = 1 \bmod p$ и $m = -1 \pmod q$, и $m = -1 \bmod p$ и $m = 1 \pmod q$ являются нетривиальными решениями.
Эта логика показывает, что других возможностей нет.
Кроме того, как найти другие 2 сообщения, когда нет никаких сведений о n, p, q?
Даже если вам дали значение $n$знание одного из двух нетривиальных значений немедленно приводит к факторизации $n$, например, путем вычисления $\gcd(m-1,n)$, следовательно, нет простого пути (без априорного знания факторизации).
