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

$$??$$

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You have to work in the ring mod 26 and not in the field of rational numbers. $\endgroup$
    – user27950
    Oct 11, 2016 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, 2016 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, 2016 at 12:39

2 Answers 2

Reset to default
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:

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ And when the matrix is not invertible? $\endgroup$
    – Darío A. Gutiérrez
    Oct 9, 2016 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, 2016 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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