Exercises - RSA and Public Key Codes

Decrypt, by hand, the following RSA-encoded message ($N=7387, \quad e=1357$):
$$2133 \quad 429 \quad 1126$$
You may assume the following was used to equate letter pairs with numbers:
$$\begin{array}{ccccccccccccc}
A & B & C & D & E & F & G & H & I & J\\
11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20
\end{array}$$
$$\begin{array}{cccccccccc}
K & L & M & N & O & P & Q & R & S & T\\
21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30
\end{array}$$
$$\begin{array}{ccccccccccccc}
U & V & W & X & Y & Z\\
31 & 32 & 33 & 34 & 35 & 36
\end{array}$$

First, we need to find $\phi(n)$. This requires factoring $n=7387$. Fortunately, $n$ is fairly small in this case, and factors easily upon trial division into $n = 83 \cdot 89$.

We know that $\phi(pq) = \phi(p) \phi(q)$ when $\gcd(p,q)=1$. Note, $\gcd(83,89)=1$, so $\phi(7387) = \phi(83)\phi(89)$.

Further, $\phi(p^k) = p^k - p^{k-1}$ for any prime, $p$, so $\phi(83) = 82$ and $\phi(89) = 88$. Thus,

$$\phi(7387) = 82 \cdot 88 = 7216$$

Now, we need to find $d$, the multiplicative inverse$\pmod{\phi(n)}$ of $e=1357$. That is to say, we need to find an integer $d$ such that $ed \equiv 1 \pmod{\phi(n)}$. Towards this end, we first apply the Euclidean Algorithm:

$$\begin{align} 7216 &= 5 \cdot 1357 + 431\\ 1357 &= 3 \cdot 431 + 64\\ 431 &= 6 \cdot 64 + 47\\ 64 &= 1 \cdot 47 + 17\\ 47 &= 2 \cdot 17 + 13\\ 17 &= 1 \cdot 13 + 4\\ 13 &= 3 \cdot 4 + \fbox{1} \leftarrow \textrm{gcd}\\ 3 &= 3 \cdot 1 + 0 \end{align}$$

Notice, as hoped for, $\gcd(\phi(n),e)=1$. Remember, we are after the integer $d$ such that $ed \equiv 1 \pmod{\phi(n)}$. So, we need to solve

$$1357d \equiv 1 \pmod{7216}$$

This, of course, can be done by finding integers $x$ and $y$ that satisfy $1357x + 7216y = 1$, which we do in the usual way:

$$\begin{align} 1 &= 13 - 3 \cdot 4\\ 1 &= 13 - 3 \cdot (17 - 13)\\ 1 &= 4 \cdot 13 - 3 \cdot 17\\ 1 &= 4 \cdot (47 - 2 \cdot 17) - 3 \cdot 17\\ 1 &= 4 \cdot 47 - 11 \cdot 17\\ 1 &= 4 \cdot 47 - 11 \cdot (64 - 47)\\ 1 &= 15 \cdot 47 - 11 \cdot 64\\ 1 &= 15 \cdot (431 - 6 \cdot 64) - 11 \cdot 64\\ 1 &= 15 \cdot 431 - 101 \cdot 64\\ 1 &= 15 \cdot 431 - 101 \cdot (1357 - 3 \cdot 431)\\ 1 &= 318 \cdot 431 - 101 \cdot 1357\\ 1 &= 318 \cdot (7216 - 5 \cdot 1357) - 101 \cdot 1357\\ 1 &= 318 \cdot 7216 - 1691 \cdot 1357 \end{align}$$

Thus, $d \equiv -1691 \pmod{7216}$ solves $1357d \equiv 1 \pmod{7216}$. Of course, it will be helpful if the particular solution we will use is positive, so we will work with $d = -1691 + 7216 = 5525$.

Now, if $a_1, a_2, a_3$ is the secret message and if it was RSA-encoded with modulus $n=7387$, and encrypting key $e=1357$, then we know that:

$$\begin{align} (a_1)^{1357} &\equiv 2133\pmod{7387}\\ (a_2)^{1357} &\equiv 429\pmod{7387}\\ (a_3)^{1357} &\equiv 1126\pmod{7387} \end{align}$$

Consider the first of these congruences. If we raise both sides to the $x=5525$ power, notice that we get a solution for $a_1$:

$$\begin{align} \left((a_1)^{1357}\right)^{5525} &\equiv 2133^{5525} \pmod{7387}\\ (a_1)^{7497425} &\equiv 2133^{5525} \pmod{7387}\\ (a_1)^{7216 \cdot 1039 + 1} &\equiv 2133^{5525} \pmod{7387}\\ \left( (a_1)^{\phi(7387)} \right)^{1039} \cdot (a_1)^1 &\equiv 2133^{5525} \pmod{7387}\\ 1^{1039} \cdot a_1 &\equiv 2133^{5525} \pmod{7387} \quad \textrm{(by Euler's Thm.)}\\ a_1 &\equiv 2133^{5525} \pmod{7387}\\ \end{align}$$

The other two congruences involving $a_2$ and $a_3$ work out in a similar way.

Note: there is no need to re-verify the calculation immediately above for any given RSA decryption. By design, given that we ensured $ed \equiv 1 \pmod{\phi(n)}$, the reduction from a sizable power of $a_i$ down to simply $a_i$ by itself always happens. As a matter of practice, once we have found the value of $d$, we generally just raise each number in our encrypted message to the $d$ power.

So we must find the values of:

$$2133^{5525}, 429^{5525}, \textrm{ and } 1126^{5525} \pmod{7387}$$

We use the method of successive squaring$\pmod{7387}$ to do this efficiently:

$$\begin{array}{c|c|c|c} n & 2133^n & 429^n & 1126^n\\\hline\hline 1 & 2133 & 429 & 1126\\\hline 2 & 6684 & 6753 & 4699\\\hline 4 & 6667 & 3058 & 858\\\hline 8 & 1310 & 6809 & 4851\\\hline 16 & 2316 & 1669 & 4606\\\hline 32 & 894 & 662 & 7159\\\hline 64 & 1440 & 2411 & 275\\\hline 128 & 5240 & 6739 & 1755\\\hline 256 & 121 & 6232 & 7033\\\hline 512 & 7254 & 4365 & 7124\\\hline 1024 & 2915 & 2152 & 2686\\\hline 2048 & 2175 & 6842 & 4884\\\hline 4096 & 2945 & 1545 & 833\\\hline \end{array}$$

Now we simply observe that when expressed as a sum of powers of two, $5525 = 4096 + 1024 + 256 + 128 + 16 + 4 + 1$.

As such, using the expressions for these powers as given in the table above...

$$\begin{align} 2133^{5525} &\equiv 2945 \cdot 2915 \cdot 121 \cdot 5240 \cdot 2316 \cdot 6667 \cdot 2133 \equiv 2431 \pmod{7387}\\ 429^{5525} &\equiv 1545 \cdot 2152 \cdot 6232 \cdot 6739 \cdot 1669 \cdot 3058 \cdot 429 \equiv 2312 \pmod{7387}\\ 1126^{5525} &\equiv 833 \cdot 2686 \cdot 7033 \cdot 1755 \cdot 4606 \cdot 858 \cdot 1126 \equiv 1528 \pmod{7387}\\ \end{align}$$

Note: To avoid calculator error, one should find the products above one pair at a time, reducing the result$\pmod{7387}$ at each step.

Hence, the original values of $a_1$, $a_2$, and $a_3$ are: $$2431, 2312, 1528$$ Knowing that these numbers must ultimately be turned back into letters, we split each number into two: $$24,\ 31,\ 23,\ 12,\ 15,\ 28$$ so that we can look up the letter equivalents (in the table given in the problem):

$$\textrm{"N" "U" "M" "B" "E" "R"}$$

Thus, our decrypted message is

$$\textrm{"NUMBER"}$$