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.

  • 2
    $\begingroup$ Assume it is not a permutation. Is decryption possible? $\endgroup$
    – mikeazo
    Commented Dec 11, 2017 at 18:50
  • $\begingroup$ See also, this and this. $\endgroup$
    – mikeazo
    Commented Dec 11, 2017 at 18:56
  • $\begingroup$ Pre-condition:$x$ must of course be smaller than $N$. $\endgroup$
    – Maarten Bodewes
    Commented Dec 11, 2017 at 20:17
  • 5
    $\begingroup$ 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\}$). $\endgroup$
    – fkraiem
    Commented Dec 12, 2017 at 0:31
  • $\begingroup$ Do you know the Chinese remainder theorem? $\endgroup$
    – j.p.
    Commented Dec 12, 2017 at 7:18

1 Answer 1


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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.