# Additional Examples of Finding RSA Decryption Keys

First let's recall the algorithm for finding the decryption key d for RSA:

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 $d \pmod {\phi (n)}$ will be the decryption key. |

We will now apply this algorithm in the following examples.

## Example 1

**Given the public information [n, e] = [2599, 73], find the decrypt key d.**

First, we must factor 2599 into its two prime factors. We find that $2599 = 23 \cdot 113$. We now determine that $\phi (2599) = \phi (23) \phi (113) = (22)(112) = 2464$. Now we want to solve the following linear congruence:

(1)We can solve this linear congruence by finding a modular inverse of 73 (mod 2464) by the division algorithm as follows:

(2)Hence -135 can be used as a modular inverse. We thus get that:

(3)Hence our decryption key d = 2329.

## Example 2

**Given the public information [n, e] = [2257, 997], find the decryption key d.**

We will first factor 2257 into its two prime constituents. We note that $2257 = 37 \cdot 61$. We note calculate that $\phi( 2257) = \phi (37) \phi (61) = (36)(60) = 2160$.

We now want to solve the linear congruence $997d \equiv 1 \pmod {2160}$. We can do this by finding a modular inverse of 997 (mod 2160) by the division algorithm as follows:

(4)Hence we can use 13 as an inverse to 997 (mod 2160). It hence follows that:

(5)Hence our decrypt key d = 13.