Examples of Decrypting with RSA

We have already looked at how to encrypt plaintext P given the public information [n, e] into ciphertext C. We are now going to look at some examples of decrypting C back into plaintext given the decryption key d. We note the following congruence holds:

(1)

\begin{align} P \equiv C^d \pmod {n} \end{align}

Example 1

Given the public information [n, e] = [143, 11] and the decryption key d = 11, decrypt the ciphertext C = 106.

We know that $P \equiv C^d \pmod {n}$, or more appropriately, $P \equiv 106^{11} \pmod {143}$. We note that we don't even need the encryption key e in these scenarios. We will now evaluate this congruence as follows:

(2)

\begin{align} 106 \equiv 106 \pmod {143} \\ 106^2 = 11236 \equiv 82 \pmod {143} \\ 106^4 \equiv (82)^2 = 6724 \equiv 3 \pmod {143} \\ 106^8 \equiv (3)^2 =9 \equiv 9 \pmod {143} \\ 106^{11} \equiv (9)(82)(106) = 78228 \equiv 7 \pmod {143} \end{align}

Hence our plaintext P = 7. We note this to be true since we have already encrypted P = 7 on a previous example for encryption. Hence when decrypting C, we get P back as a result.

Example 2

Given the public information [n, e] = [391, 13] and that the decryption key d = 325, decrypt the ciphertext C = 213.

By the congruence, we know that $P \equiv 213^{325} \pmod {391}$. We will now evaluate this congruence as follows:

(3)

\begin{align} 213 \equiv 213 \pmod {391} \\ 213^2 = 45369 \equiv 13 \pmod {391} \\ 213^4 \equiv (13)^2 = 169 \equiv 169 \pmod {391} \\ 213^8 \equiv (169)^2 = 28561 \equiv 18 \pmod {391} \\ 213^{16} \equiv (18)^2 = 324 \equiv 324 \pmod {391} \\ 213^{32} \equiv (324)^2 = 104976 \equiv 188 \pmod {391} \\ 213^{64} \equiv (188)^2 = 35344 \equiv 154 \pmod {391} \\ 213^{128} \equiv (154)^2 = 23716 \equiv 256 \pmod {391} \\ 213^{256} \equiv (256)^2 = 65536 \equiv 239 \pmod {391} \\ \quad 213^{325} = 213^{256} \cdot 213^{64} \cdot 213^{4} \cdot 213 \equiv (239)(154)(169)(213) \equiv 1324905582 \equiv 123 \pmod {391} \end{align}

Hence our plaintext P = 127.