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.
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.

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.