Code 57 : Hill Cipher

Hill Cipher

Background

The Hill cipher was developed in 1929 by Lester S. Hill (*1891; † 1961) and was published in the Journal American Mathematical Monthly (Issue 36).¹

Principle

The Hill cipher was the first cipher purely based on mathematics (linear algebra). First, each character is assigned to a number, usually from the range of 00-25 for the characters A-Z. 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:

The message is thus encoded by this vector:

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

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.

Security

The cipher is based on linear algebra. When parts of the plaintext are known, an attacker could try to find out the key by using a system of linear equations.

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:

Weblinks

http://en.wikipedia.org/wiki/Hill_cipher

References

¹ Kryptographiespielplatz
² Wikipedia, 2009-03-22