# Proving RSA is a permutation

I am trying to prove that RSA is a permutation. All I can find is places where it is stated that it is a permutation because the function is bijective. I know that it is, but would like to see a detailed proof.

For clarity, we have $N = p \cdot q$, where $p$ and $q$ are prime and $e$ such that $1 = \gcd(e, (p-1)\cdot(q-1))$. We want to show that $f(x) = x^e \pmod N$ is a permutation. I am thinking we must use Fermat's little theorem somewhere but I cannot complete a detailed proof myself.

• Assume it is not a permutation. Is decryption possible? Commented Dec 11, 2017 at 18:50
• See also, this and this. Commented Dec 11, 2017 at 18:56
• Pre-condition:$x$ must of course be smaller than $N$. Commented Dec 11, 2017 at 20:17
• Saying "it is a permutation because it is bijective" is like saying "it is a permutation because it is a permutation", since a permutation is by definition a bijection from a set to itself (here, $\{0,N-1\}$). Commented Dec 12, 2017 at 0:31
• Do you know the Chinese remainder theorem?
– j.p.
Commented Dec 12, 2017 at 7:18

## 1 Answer

First let's clarify notations. $$f(x)=x^e \pmod N$$ is non-standard, hesitating between

• $$f(x)\equiv x^e\pmod N$$ , meaning $$N$$ divides $$x^e-f(x)$$
• $$f(x)=x^e\bmod N$$ , additionally specifying that $$0\le f(x).

What's meant in RSA encryption is the later.

A permutation of a set is a bijection from that set to that same set. Any injective function from a finite set to a set with the same cardinality (number of elements) is a bijection. Thus we only need to prove that for any integers $$x$$ and $$y$$ in $$[0,N)$$ , if $$f(x)=f(y)$$ , then $$x=y$$. We do that in the following.

We assume $$f(x)=f(y)$$. By definition of $$f$$ that means $$(x^e\bmod N)=(y^e\bmod N)$$. That implies $$N$$ divides $$x^e-y^e$$. That implies any prime factor $$p$$ of $$N$$ divides $$x^e-y^e$$, that is $$x^e\equiv y^e\pmod p$$.

It is hypothesized $$1=\gcd(e,(p-1)\cdot(q-1))$$. Therefore $$e$$ and $$p-1$$ are coprime, the multiplicative inverse of $$e$$ in $$\mathbb Z_{p-1}$$ is well defined, and there exists a positive integer $$d_p$$ and a non-negative integer $$k$$ such that $$e\cdot d_p=1+k\cdot(p-1)$$.

Raising $$x^e\equiv y^e\pmod p$$ to that power $$d_p$$, we get that $$(x^e)^{d_p}\equiv (y^e)^{d_p}\pmod p$$; thus $$x^{e\cdot d_p}\equiv y^{e\cdot d_p}\pmod p$$; thus $$x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$$.

For any prime $$p$$ and any integer $$x$$, Fermat's little theorem states that $$x^p\equiv x\pmod p$$. That allows to prove by induction on $$k$$ that for any non-negative integer $$k$$, $$x^{1+k\cdot(p-1)}\equiv x\pmod p$$.

Thus $$x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$$ becomes $$x\equiv y\pmod p$$, that is $$p$$ divides $$x-y$$. Similarly, $$q$$ divides $$x-y$$.

Here we hypothesize that $$p\ne q$$ (which is unstated in the question). If distinct primes divide an integer, their product does. It follows that $$p\cdot q$$ divides $$x-y$$, that is $$x\equiv y\pmod N$$, that is $$x=y$$ given that both belong to the set $$[0,N)$$; that completes our proof.

Note: the hypothesis $$p\ne q$$ is necessary. Illustration: $$p=q=e=3$$, $$f(3)=f(6)$$.

• By the way, proving surjectivity, rather than injectivity, might be more straightforward--the preimage of $y$ is $y^d$. Commented Dec 12, 2017 at 11:30