Hill cipher

Note: $\: \det(A) = 3$ and $\gcd(3,26) = 1$ , so for each block $X_{j}$ the system $A * X_{j} = B_{j} \bmod{26}$ has a unique solution, where $(1 <= j <= 7)$ . $$

Using seven blocks for $RQTICODEWWMGHI$ we obtain: $$

$17\: 16$ $$

$19 \: 8$ $$

$2 \: 14$ $$

$3 \: 4$ $$

$22 \: 22$ $$

$12 \: 6$ $$

$7 \: 8$ $$

$A * X_{j} = B_{j} \implies X_{j} = A^{-1} * B_{j}$ $$

$C = A|I = \left [\begin{array}{cc|cc} 4 & 5 & 1 & 0 \\ 1 & 2 & 0 & 1 \\ \ \end{array} \right] \bmod{26}$

$$

Using the row operation: $Row_{1} \leftrightarrow Row_{2} \implies$

$C = \left [\begin{array}{cc|cc} 1 & 2 & 0 & 1 \\ 4 & 5 & 1 & 0 \\ \ \end{array} \right] \bmod{26}$ $$

Using the row operation: $22 * Row_{1} + Row_{2} \implies$

$C = \left [\begin{array}{cc|cc} 1 & 2 & 0 & 1 \\ 0 & 23 & 1 & 22 \\ \ \end{array} \right] \bmod{26}$

$$

Using the row operation: $17 * Row_{2} \implies$

$C = \left [\begin{array}{cc|cc} 1 & 2 & 0 & 1\\ 0 & 1 & 17 & 10 \\ \ \end{array} \right] \bmod{26}$ $$

Using the row operation: $24 * Row_{2} + Row_{1} \implies$

$C = \left [\begin{array}{cc|cc} 1 & 0 & 18 & 7\\ 0 & 1 & 17 & 10 \\ \ \end{array} \right] \bmod{26}$

$$

$\implies$

$A^{-1} = \left [\begin{array}{cc|c} 18 & 7\\ 17 & 10 \\ \ \end{array} \right] \bmod{26}$

$$

Note: $A * A^{-1} = I$

Deciphering the first block $\left [\begin{array}{cc|c} 17 \\ 16 \\ \ \end{array} \right] \textbf{:}$ $$

$X_{1} = A^{-1} * B_{1} \bmod{26} = \left [\begin{array}{cc|c} 18 & 7\\ 17 & 10 \\ \ \end{array} \right] * \left [\begin{array}{cc|c} 17 \\ 16 \\ \ \end{array} \right] \bmod{26} = \left [\begin{array}{cc|c} 2 \\ 7 \\ \ \end{array} \right] \bmod{26}$ : $$

Deciphering the second block $\left [\begin{array}{cc|c} 19 \\ 8 \\ \ \end{array} \right] \textbf{:}$ $$ $$

$X_{2} = A^{-1} * B_{2} \bmod{26} = \left [\begin{array}{cc|c} 18 & 7\\ 17 & 10 \\ \ \end{array} \right] * \left [\begin{array}{cc|c} 19 \\ 8 \\ \ \end{array} \right] \bmod{26} = \left [\begin{array}{cc|c} 8 \\ 13 \\ \ \end{array} \right] \bmod{26}$ $$

Repeat the same procedure for the remaining five blocks. $$

Our deciphered blocks are: $$

$2 \: 7$ $$

$8 \: 13$ $$

$4 \: 18$ $$

$4 \: 13$ $$

$4 \: 22$ $$

$24 \: 4$ $$

$0 \: 17$ $$

Our plain text message is:

$CHINESENEWYEAR$

$$

As a string of integers we have: $27813418413422244017$ . $$

$$

$\textbf{ The Chinese New Year is on January 28, 2017.}$

My approach was the same as Rocco, except for two things.

First off, I wasn't sure whether the given matrix was the enciphering matrix or deciphering matrix. I tried it as the deciphering matrix and got the first two letters SX which seemed unlikely.

So we need to find the inverse matrix - but with integers and mod 26. I wasn't sure how to do this so took a different approach.

I worked out the inverse matrix (in my view more conventionally?) as:

$\frac13 \left[ {\begin{array}{cc} 2 & -5 \\ -1 & 4 \ \end{array} } \right]$ .

This means that $\left[ {\begin{array}{cc} 4 & 5 \\ 1 & 2 \ \end{array} } \right]\left[ {\begin{array}{cc} 2 & -5 \\ -1 & 4 \ \end{array} } \right]=\left[ {\begin{array}{cc} 3 & 0 \\ 0 & 3 \ \end{array} } \right]$ .

Now, as $3\times 9 = 27 = 1 \mod 26$ , we can calculate:

$9\times\left[ {\begin{array}{cc} 2 & -5 \\ -1 & 4 \ \end{array} } \right]=\left[ {\begin{array}{cc} 18 & -45 \\ -9 & 36 \ \end{array} } \right]=\left[ {\begin{array}{cc} 18 & 7 \\ 17 & 10 \ \end{array} } \right]\mod 26$ .

From here, I proceeded as Rocco did...