The Hill Cipher was invented by Lester S. Hill in 1929 and was the first polygraphic cipher in which it was practical to operate on more than three symbols at once.

In the Hill Cipher, you start with a string, for instance "OMNIA GALLIA IN TRES PARTES DIVISO EST". Each letter in the string can be mapped uniquely to a numerical value from 0 tok, providing thatkis prime, and that you have enough characters such that there is always a 1-1 correspondence. A common arrangement is A=0, B=1, C=2, etc., but it is possible to permute this mapping to anything one wishes.

For the sake of simplicity, we will usek=29 (the smallest possible prime using the standard English alphabet), and the arrangement that A=0, B=1...Z=26, along with the extra characters 27 = "space" 28 = ? and 29 = !. We now convert the letters into their numeric values. This is represented as a vector, which we will call 'P' for Plaintext

P = [14, 12, 13, 8, 0, 26, 6, 0, 11, 11, 8, 0, 26, 8, 13, 26, 19, 17, 4, 18, 26, 15, 0, 17, 19, 4, 18, 26, 3, 8, 21, 8, 18, 14, 26, 4, 18, 19]

The next step is to choose a n-by-n matrix of positive, non-zero integers. In theory, any number could be used, but in practice values from 1-k are used. The number 0 tends to be avoided because multiplying by 0 often results in losing information.

For this, we will choose the matrix:

E = [28 7 16

3 13 5

2 9 19]

Since P can’t be multiplied by C directly, P should be split up intoiblocks, P_{1}to P_{i}, such that block contains n elements, arranged in a column. So, P_{1}= [14, 12, 13]^{T}, P_{2}= [8, 0, 26]^{T}, etc. until all the numbers are exhausted. If the last two set, P_{i}, has less than n elements, they can be "filled" in using random numbers.

After this, the next step is to multiply eachPcolumn vector by E modulus n, to get the ciphertext for that block, C.

(E*P_{i}) mod n = C_{i}

It goes without saying that C_{i}is likewise a column matrix with n elements. You do this until all P column vectors have been encrypted into C, then you use your original mapping (A=0, B=1...Z=26) to get a ciphertext. If you do this, you should get:

RCGSOHZPSQVHFSZBH?DEQZOFHZKGPBEZVHH!XES,

Which is quite different from what we had originally. Note that the pair "LL" in GALLIA becomes 'SQ'. So that in the cipher text, there is not a one-to-one correspondence as there are in monoalphabetic ciphers.

The Drawback to this method is that, because it is computed by simple matrix multiplication, and the matrix does not change, it is completely linear. With modern computing technology, it is very easy to solve this given a sufficient plaintext/ciphertext pair (mathematically, it can be solved in as few as n^{2}(in this case 81) pairs (i.e. a message with 81 characters).

Nonetheless, it can still be used as a primary step in other encryption methods.