# What does it imply if in RSA pow(m, e, n) is same as the m

So, Let's assume we have n which is made up of 2 strong primes which cannot be factored & e which is textbook value of e that is 65537.

Now, I have a message1, first I convert that into decimal and then do

(msg1^e)%n and this turns out to be exactly same as random1 . Now, I generated a lot of messages and performed the encryption same way and I found one of the message (let's call it msg2) generates same output after encryption as it is in plain.

So, usually RSA formula is c=pow(m,e,n) . In my case pow(msg2,e,n) gives output exactly same as msg2. That implies for an edge case of a message the encryption provides same ciphertext as plaintext.

Does this means, that this RSA system for n is broken/buggy?

• Some elements of $\mathbb Z/n\mathbb Z$ have small multiplicative order! Every order divides $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$, but there are always going to be at least some elements of order below $\lambda(n)$. For example, what happens if $m = -1$? (Remember that $e$ is odd for RSA.) – Squeamish Ossifrage Jun 16 '19 at 16:37

Not necessarily. With the (not so strong) primes p=211 and q=311, we have n=65621. Using e=157, I came up with the following messages that encrypt to themselves:

1
5908
5909
11197
11817
17105
17106
23013
23014
28922
36699
42607
42608
48515
48516
53804
54424
59712
59713
65620

Finding such a message with strong primes would be extremely difficult, but I can't think of a reason it couldn't occur.

At this point I don't have an explanation for the consecutive numbers in the list.

• Hint: if $x = 0$ or $x = 1$, then $x^e \equiv x \pmod m$ for any $m$ (prime or composite). What happens with $x^e \bmod n$ if $n = pq$ and, say, $x \equiv 0 \pmod p$, $x \equiv 1 \pmod q$? Use the Chinese remainder theorem! – Squeamish Ossifrage Jun 16 '19 at 16:34
• @SqueamishOssifrage: ...and if $e$ is odd, then this also happens for $x \equiv -1$ modulo $p$ or $q$ (which explains why these fixed points frequently come in pairs). – Ilmari Karonen Jul 16 '19 at 14:20