Exercises - RSA and Public Key Codes

1. Find the decoding key $d$ for the code whose published values of $N$ and $e$ are
$$N = 233570063, e = 125$$

2. 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"}$$

3. Presume that a plaintext message is converted to a number by making the following substitutions:
blank = $99$, $A = 10$, $B = 11$, ..., $Z=35$. Decode, the following message. It is a quotation from Shakespeare's "Hamlet". The coded message consists of four integers
$$\begin{array}{r} 39 \; 25736 \; 57380 \; 83976\\ 8 \; 66571 \; 70599 \; 56870\\ 14569 \; 39934 \; 49451\\ 14 \; 57541 \; 36754 \; 04137 \end{array}$$
The public key used for encryption was
$$(N = 59 \; 11142 \; 11035 \; 79513, e = 123)$$

Hint: Don't do this one by hand. You may find it useful to use the Mathematica functions GCD, PowerMod, and FactorInteger in combination with www.wolframalpha.com. Look these functions up! Pay special attention to PowerMod, as it can be used not only to speed up successive squaring, but also to find multiplicative inverses in a given mod.