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 Dec 11 '17 at 18:50
  • $\begingroup$ See also, this and this. $\endgroup$ – mikeazo Dec 11 '17 at 18:56
  • $\begingroup$ Pre-condition:$x$ must of course be smaller than $N$. $\endgroup$ – Maarten Bodewes Dec 11 '17 at 20:17
  • 4
    $\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 Dec 12 '17 at 0:31
  • $\begingroup$ Do you know the Chinese remainder theorem? $\endgroup$ – j.p. Dec 12 '17 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)<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)$.

| improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – Joost Dec 12 '17 at 10:46
  • 1
    $\begingroup$ 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$.) $\endgroup$ – fkraiem Dec 12 '17 at 11:30

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.