-1
$\begingroup$

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}$$

Many thanks in advance.


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}$$

$$??$$

$\endgroup$
  • 2
    $\begingroup$ You have to work in the ring mod 26 and not in the field of rational numbers. $\endgroup$ – user27950 Oct 11 '16 at 11:38
  • $\begingroup$ 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}$ $\endgroup$ – Darío A. Gutiérrez Oct 11 '16 at 12:16
  • 2
    $\begingroup$ 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. $\endgroup$ – user27950 Oct 11 '16 at 12:39
3
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ There is no submatrix invertible.. :( That is the problem $\endgroup$ – Darío A. Gutiérrez Oct 9 '16 at 22:34
  • $\begingroup$ Ok, you are right. I modified my answer. $\endgroup$ – user27950 Oct 10 '16 at 3:26
  • 1
    $\begingroup$ @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$. $\endgroup$ – fgrieu Oct 10 '16 at 7:03
1
$\begingroup$

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.$$

$\endgroup$
  • 1
    $\begingroup$ And when the matrix is not invertible? $\endgroup$ – Darío A. Gutiérrez Oct 9 '16 at 22:38
  • $\begingroup$ 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. $\endgroup$ – fgrieu Oct 10 '16 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.