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? Dec 11, 2017 at 18:50
• Pre-condition:$x$ must of course be smaller than $N$. 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\}$). Dec 12, 2017 at 0:31
• Do you know the Chinese remainder theorem?
– j.p.
Dec 12, 2017 at 7:18

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

• You write "Any injective function function[sic] on a finite set is a bijection", but strictly speaking that skips over the fact that the domain and codomain are the same set. While I believe the correct term here is an injective endofunction (although, if the domain is finite, I suppose it is always injective?), perhaps a note on this is more accessible. Dec 12, 2017 at 10:46
• It is correct that any injective function on a finite set is a bijection (from its domain to its range). Here we need only note that the domain and codomain have the same cardinality, hence injectivity implies that the range equals the codomain. (By the way, proving surjectivity, rather than injectivity, might be more straightforward--the preimage of $y$ is $y^d$.) Dec 12, 2017 at 11:30