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

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

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.

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.

• Thanks for the explanation! I'm also wondering why there are ciphertexts other then 0 which also have multiple preimages, and how the occurence of such ciphertexts could be generalized. Aug 18 '20 at 18:42
• @HenadziMatuts: well, if $e>1, \phi(q)$ are relatively prime, and $p, q$ are relatively prime, then any value $kp^2$ will have multiple preimages for the function $f(x) = x^e \bmod p^2q$; the various examples you found are of this form. Aug 18 '20 at 21:50