The RSA Algorithm

With that bit of number theory under our belts, we are ready to tackle the RSA algorithm. Here is how it goes. Bob wants to send me an encrypted message. The RSA algorithm has the following steps.

1. I create a large number $N$ by multiplying together two fairly large prime numbers $p$ and $q$; so $N = pq$.

2. I also create an encryption key $K$ with $K < N$ and check that $K$ has no common factors (other than $1$) with $(p − 1)(q − 1)$. I send the integers $K$ and $N$ to Bob. I may use an unencrypted channel to do so.

3. Let’s assume that Bob expresses his message as a number $m$. Using the values of $K$ and $N$ I have sent him, Bob calculates another number $c$ such that $c = m^K \mod N$ and sends the number $c$ to me.

4. In the meantime, I have calculated an integer $d$ such that

$$1 = Kd \bmod (p − 1)(q − 1),$$

which means that $(p − 1)(q − 1)$ divides $K d − 1$ evenly, that is, with no remainder. I need the two prime numbers $p$ and $q$ to calculate $d$.

5. To decode the message from Bob, I solve $m = c^d \bmod N$.