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)

\begin{align} 73d \equiv 1 \pmod {2464} \end{align}

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

(2)

\begin{align} 2464 = 73(33) + 55 \\ 73 = 55(1) + 18 \\ 55 = 18(3) + 1 \\ 1 = 55 + 18(-3) \\ 1 + 55 + [73 + 55(-1)](-3) \\ 1 = 73(-3) + 55(4) \\ 1 = 73(-3) + [2464 + 73(-33)](4) \\ 1 = 2464(4) + 73(-135) \end{align}

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

(3)

\begin{align} (-135)73d \equiv (-135)1 \pmod {2464} \\ d \equiv -135 \pmod {2464} \\ d \equiv 2329 \pmod {2464} \end{align}

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)

\begin{align} 2160 = 997(2) + 166 \\ 997 = 166(6) + 1 \\ 1 = 997 + 166(-6) \\ 1 = 997 + [2160 + 997(-2)](-6) \\ 1 = 2160(-6) + 997(13) \\ \end{align}

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

(5)

\begin{align} (13)997d \equiv (13)1 \pmod {2160} \\ d \equiv 13 \pmod {2160} \end{align}

Hence our decrypt key d = 13.