Hill Cipher - Trigraph Block Frequencies

You can verify that all 4 matrices will work. $$

Prior to verification, I show how each matrix was constructed.

To construct each matrix: $$

Let $A = [a_{ij}]_{3 \: X \: 3},$ . $$

Using $A * P_{j} \equiv C_{j} \mod 26,$ , where $(1 <= j <= 3)$ enciphering each plaintext block we obtain the three $3 \: X \: 3$ systems of linear congruence's below: $$

$19 * a_{11} + 7 * a_{12} + 4 * a_{13} = 11 \mod{26}$ $13 * a_{12} + 3 * a_{13} = 22 \mod{26}$ $19 * a_{11} + 7 * a_{12} = 25 \mod{26}$ $$

$$ $19 * a_{21} + 7 * a_{22} + 4 * a_{23} = 12 \mod{26}$ $13 * a_{22} + 3 * a_{23} = 17 \mod{26}$ $19 * a_{21} + 7 * a_{22} = 24 \mod{26}$ $$

$$ \ $19 * a_{31} + 7 * a_{32} + 4 * a_{33} = 4 \mod{26}$ $13 * a_{32} + 3 * a_{33} = 8 \mod{26}$ $19 * a_{31} + 7 * a_{32} = 2 \mod{26}$ $$

Setting up the augmented matrix $B$ we obtain: $$

$B = \left[ \begin{array}{ccc|ccc} 19 & 7 & 4 & 11 & 12 & 4\\ 0 & 13 & 3 & 22 & 17 & 8\\ 19 & 7 & 0 & 25 & 24 & 2\\ \ \end{array} \right] \mod{26}$
$$

$Row_{2} \leftrightarrow Row_{3} \implies$ $$

$B = \left[ \begin{array}{ccc|ccc} 19 & 7 & 4 & 11 & 12 & 4\\ 19 & 7 & 0 & 25 & 24 & 2\\ 0 & 13 & 3 & 22 & 17 & 8 \ \end{array} \right] \mod{26}$ $$

$11 * Row_{1} \implies$ $$

$B = \left[ \begin{array}{ccc|ccc} 1 & 25 & 18 & 17 & 2 & 18\\ 19 & 7 & 0 & 25 & 24 & 2\\ 0 & 13 & 3 & 22 & 17 & 8 \ \end{array} \right] \mod{26}$ $$

$7 * Row_{1} + Row_{2} \implies$ $$

$B = \left[ \begin{array}{ccc|ccc} 1 & 25 & 18 & 17 & 2 & 18\\ 0 & 0 & 22 & 14 & 12 & 24\\ 0 & 13 & 3 & 22 & 17 & 8 \ \end{array} \right] \mod{26}$ $$

$9 * Row_{3} \implies$ $$

$B = \left[ \begin{array}{ccc|ccc} 1 & 25 & 18 & 17 & 2 & 18\\ 0 & 0 & 22 & 14 & 12 & 24\\ 0 & 13 & 1 & 16 & 23 & 20 \ \end{array} \right] \mod{26}$ $$

$8 * Row_{3} + Row_{1} \implies$ $$

$B = \left[ \begin{array}{ccc|ccc} 1 & 25 & 0 & 15 & 4 & 22\\ 0 & 0 & 22 & 14 & 12 & 24\\ 0 & 13 & 1 & 16 & 23 & 20 \ \end{array} \right] \mod{26}$ $$

$4 * Row_{3} + Row_{2} \implies$ $$

$B = \left[ \begin{array}{ccc|ccc} 1 & 25 & 0 & 15 & 4 & 22\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 13 & 1 & 16 & 23 & 20 \ \end{array} \right] \mod{26}$ $$

From the above matrix we obtain: $$

$$

$a_{11} + 25 * a_{12} \equiv 15 \mod{26}$ $$

$a_{21} + 25 * a_{22} \equiv 4 \mod{26}$ $$

$a_{31} + 25 * a_{32} \equiv 22 \mod{26}$ $$

Since $a_{j2}$ is an arbitrary variable let: $$

$a_{12} \equiv 13 \mod{26}$ $$

$a_{22} \equiv 23 \mod{26}$ $$

$a_{32} \equiv 3 \mod{26}$

$\implies$

$a_{11} \equiv 15 - 25 * 13 \mod{26} \equiv -310 \mod{26} \equiv -24 \mod{26} \equiv 2 \mod{26}$ $$

$a_{21} \equiv 1 \mod{26}$ $$

$a_{31} \equiv 25 \mod{26}$ $$

and since $a_{12}, a_{22}, and a_{32}$ are odd $\implies$

$13 + a_{13} \equiv 16 \mod 26$ $$

$13 + a_{23} \equiv 23 \mod{26}$ $$

$13 + a_{33} \equiv 20 \mod{26}$ $$

$\implies$ $$

$a_{13} \equiv 3 \mod{26}$ $$

$a_{23} \equiv 10 \mod{26}$ $$

$a_{33} \equiv 7 \mod{26}$ $$

$\therefore$ for the first matrix we obtain: $$

$A = \left[ \begin{array}{ccc} 2 & 13 & 3\\ 1 & 23 & 10\\ 25 & 3 & 7\\ \ \end{array} \right] \mod{26}$
$$

For the second matrix let: $$

$a_{12} \equiv 1 \mod{26}$ $$

$a_{22} \equiv 1 \mod{26}$ $$

$a_{32} \equiv 1 \mod{26}$

$\implies$

$a_{11} \equiv -20 \mod{26} \equiv 16 \mod{23}$ $$

$a_{21} \equiv 5 \mod{26}$ $$

$a_{31} \equiv 23 \mod{26}$ $$

and,

$a_{13} \equiv 3 \mod{26}$ $$

$a_{23} \equiv 10 \mod{26}$ $$

$a_{33} \equiv 7 \mod{26}$ $$

$\therefore$ for the second matrix we obtain: $$

$A = \left[ \begin{array}{ccc} 16 & 1 & 3\\ 5 & 1 & 10\\ 23 & 1 & 7\\ \ \end{array} \right] \mod{26}$
$$

For the third matrix let: $$

$a_{12} \equiv 1 \mod{26}$ $$

$a_{22} \equiv 2 \mod{26}$ $$

$a_{32} \equiv 3 \mod{26}$

$\implies$

$a_{11} \equiv 16 \mod{23}$ $$

$a_{21} \equiv 6 \mod{26}$ $$

$a_{31} \equiv 25 \mod{26}$ $$

and,

$a_{13} \equiv 3 \mod{26}$ $$

$a_{23} \equiv 23 \mod{26}$ $$

$a_{33} \equiv 7 \mod{26}$ $$

$\therefore$ for the third matrix we obtain: $$

$A = \left[ \begin{array}{ccc} 16 & 1 & 3\\ 6 & 2 & 23\\ 23 & 3 & 7\\ \ \end{array} \right] \mod{26}$
$$

For the fourth matrix let: $$

$a_{12} \equiv 3 \mod{26}$ $$

$a_{22} \equiv 2 \mod{26}$ $$

$a_{32} \equiv 1 \mod{26}$

$\implies$

$a_{11} \equiv 18 \mod{23}$ $$

$a_{21} \equiv 6 \mod{26}$ $$

$a_{31} \equiv 23 \mod{26}$ $$

and,

$a_{13} \equiv 3 \mod{26}$ $$

$a_{23} \equiv 23 \mod{26}$ $$

$a_{33} \equiv 7 \mod{26}$ $$

$\therefore$ for the fourth matrix we obtain: $$

$A = \left[ \begin{array}{ccc} 18 & 3 & 3\\ 6 & 2 & 23\\ 23 & 1 & 7\\ \ \end{array} \right] \mod{26}$
$$

Note for all four cases $(\det(A), 26) = 1$ .

For the first matrix we obtain: $$

$\left[ \begin{array}{ccc} 2 & 13 & 3 \\ 1 & 23 & 10 \\ 25 & 3 & 7 \\ \ \end{array} \right] * \left[ \begin{array}{ccc} 19 & 0 & 19 \\ 7 & 13 & 7 \\ 4 & 3 & 0 \\ \ \end{array} \right] \equiv \left[ \begin{array}{ccc} 11 & 22 & 25 \\ 12 & 17 & 24 \\ 4 & 8 & 2 \\ \ \end{array} \right] \mod{26}$ $$

Using the blocks $\left [\begin{array}{ccc|c} 11 \\ 12 \\ 4 \\ \ \end{array} \right], \left [\begin{array}{ccc|c} 22 \\ 17 \\ 8 \\ \ \end{array} \right]$ , and, $\left [\begin{array}{ccc|c} 25 \\ 24 \\ 2 \\ \ \end{array} \right]$ we obtain the ciphertext: $$

$LME$ , $WRI$ , and $ZYC$ .

The user can verify the enciphered text using the other three matrices.

$\textbf{Answer:}$ $(1), (2), (3),$ and $(4)$ . $$