A cryptoanalist, while trying to decipher a message, found that the
most frequent blocks were RH and NI, which must correspond to TH and
HE, which are the most common in the english language. Supposing the
text was codified using a 2×2 block cipher, what was the used matrix?
I know that
$\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}T&H\\H&E\end{bmatrix} =\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}19&7\\7&4\end{bmatrix} = \begin{bmatrix}R&N\\H&I\end{bmatrix}=\begin{bmatrix}17&13\\7&8\end{bmatrix} \pmod{26}$
I got as far as making a system of equations but that didn't get me anywhere. How do I solve this?
Best Answer
The equation $$ \begin{bmatrix} a&b\\c&d \end{bmatrix} \begin{bmatrix} 19&7\\7&4 \end{bmatrix} \equiv \begin{bmatrix} 17&13\\7&8 \end{bmatrix} \pmod{26} $$ gives you four equations in the four unknowns $\ a,b,c,d\ $. Two of these equations, \begin{align} 19a+7b&\equiv17\pmod{26}\\ 7a+4b&\equiv13\pmod{26}\ , \end{align} contain only $\ a\ $ and $\ b\ $, while the other two contain only $\ c\ $ and $\ d\ $.
You can solve these equations by Gaussian elimination, just like you do for linear equations in real numbers, except that you use arithmetic modulo $26$ instead of normal arithmetic. In arithmetic modulo $26$, besides not being able to divide by $0$, you can't divide by $26$, $2$, or $13$ either (unless, in the latter two cases, you divide the modulus as well as both sides of the equation). Division by any other number, $\ m\ $ modulo $26$ requires you to compute its reciprocal, $\ m^{-1}\ $, modulo $26$ and multiply by that. Reciprocals can be computed efficiently with the Euclidean algorithm, but if you're not familiar with that algorithm, it's not all that tedious to find them by trial and error.
For the above equations, if you add the second to the first, you get \begin{align} 26a+11b \equiv 11b&\equiv 30 \pmod{26}\\ &\equiv 4 \pmod{26}\ . \end{align} The reciprocal of $11$ modulo $26$ is $19$ (check: $11\cdot19\equiv$$ -11\cdot7\equiv$$-77\equiv1\pmod{26}\ $). So you get $$ 19\cdot 11b\equiv b\equiv19\cdot4\equiv-7\cdot4\equiv-2\equiv24\pmod{26}\ . $$ Now substituting $\ b\equiv-2\ $ back into the second of the above equations, you get $$ 7a-8\equiv 13\pmod{26}\ \text{, or}\\ 7a\equiv 21 \pmod{26}\ . $$ Here, you don't even need to compute the reciprocal of $7$ modulo $26$ to solve for $\ a\ $. Because $\ 21=7\cdot3\ $, you can immediately deduce $\ a=3\ $.
Can you now solve the other two equations to find $\ c\ $ and $\ d\ $?