![]() | ![]() |
Find the decoding key d for the code whose published values of N and e are
N=233570063,e=125
First, we need to find ϕ(n). This requires factoring n=7387. Fortunately, n is fairly small in this case, and factors easily upon trial division into n=83⋅89.
We know that ϕ(pq)=ϕ(p)ϕ(q) when gcd. 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 = 7216Now, 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"}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.