The Rivest-Shamir-Adleman public key system

A sets up a system so that anyone can send him an encoded message, but only A will be able to decode it. The message is represented as a number $M$. The encoding is done by a publicly known function $f(M)$, with A the only person who knows how to compute $f^{-1}$. A chooses two large primes $p$, $q$ which he keeps secret. He announces $n=pq$ and another number $d$, with $(d,p-1)=(d,q-1)=1$ (one way to do this is to choose $d$ a prime larger than $p/2$ and $q/2$.) The encoding is

$$f(M){\equiv} M^d\hbox{ mod n}$$

where $M$ and $f(M)$ are both $\le n-1$. We have seen $f$ can be computed in a realistic amount of time even if $M$, $d$, $n$ are many digits long.

A computes $M$ from $M^d$ using his knowledge of $p$, $q$. By Corollary 8,

$$\hbox{If }{de}\equiv{1}\hbox{ (mod }{(p-1)})\hbox{ then }{\left(M^d\right)^e}\equiv{1}\hbox{ (mod }{p})$$

Similarly ${\left(M^d\right)^e}\equiv{M}\hbox{ (mod }{q})$ if ${de}\equiv{1}\hbox{ (mod }{(q-1)})$. $e$ satisfies these two conditions if ${ed}\equiv{1}\hbox{ (mod }{(p-1)(q-1)})$. Theorem 1 says we can let $e=x$, where $x$ is a solution of

$$dx+(p-1)(q-1)y=1$$

Since $\left(M^d\right)^e-M$ is divisible by $p$ and by $q$, it is divisble by $pq$, hence we can recover $M$ from $M^d$ by taking to the $e$-th power mod $pq$.

It is crucial to the security of this system that knowledge of $n$ does not allow an eavesdropper to calculate $p$ and $q$. The crude approach of dividing $n$ by all numbers up to $\sqrt n$ would take $\sim10^{50}$ steps for a 100-digit $n$. However, many famous mathematicians have been unable to devise significantly better factoring algorithms, and this problem has been studied for at least 100 years.

One practical difficulty in using this system is the need to do calculations with many-digit numbers, especially to find primes. Another difficulty is that the inventors of this system have patented it. Amateur programmers who have posted implementations on electronic bulletin boards have received letters from ``RSA Security, Inc'' warning of possible patent infringement.