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)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)Hence we can use 49571 as our inverse. Hence it follows that:
(3)Hence our decryption key d = 49571.