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

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$
3
  • $\begingroup$ There is no submatrix invertible.. :( That is the problem $\endgroup$ 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.$$

$\endgroup$
2
  • 1
    $\begingroup$ And when the matrix is not invertible? $\endgroup$ 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 you have read our privacy policy.

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