Introduction to Cryptography with Coding Theory, 3rd Edition

6.2 Hill Ciphers

This section is not needed for understanding the rest of the chapter. It is included as an example of a block cipher.

In this section, we discuss the Hill cipher, which is a block cipher invented in 1929 by Lester Hill. It seems never to have been used much in practice. Its significance is that it was perhaps the first time that algebraic methods (linear algebra, modular arithmetic) were used in cryptography in an essential way. As we’ll see in later chapters, algebraic methods now occupy a central position in the subject.

Choose an integer $n$, for example $n=3$. The key is an $n\times n$ matrix $M$ whose entries are integers mod 26. For example, let

$$M=\left(\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 11& 9& 8\end{array}\right)\text{.}$$

The message is written as a series of row vectors. For example, if the message ...