Additional Examples of Creating RSA Decryption Keys

# Additional Examples of Creating RSA Decryption Keys

Recall the algorithm for creating an RSA decryption key:

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

We will now apply this algorithm in the following examples omitting step 1 and 4 as this will be given in the example questions, and step 6 is unnecessary.

## Example 1

Create a decryption key given p = 641, q = 853, and e = 11

We first multiple pq to obtain n, as n = pq = 546773. We now want to calculate $\phi (n)$ as follows:

(1)
\begin{align} \phi (546773) = \phi (641) \phi (853) \\ \phi (546773) = (640)(852) \\ \phi (546773) = 545280 \end{align}

We note that our selected e = 11 is relatively prime to 545280 and 11 is not a factor of 545280. Hence (11, 545280) = 1.

We now want to solve the congruence $11d \equiv 1 \pmod {545280}$. We can solve this by finding a multiplicative inverse of 11 (mod 545280) by the division algorithm.

(2)
\begin{align} 545280 = 11(49570) + 10 \\ 11 = 10(1) + 1 \\ 1 = 11 + 10(-1) \\ 1 = 11 + [545280 + 11(-49570)](-1) \\ 1 = 545280(-1) + 11(49571) \end{align}

Hence we can use 49571 as our inverse. Hence it follows that:

(3)
\begin{align} (49571) 11d \equiv (49571) 1 \pmod {545280} \\ d \equiv 49571 \pmod {545280} \end{align}

Hence our decryption key d = 49571.