# Hill-Chiffre - How can I find the Matrix $X$

This is a problem of classical cryptography: Hill-Chiffre Where the matrix $A$ is the clear message and the matrix $C$ the coded message.

How can I find the Matrix $X$?
Which method I can use?

$$\underbrace{\begin{pmatrix} 15 &4 & 17 \\ 12 &20 & 19\\ 0 &19 &8\\ 14 &13 &18\\ 10 &17 &24\\ 15 &19 &14\\ 18 &24 &18\\ 19 &4 &12\\ \end{pmatrix}}_{A} \cdot X = B\pmod{26} = \underbrace{\begin{pmatrix} 8 &3 &0\\ 18 &1 &23\\ 19 &13 &7\\ 15 &5 &13\\ 11 &23 &17\\ 23 &19 &0\\ 8 &12 &2\\ 16 &24 &5 \end{pmatrix} }_{C}$$

Update - my attempt:

$$X=(A^T \cdot A)^{-1}\cdot A^T \cdot B$$

$$A^T =$$ $\begin{pmatrix} 15 &4 &17\\ 12 &20 &19\\ 0 &19 & 8\\ 14 &13 &18\\ 10 &17 &24\\ 15 &19 &14\\ 18 &24 &18\\ 19 &4 &12\\ \end{pmatrix}^T= \begin{pmatrix} 15 &12 &0 &14 &10 &15 &18 &19\\ 4 &20 &19 &13 &17 &19 &24 &4\\ 17 &19 &8 &18 &24 &14 &18 &12\\ \end{pmatrix}$

$$A^T \times A =$$ $\begin{pmatrix} 15 &12 &0 &14 &10 &15 &18 &19\\ 4 &20 &19 &13 &17 &19 &24 &4\\ 17 &19 &8 &18 &24 &14 &18 &12\\ \end{pmatrix} \times \begin{pmatrix} 15 &4 &17\\ 12 &20 &19\\ 0 &19 & 8\\ 14 &13 &18\\ 10 &17 &24\\ 15 &19 &14\\ 18 &24 &18\\ 19 &4 &12\\ \end{pmatrix}=$

$$\begin{pmatrix} 1575 &1445 &1737\\ 1445 &2188 &1988\\ 1737 &1988 &2278\\ \end{pmatrix} (\mod 26) = \begin{pmatrix} 15 &15 &21\\ 15 &4 &12\\ 21 &12 &16\\ \end{pmatrix}$$

$$(A^T \times A)^{-1} =$$ $$\begin{pmatrix} 15 &15 &21\\ 15 &4 &12\\ 21 &12 &16\\ \end{pmatrix}^{-1}= \begin{pmatrix} \frac{-20}{249} &\frac{1}{83} &\frac{8}{83}\\ \frac{1}{83} &\frac{-67}{332} &\frac{45}{332}\\ \frac{8}{83} &\frac{45}{332} &\frac{-55}{332} \end{pmatrix}$$

$$??$$

• You have to work in the ring mod 26 and not in the field of rational numbers.
– user27950
Oct 11, 2016 at 11:38
• How? when.. $\begin{pmatrix} 15 &15 &21\\ 15 &4 &12\\ 21 &12 &16\\ \end{pmatrix}^{-1}= \begin{pmatrix} \frac{-20}{249} &\frac{1}{83} &\frac{8}{83}\\ \frac{1}{83} &\frac{-67}{332} &\frac{45}{332}\\ \frac{8}{83} &\frac{45}{332} &\frac{-55}{332} \end{pmatrix}$ Oct 11, 2016 at 12:16
• You're matrix is not invertible (mod 26). This shows that the pseudo-inverse method does not work in general. Second, you seem to not understand modular arithmetic. You have first to get familiar with it.
– user27950
Oct 11, 2016 at 12:39

First note that X must be a 3x3 matrix.
Then use the following procedure:
Let $X_k$ be the k'th column of X and $C_k$ the k"th column of C.
Then you can solve the three equations $A X_k = C_k$ by Gaussian elimination:

• There is no submatrix invertible.. :( That is the problem Oct 9, 2016 at 22:34
• Ok, you are right. I modified my answer.
– user27950
Oct 10, 2016 at 3:26
• @Dario Gutierrez: Cryptostasis's modified method is most general. But the submatrix$$\widehat A=\begin{pmatrix}15&4&17\\12&20&19\\14&13&8\end{pmatrix}$$ of $A$ (keeping first, second and fourth lines) is invertible$\pmod{26}$. Then, obviously, $X=\widehat A^{-1}\cdot\widehat B$, where $\widehat B$ keeps the lines of $B$ kept in $\widehat A$.
– fgrieu
Oct 10, 2016 at 7:03

In general case, let $A\cdot X=B$. Then: $${(A^T\cdot A)^{-1}}\cdot A^T\cdot A \cdot X={(A^T\cdot A)^{-1}}\cdot A^T \cdot B$$ So

$$X={(A^T\cdot A)^{-1}}\cdot A^T \cdot B.$$

Edit: Another way to solve this problem is solving bellow equations which are derived from matrix multiplication law( when $A^T\cdot A$ is not invertible, this method is useful):

$$15x_{1,1}+4x_{2,1}+17x_{3,1}=8\\15x_{1,2}+4x_{2,2}+17x_{3,2}=3\\\vdots\\19x_{1,2}+4x_{2,2}+12x_{3,2}=24\\19x_{1,3}+4x_{2,3}+12x_{3,3}=5.$$

• And when the matrix is not invertible? Oct 9, 2016 at 22:38
• The first method works if we replace $A^T$ with any matrix $C$ of the same dimension as $A^T$ is (that is, in the context, 8 lines and 3 columns), and such that $(C\cdot A)$ is invertible. Many choices of $C$ consisting of all-$0$ except a single $1$ in each line and at most one $1$ in each column qualify.
– fgrieu
Oct 10, 2016 at 10:12