Hill cipher

Invented by Lester S. Hill in 1929, it was the first polygraphic cipher in which it was practical (though barely) to operate on more than three symbols at once.

Though this is not an essential feature of the cipher, this simple scheme is often used: To encrypt a message, each block of n letters (considered as an n-component vector) is multiplied by an invertible n × n matrix, against modulus 26.

To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption.

The matrix used for encryption is the cipher key, and it should be chosen randomly from the set of invertible n × n matrices (modulo 26).

Now, suppose that our message is instead 'CAT', or: This time, the enciphered vector is given by: which corresponds to a ciphertext of 'FIN'.

In order to decrypt, we turn the ciphertext back into a vector, then simply multiply by the inverse matrix of the key matrix (IFK/VIV/VMI in letters).

One complication exists in picking the encrypting matrix: Thus, if we work modulo 26 as above, the determinant must be nonzero, and must not be divisible by 2 or 13.

Fortunately, matrices which satisfy the conditions to be used in the Hill cipher are fairly common.

Consequently, a useful variant of the Hill cipher adds 3 extra symbols (such as a space, a period and a question mark) to increase the modulus to 29.

Then this plaintext is represented by two pairs Then we compute and continue encryption as follows: The matrix K is invertible, hence

Calculating this solution by standard linear algebra algorithms then takes very little time.

While matrix multiplication alone does not result in a secure cipher it is still a useful step when combined with other non-linear operations, because matrix multiplication can provide diffusion.

Indeed, some modern ciphers use a matrix multiplication step to provide diffusion.

The function g in Twofish is a combination of non-linear S-boxes with a carefully chosen matrix multiplication (MDS).

is an upper bound on the key size of the Hill cipher using n × n matrices.

This is only an upper bound because not every matrix is invertible and thus usable as a key.

The number of invertible matrices can be computed via the Chinese Remainder Theorem.

The number of invertible n × n matrices modulo 2 is equal to the order of the general linear group GL(n,Z2).

Hence it is Additionally it seems to be prudent to avoid too many zeroes in the key matrix, since they reduce diffusion.

When operating on 2 symbols at once, a Hill cipher offers no particular advantage over Playfair or the bifid cipher, and in fact is weaker than either, and slightly more laborious to operate by pencil-and-paper.

As the dimension increases, the cipher rapidly becomes infeasible for a human to operate by hand.

Hill and a partner were awarded a patent (U.S. patent 1,845,947) for this device, which performed a 6 × 6 matrix multiplication modulo 26 using a system of gears and chains.

Such a combination was actually very powerful for 1929, and indicates that Hill apparently understood the concepts of a meet-in-the-middle attack as well as confusion and diffusion.

[citation needed] Other practical "pencil-and-paper" polygraphic ciphers include: