3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henadzi Matuts Aug 18 at 18:42
  • $\begingroup$ @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. $\endgroup$ – poncho Aug 18 at 21:50

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.