Hill

Polygraphic substitution, based on linear algebra


Options:

The Hill cipher was the first cipher purely based on mathematics (linear algebra).
To encipher a message, first the plaintext is broken into blocks of n letters which are converted to numbers, where A=0, B=1, C=2 ... Y=24, Z=25 (so each character is assigned to a number which is usually from the range of 00-25 for the characters A-Z. Upper case and lower case characters are treated equally).
Then the encryption is done by multiplying the numbers with an n x n key matrix modulo 26 (if we have A-Z as our alphabet). The result is converted back to text producing the ciphertext.

Let’s assume that we want to encode the message "ACT" with the key "GYBNQKURP".¹
Since G=6, Y= 24, B=1 etc. we get the following matrix for the chosen key:

hill1

The message is thus encoded by this vector:

hill2

Key and message are multiplied with each other and apply modulo 26 to the result:

hill3

This result (15, 14, 7) can be decoded by "POH" which would be the output of the Hill cipher for the chosen message and the used key. To decode the message, one would have to multiply the ciphertext with the inverse matrix of the key and apply modulo 26 to the result.


Details:

The key has to be chosen in such a way that there exists an inverse matrix for the key matrix because it would be impossible to decode the message otherwise. Therefore the determinant of the key matrix modulo 26 has to be co-prime to 26. Numbers co-prime to 26 are: 1,3,5,7,9,11,15,17,19,21,23,25. The determinant of the key matrix shown above is therefore calculated as such:

hill4

hill5

Some implementations like http://massey.limfinity.com/207/hillcipher.php only allow modulo values which are primes. This is better for security but no requirement of the original method. If a length like 26 is used, then this website complains e.g. "Hill cipher won't work unless the alphabet length is prime." This extra requirement can be achieved by adding e.g. an underscore as the first letter.
Implementations without this additional restriction and with the possibility to choose matrix dimensions n other than 2 or 3 are: CrypTool 1, CrypTool 2, and SageMath.



(1) This sample is taken from en.wikipedia.org/wiki/Hill_cipher, 2017-06-05

The Hill cipher was invented in 1929 by Lester S. Hill (*1891; † 1961)who described its method in the journal American Mathematical Monthly (Issue 36).¹

(1) en.wikipedia.org/wiki/Hill_cipher

The cipher is based on linear algebra only. When parts of the plaintext are known, an attacker could try to find out the key by using a system of linear equations.
So unfortunately, the basic Hill cipher is vulnerable to known-plaintext attacks. An opponent who intercepts n&sup2, plaintext/ciphertext character pairs can set up a linear system which can (usually) be easily solved.