Finding a 2x2 matrix of a block cipher using two decoded groups

Question

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 2x2 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?

Answer 1

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\ $?

Answer 2

Note that we have\begin{align}\begin{bmatrix} 19 & 7 \\ 7 & 4\end{bmatrix}^{-1} &= (19 \cdot 4 - 7^2)^{-1}\begin{bmatrix} 4 & -7 \\ -7 & 19\end{bmatrix}\\&=(-7\cdot 4 - 7^2)^{-1}\begin{bmatrix} 4 & -7 \\ -7 & -7\end{bmatrix} \\ &= (-77)^{-1}\begin{bmatrix} 4 & -7 \\ -7 & -7\end{bmatrix} \\ &= (-26 \cdot3+1)^{-1}\begin{bmatrix} 4 & -7 \\ -7 & -7\end{bmatrix}\\ &=\begin{bmatrix} 4 & -7 \\ -7 & -7\end{bmatrix}\end{align}

By post-multiplying this matrix to both sides, you should be able to recover your desired matrix.