RSA Encryption

RSA encryption is a form of public key encryption cryptosystem utilizing Euler's totient function, $\phi$, primes and factorization for secure data transmission. For RSA encryption, a public encryption key is selected and differs from the secret decryption key.

RSA Key Creations

The algorithm for creating a decryption key is as follows:

Step 1	First select two large primes. We will denote these primes as p and q.
Step 2	Multiply p and q together. Their product will be denoted $n = pq$.
Step 3	Using Euler's totient function, determine $\phi (n) = \phi (p) \phi (q)$.
Step 4	Select an integer e such that $(e, \phi (n) ) = 1$ (e and $\phi (n)$ must be relatively prime).
Step 5	Find d such that $ed \equiv 1 \pmod {\phi (m)}$. This will be the secret decryption key.
Step 6	Public [n, e] and keep the decryption key secret.

Example 1

Create a public decryption key with the primes p = 13 and q = 23.

We will go through the process step by step.

Step 1	We already were given two primes to work with. In our example, the primes p = 13 and q = 23 are not necessarily "large" primes, however, for the purpose of simple calculations we will use these.
Step 2	The product of p = 13 and q = 23 is 299. So $n = pq = 299$.
Step 3	Now using Euler's totient function, $\phi (299) = \phi (13) \phi (23) =(12)(22) = 264$.
Step 4	We must now select an integer e such that $(e, 264) = 1$. Let's select the prime e = 17 since $(e, \phi (299)) = (e, 264) = (17, 264) = 1$. Note that any e such that $(e, \phi (n)) = 1$ will work.
Step 5	We will now have to solve the congruence $17d \equiv 1 \pmod {264}$. This can be done using the division algorithm to find the modular inverse of 17 (mod 264). We will omit showing this, but through the division algorithm we'll find that 233 is a modular inverse of 17 (mod 264). Hence $(233)17d \equiv (233)1 \pmod {264}$. Hence $d \equiv 233 \pmod {264}$. Hence, our decryption key d = 233.
Step 6	We will now public the public information [n, e] = [299, 17], and keep our decryption key d a secret.

Encryption

Suppose that we want to send a message P that is a least residue (mod n). We would first look up the public information [n, e] and would then calculate:

(1)

\begin{align} C \equiv P^e \pmod n \end{align}

We would then send the cyphertext C. If the recipient of the cyphertext has the decryption key d, then they could decrypt the cyphertex C by calculating:

(2)

\begin{align} P \equiv C^d \pmod n \end{align}

RSA Key Decryption

The algorithm for finding the decryption key d from the public information [n, e] is as follows:

Step 1	Look up the public information [n, e]
Step 2	Factor n into primes p and q such that $n = pq$. Note that for very large primes n, this may take a long time.
Step 3	Determine the value for $\phi (n)$
Step 4	Solve the linear congruence $ed \equiv 1 \pmod {\phi (n)}$. The least residue $x \pmod {\phi (n)}$ will be the decryption key.

Example 2

Find the decryption key, d given the public information [n, e] = [299, 17].

Step 1	The public information in this example is [n, e] = [299, 17]. So n = 299 and e = 17.
Step 2	Factoring 299 we obtain $299 = 13 \cdot 23$. So our primes p and q are p = 13, and q = 23.
Step 3	Using Euler's totient function, $\phi (299) = \phi (13) \phi (23) = (12)(22) = 264$.
Step 4	We now need to solve the linear congruence $17d \equiv 1 \pmod {\phi (n)}$. We thus obtain that our decryption key d = 233 after solving this. So we have found our decryption key.