[Next] [Up] [Previous] [Index]
Main : Index : Rotor Machine Ciphers : Early Machine Ciphers : The Hill Cipher

The Hill Cipher

This cipher was once implemented in the form of a machine using gears and chains like those used with bicycles. That, and the fact that it is impractical for hand use, while it predates the computer age, has caused me to put it in this section, although the appropriateness of this choice is also doubtful.

Supposing you are given the following problem to solve:

2x + y = a
x - y = b

and you want to find out what x and y are in terms of a and b.

The steps you can take to find it are the following:

You can add or subtract a multiple of one equation from another.

You can multiply one of the equations by a number.

You can change the order of the equations.

That last step may seem trivial, but it is included for completeness.

You can make a chart to save you copying the letters x, y, a, and b every time you perform a step:

x  y   a  b
-------------
2  1 | 1  0
1 -1 | 0  1

and the rows of this chart can be treated like the equations were. In this case, one might proceed as follows:

x  y   a  b
-------------
2  1 | 1  0      2x +  y = a
1 -1 | 0  1       x -  y = b

3  0 | 1  1      3x      = a + b
1 -1 | 0  1       x -  y = b

3  0 | 1  1      3x      = a + b
-3  3 | 0 -3     -3x + 3y = -3b

3  0 | 1  1      3x      = a + b
0  3 | 1 -2           3y = a - 2b

Of course, the last step of multiplying each row by 1/3rd (or, equivalently, dividing each row by 3) is still to be taken. I've avoided it here, to omit dealing with fractions.

If one works with numbers in modular arithmetic, particularly if the modulus is not a prime number, the rules change slightly.

If you add or subtract a multiple of one of the equations from another, you can still use any multiple, since a multiple of zero is the same as doing nothing, and so since that does not destroy information, neither will using a number that is not relatively prime to the modulus.

When multiplying a single row by a number, however, you cannot use a number unless it is relatively prime to the modulus. The Hill Cipher deals with modulo-26 arithmetic, and so in addition to zero, 13 and all the even numbers are disallowed for this manipulation.

Enciphering in the Hill Cipher is the same as finding a and b given x and y, where x and y are numbers from 0 to 25 substituted for two letters of a digraph being enciphered, and deciphering is solving for x and y given a and b.

Note that not all systems of linear equations can be solved, and you must choose one that has an inverse. One way to do this is by performing the manipulations allowed for finding an inverse on a square with zeroes everywhere except along the diagonal, since this will always result in a square that can be brought to that form by these same manipulations.

Also, the square formed by the coefficients of this kind of equation is called a matrix. The act of finding a and b for x and y, using the original form of the equations which directly give a and b as functions of x and y, thought of as an operation using the square of numbers we began with in the x and y columns (called a matrix) is called multiplying the vector (x,y) by the matrix to get the vector (a,b). The square representing x, y, and z or a, b, and c on one side of a set of equations, with a 1 at the start of the first row, in the second place in the second row, and so on, with zeroes everywhere else, is called the identity matrix, since if a=x, b=y, c=z, then finding a, b, and c for x, y, and z gives you the same numbers.

The linearity in the Hill cipher is its weak point. So a scrambled alphabet for converting letters to numbers needs to be used, and it is important to remember that that scrambled alphabet is a very important part of the key.

[Next] [Up] [Previous] [Index]