Tag Archives: hill

Cryptanalysis of Hill Cipher

Published / by Alex Barter / 6 Comments on Cryptanalysis of Hill Cipher

If you need a reminder on how the Hill Cipher works click here.

The first thing to note is that when encoding in Hill Cipher each row of the key matrix encodes to 1 letter independently of the rest of the key matrix.

 \begin{bmatrix}21 & 18 & 12 \\9 & 0 & 23 \\8 & 3 & 2 \end{bmatrix}\begin{bmatrix}a \\b \\c \end{bmatrix}=\begin{bmatrix}21a+18b+12 c \\9 a+0b+23c \\8a+3b+2c \end{bmatrix}\bmod 26

Notice how the top row of the far left matrix is only involved in the top cell of the ciphertext matrix, the middle row is only involved in the middle cell etc.

We can use this fact to dramatically decrease the number of keys we have to test to break the Hill Cipher.

For square matrix of size N, there are 26N×N unique keys (there will be less as not all matrices have an inverse). For N=3, there is 269 ≈ 5.43×1012 keys, to test all of these is not feasible (I calculated on my pc it would take ≈ 8 years to test them all).

However, if we test each row individually then there is only 26N keys we need to test, For N=3 there is 263 = 17,576 which is a very small number in comparison (Takes 0.5 seconds on my pc!)

With this property of Hill Cipher we can go about cracking it.

First you will need to identify N (the size of the matrix) the size will be a multiple of the text length – this narrows it down a lot

Now you will be to iterate over all the row vectors with a size of N and possible values of 0 (inclusive) to 26 (exclusive).

For a 3 by 3 there are 17,576 combinations. They look will look something like this. On the left is the iteration number…

1/17576         [ 0,  0,  0]
2/17576         [ 0,  0,  1]
3/17576         [ 0,  0,  2] ……
16249/17576     [24,  0, 24]
16250/17576     [24,  0, 25]
16251/17576     [24,  1,  0] ……
17576/17576     [25, 25, 25]

For each one of these possibilities assume it is part of the key and multiply your ciphertext by it, you will multiply in blocks of N and get a single letter out for each block.

\begin{bmatrix}a & b & c \end{bmatrix} \begin{bmatrix}L_{1} \\L_{2} \\L_{3} \end{bmatrix}=\begin{bmatrix}a\times L_{1} + b\times L_{2} + c\times L_{3} \end{bmatrix}\bmod26

Once you have all the output letters for a particular possibility, score the letters using the Chi-Squared Statistic. Store the row vectors from smallest to largest Chi-Squared value.

Once you have checked all the possibilities. Take the best results from the list you have compiled and then go through all the permutations of creating an N by N matrix and checking it has an inverse in modular 26.

Example:

Let’s say you know N=3 and the best row vectors found using this method were with a Chi-Squared value of… (note is some cases the best N vectors may not be the correct ones so you may need to try a combination of a few different ones)

[22,  6,  7]    X2 = 71.721647
[23, 17, 18]    X2 = 50.562860
[25,  0,  6]    X2 = 81.987751

Rearranging each row to every possible position (For R number of rows there is R!, R×(R-1)×(R-2)…×1, permutations)

The next (3! = 6) matrices are all the permutations of each row vector.

\begin{bmatrix}22 & 6 & 7 \\23 & 17 & 18\\25 & 0 & 6  \end{bmatrix} \begin{bmatrix}22 & 6 & 7 \\25 & 0 & 6\\23 & 17 & 18  \end{bmatrix} \begin{bmatrix}23 & 17 & 18 \\22 & 6 & 7\\25 & 0 & 6\end{bmatrix}
\begin{bmatrix}25 & 0 & 6 \\22 & 6 & 7\\23 & 17 & 18 \end{bmatrix}\begin{bmatrix}25 & 0 & 6 \\23 & 17 & 18\\22 & 6 & 7 \end{bmatrix}\begin{bmatrix}{23} & 17 & 18 \\25 & 0 & 6\\22 & 6 & 7\end{bmatrix}

Then encrypt your ciphertext using these matrices (encrypting using the inverse key matrix is the same as decrypting using the key matrix). One of these results should be English – being your solution. If you wish to find the key matrix, you will need to inverse the inverse key matrix in mod 26.

To Conclude

For larger matrices like 4 by 4 and up the sheer number of keys make a brute force attack impossible, I don’t believe anyone has the patience or life expectancy to wait around 64 trillion years to solve one cipher. Other methods like crib dragging require you to guess or make assumptions for large chunks of the plaintext, a crib of 19+ characters very hard to come by. The method described above can solve a 4 by 4 Hill cipher in about 10 seconds, with no known cribs. The only thing it requires is that the text is of a certain length, about 100×(N-1) or greater when N is the size of the matrix being tested, so that statistical properties are not affected by a lack of data.

This same method can be adapted to decrypted ciphertext in other languages you just need to change the frequencies of letters that the Chi-Squared Statistic uses.

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