Proving that RSA encryption function with non-square free modulus is not a permutation

Question

Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already a related topic on this (Why does RSA need p and q to be prime numbers?). While most of the answers boil down to efficency and security considerations, there is a single answer which states that RSA encryption function with modulus consisting of prime powers loses it's bijection properties, i.e, it is not a permutation any more. However this behaviour is shown only on example with no proof.

Given that, I've started to search a proof of RSA permutation property, and I found such a proof here. But again, it states that the proof works only if $p \ne q$, while it is not actually clear why it is not for $p = q$.

Then I have started to digging it up by myself. Actually, it seems pretty clear for $p = q$ case if $p$ is prime. Then for $N = p^2$, we got a set of plaintexts $\{m_i\}$ such that $0 \leq m_i < N$ and $m_i \equiv 0\pmod{p}$, and having the exponent $e > 2$ we also got $m_i^e \equiv 0\pmod{p^2}$.

But I'm not sure how to generalize cases for $N = p^s, s > 2$; $N=p^sq, s > 1$; $N=p^sq^r, s > 2, r > 2$. Let's take a second case for example. Let $N=5^23= 75$, then $\phi(N) = (5^2 - 5)(3 - 1) = 40$, and $e=3$ is acceptable exponent. Next if I compute all $c_i=m_i^3\pmod{75}$ for all $0 < m_i < 75$, I see that there are 3 sets of discinct $m_i$ values that give the same $c_i$ after encryption:

• $c_i = 0, m_i=\{0, 15, 30, 45, 60\}$
• $c_i = 50, m_i=\{5, 20, 35, 50, 65\}$
• $c_i = 25, m_i=\{10, 25, 40, 55, 70\}$

Thinking of this $c_i$ values I found the following pattern $5^3 \equiv 50\pmod{75}$, $5^32\equiv 25\pmod{75}$, $5^33 \equiv 0\pmod{75}$, $5^34 \equiv 50\pmod{75}$ and so on. Given that it's clear that:

• for $m_i = 5(3k_j + 0)\pmod{75}, k_j \geq 0$ we got $c_i = 0$
• for $m_i = 5(3k_j + 1)\pmod{75}, k_j \geq 0$ we got $c_i = 50$
• for $m_i = 5(3k_j + 2)\pmod{75}, k_j \geq 0$ we got $c_i = 25$

And that's where I stuck. I have tried to explore the examples for $N = p^s$ and $N=p^sq^r$ and have found similar patterns like shown above. But I still need some clues in order to generalize this behaviour and prove that RSA encryption with non-square free modulus is not a permutation. I believe that there should be some simple concept I missing, but since I'm not much into Number Theory, I need community help.

Just for clarification. I'm completely OK with efficency and security considerations of $p$ and $q$ being two discinct prime. The only thing I'm worrying about is RSA encryption function bijection property (or it's absense, which is the case).

Thanks in advance.

UPD

@poncho gave a clear explanation on existence of multiple preimages for $c = 0$. But it also be great to generalize existence of other ciphertexts that can have multiple preimages.

Answer 1

While most of the answers boil down to efficency and security considerations, there is a single answer which states that RSA encryption function with modulus consisting of prime powers loses it's bijection properties, i.e, it is not a permutation any more. However this behaviour is shown only on example with no proof.

It's rather straightforward to demonstrate (assuming $e>1$; with $e=1$, it is a permutation, but not a very interesting one).

A value $N$ is nonsquarefree if there is a value $p>1, q$ such that $N = p^2q$ (note that $q$ may have $p$ as a factor). If so, then consider the encryption of the two values $0$ and $pq$. In the two cases, we have:

$$0^e \equiv 0 \pmod N$$

$$(pq)^e \equiv p^eq^e \equiv p^{2+x}q^{1+y} \pmod N$$

for $x = e-2$ and $y = e-1$. Now, both $x, y \ge 0$, and so $p^{2+x}q^{1+y}$ is a multiple of $p^2q$, and so this latter is equivalent to $0 \bmod N$

Since these two distinct plaintexts map to the same ciphertext 0, the mapping cannot be bijective.