1.27: The RSA Scheme

In this chapter we discuss the basis of the so-called RSA scheme. This is the most important example of a public key cryptographic scheme. The RSA scheme is due to R. Rivest, A. Shamir and L. Adelman\(^{1}\) and was discovered by them in 1977. We show how to implement it in more detail later using Maple. Here we give the number-theoretic underpinning of the scheme.

We assume that the message we wish to send has been converted to an integer in the set \(J_m = \{0,1,2,\dots, m-1 \}\) where \(m\) is some positive integer to be determined. Generally this is a large integer. We will require two functions: \[E:J_m \to J_m \qquad \mbox{(E for encipher)}\nonumber \] and \[D:J_m \to J_m \qquad \mbox{(D for decipher)}.\nonumber \] To be able to use \(D\) to decipher what \(E\) has enciphered we need to have \(D(E(x)) = x\) for all \(x \in J_m\). To show how \(m\), \(E\), and \(D\) are chosen we first prove a lemma:

Lemma \(\PageIndex{1}\)

Let \(p\) and \(q\) be any two distinct primes and let \(m=pq\). Let \(e\) and \(d\) be any two positive integers which are inverses of each other modulo \(\phi(m)\). Then \[x^{ed}\equiv x\pmod m\nonumber \] for all \(x\).

Proof

By Theorem 22.6, \(\phi(m)=(p-1)(q-1)\). Since \(ed\equiv 1 \pmod {\phi(m)}\) we have \(ed-1=k\phi(m)=k(p-1)(q-1)\) for some \(k\). Note \(k>0\) unless \(ed=1\) in which case the theorem is obvious. So we have \[\label{eq:1} ed=k\phi(m)+1=k(p-1)(q-1)+1 \] for some \(k>0\).

Now by Fermat’s Little Theorem, if \(\gcd(x,p)=1\) we have \(x^{p-1}\equiv 1\pmod p\) and raising both sides of the congruence to the power \((q-1)k\) we obtain: \[x^{(p-1)(q-1)k}\equiv 1\pmod p\nonumber \] and multiplying both sides by \(x\) we have \[x^{(p-1)(q-1)k+1}\equiv x\pmod p\nonumber \] That is, by \(\eqref{eq:1}\) \[\label{eq:2} x^{ed}\equiv x\pmod p. \] Now we proved \(\eqref{eq:2}\) when \(\gcd(x,p)=1\), but if \(\gcd(x,p)=p\) it is obvious since then \(x\equiv 0\pmod p\). So in all cases \(\eqref{eq:2}\) holds. A similar argument proves that for all \(x\) \[x^{ed}\equiv x\pmod q.\nonumber \] So by Exercise 15.11, we have since \(\gcd(p,q)=1\) \[x^{ed}\equiv x\pmod m\nonumber \] for all \(x\).

Theorem \(\PageIndex{1}\)

Let \(J_m=\{0,1,2,\dotsc,m-1\}\) and define \(E:J_m\to J_m\) by \[E(x)=x^e\bmod m\nonumber \] and \(D:J_m\to J_m\) by \[D(x)=x^d\bmod m.\nonumber \] Then \(E\) and \(D\) are inverses of each other if \(m\), \(e\) and \(d\) are as in Lemma \(\PageIndex{1}\).

Proof

It suffices to show that \(D(E(x))=x\) for all \(x\in J_m\). Let \(x\in J_m\) and let \(E(x)=x^e\bmod m=r_1\). Also let \(D\left(r_1\right)=r_1^d\bmod m=r_2\). We must show that \(r_2=x\). Since \(x^e \bmod m = r_1\) we know that \[x^e\equiv r_1\pmod m.\nonumber \] Hence \(x^{ed}\equiv r_1^d\pmod m\). We also know that \[r_1^d\equiv r_2\pmod m.\nonumber \] Hence \(x^{ed}\equiv r_2\pmod m\). By Lemma \(\PageIndex{1}\) \(x^{ed}\equiv x\pmod m\) so we have \[x\equiv r_2\pmod m.\nonumber \] Since both \(x\) and \(r_2\) are in \(J_m\) we have by Exercise 15.5 that \(x=r_2\). This completes the proof.

More details on the use of the RSA scheme will be given in the Maple worksheets which are available from the course website which may be reached from my home page: http://www.math.usf.edu/~eclark.

Footnotes

[1] A copy of the paper “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” may be downloaded from http://citeseer.nj.nec.com/rivest78method.html