Tag Archives: matrices

Hill Cipher

Published / by Alex Barter / Leave a Comment

Encryption

To encrypt in Hill a key first needs to be chosen, this will be a square matrix which has an inverse in modular 26. For the matrix to have an inverse the determinant must be co-prime to 26.

Here are two example matrices…
M_{2}=\begin{bmatrix}2 & 3 \\5 & 3 \end{bmatrix}, M_{3}=\begin{bmatrix}25 & 2 & 11 \\19 & 5 & 12 \\21 & 22 & 6 \end{bmatrix}
det(M_{2})=-9 (-9 mod 26) is 17 (-9+26×1), 17 is co-prime to 26
det(M_{3})=-2131 (-2131 mod 26) is 1 (-2131+26×82), 1 is co-prime to 26
Hence both these matrices are valid keys for the Hill cipher
*Co-prime means that the greatest common factor between the two numbers is 1.

If a 2 by 2 matrix is chosen for the key, the plaintext must be padded usually with an ‘X’ so that it is a multiple of 2. So for an N by N matrix the plaintext must be padded so that it that it is a multiple of N. E.G
For N=2, “CAREFUL” would become “CAREFULX”
For N=2, “SPORTS” would stay as “SPORTS”
For N=3, “CAREFUL” would become “CAREFULXX”
Once the text is a valid length, you take letters in blocks of N and convert them to a column vector. Letter ‘A’ has the value 0, ‘B’ is 1, ‘C’ is 2 … ‘Z’ is 25 etc.

Example:
CA=\begin{bmatrix}2 \\0 \end{bmatrix} , RE=\begin{bmatrix}17 \\4 \end{bmatrix} , FU=\begin{bmatrix}5 \\20 \end{bmatrix} , LX=\begin{bmatrix}11 \\23 \end{bmatrix}
CAR=\begin{bmatrix}2 \\0 \\17 \end{bmatrix} , EFU=\begin{bmatrix}4 \\5 \\20 \end{bmatrix} , LXX=\begin{bmatrix}11 \\23 \\23 \end{bmatrix}

You do this for each block of N characters. Then multiply the key matrix by each column vector. You will get a new column vector which can be converted back to letters.

\begin{bmatrix}2&3 \\5&3 \end{bmatrix}\begin{bmatrix}2 \\0 \end{bmatrix}=\begin{bmatrix}2\times2+3\times0 \\5\times2+3\times0 \end{bmatrix}=\begin{bmatrix}4 \\10 \end{bmatrix}\bmod26
“CAREFUL” encodes to “EKUTSHNU” using the key matrix M2

\begin{bmatrix}25 & 2 & 11 \\19 & 5 & 12 \\21 & 22 & 6 \end{bmatrix}\begin{bmatrix}2 \\0 \\17 \end{bmatrix}=\begin{bmatrix}25\times2+2\times0+11\times17 \\19\times2+5\times0+12\times17 \\21\times2+22\times0+6\times17 \end{bmatrix}=\begin{bmatrix}3 \\8 \\14 \end{bmatrix}\bmod26
“CAREFULX” encodes to “DIOSDCCCR” using the key matrix M3