Reply To: !
@Crackerjack_404 describes using brute force search over the set of inverse matrices to break a hill cipher. This only works “quickly enough” for small matrices, perhaps up to 3×3.
Assuming we are working mod 26, there are something like 26 to the power of n squared inverse matrices to search. Of course, many of these are not invertible, but I know of no way to efficiently iterate the invertible matrices.
In python, this might look like this (you can do this more neatly with itertools but this example illustrates the point):
m = 26
for a in range(m):
for b in range(m):
for c in range(m):
for d in range(m):
try_matrix([a, b, c, d])
This will run in O(pow(26, pow(n, 2))) time, where the matrix has size n × n.
There’s actually a brute force attack that runs in O(pow(26, n)) time, a substantial speedup: take a look at the matrix multiplication for the decryption operation below. By the rules of matrix multiplication, U = AX + BY + CZ, so it’s possible to work out the first letter (or the second, etc.) in each block in terms of only one row of the inverse key.
Inverse Cipher Plain
matrix block block
╭ ╮ ╭ ╮ ╭ ╮
| A B C | | X | | U |
| D E F | | Y | = | V |
| G H I | | Z | | W |
╰ ╯ ╰ ╯ ╰ ╯
... therefore ...
╭ ╮
╭ ╮ | X | ╭ ╮
| A B C | | Y | = | U |
╰ ╯ | Z | ╰ ╯
╰ ╯
We can do a brute force search through the pow(26, n) possible inverse matrix rows, which will necessarily include all three rows of the actual inverse matrix.
When we decrypt with each of the possible rows, we get a potential slice of the plaintext (every nth letter). The slices can be evaluated using a scoring function that works on non-continuous samples of a plaintext, like the index of coincidence.
We can then take a selection of the best inverse matrix rows using a threshold (or just taking the top 2n rows) and try to fit them together to make a matrix that is invertible mod 26, and take the overall highest scoring invertible matrix. The runtime complexity of this step varies depending on the number of possible rows we obtained from the first step; practically this lets us solve for larger matrices much more efficiently.