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

The message is written as a series of row vectors. For example, if the message is abc, we change this to the single row vector $(0\text{,}1\text{,}2)$. To encrypt, multiply the vector by the matrix (traditionally, the matrix appears on the right in the multiplication; multiplying on the left would yield a similar theory) and reduce mod 26:

Therefore, the ciphertext is AXW. (The fact that the first letter $a$ remained unchanged is a random occurrence; it is not a defect of the method.)

In order to decrypt, we need the determinant of $M$ to satisfy

This means that there is a matrix $N$ with integer entries such that $MN\equiv I(\text{mod}26)$, where $I$ is the $n\times n$ identity matrix.

In our example, $\text{det}(M)=-3$. The inverse of $M$ is

Since 17 is the inverse of $-3$ mod 26, we replace $-1/3$ by 17 and reduce mod 26 to obtain

The reader can check that $MN\equiv I(\text{mod}26)$.

For more on finding inverses of matrices mod $n$, see Section 3.8. See also Example 15 in the Computer Appendices.

The decryption is accomplished by multiplying by $N$, as follows:

In the general method with an $n\times n$ matrix, break the plaintext into blocks of $n$ characters and change each block to a vector of $n$ integers between 0 and 25 using $a=0\text{,}b=1\text{,}\dots \text{,}z=25$. For example, with the matrix $M$ as above, suppose our plaintext is

This becomes (we add an $x$ to fill the last space)

Now multiply each vector by $M$, reduce the answer mod 26, and change back to letters:

In our case, the ciphertext is

It is easy to see that changing one letter of plaintext will usually change $n$ letters of ciphertext. For example, if $block$ is changed to $clock$, the first three letters of ciphertext change from $RBZ$ to $SDC$. This makes frequency counts less effective, though they are not impossible when $n$ is small. The frequencies of two-letter combinations, called digrams, and three-letter combinations, trigrams, have been computed. Beyond that, the number of combinations becomes too large (though tabulating the results for certain common combinations would not be difficult). Also, the frequencies of combinations are so low that it is hard to get meaningful data without a very large amount of text.

Now that we have the ciphertext, how do we decrypt? Simply break the ciphertext into blocks of length $n$, change each to a vector, and multiply on the right by the inverse matrix $N$. In our example, we have

and similarly for the remainder of the ciphertext.

For another example, see Example 21 in the Computer Appendices.

The Hill cipher is difficult to decrypt using only the ciphertext, but it succumbs easily to a known plaintext attack. If we do not know $n$, we can try various values until we find the right one. So suppose $n$ is known. If we have $n$ of the blocks of plaintext of size $n$, then we can use the plaintext and the corresponding ciphertext to obtain a matrix equation for $M$ (or for $N$, which might be more useful). For example, suppose we know that $n=2$ and we have the plaintext

corresponding to the ciphertext

The first two blocks yield the matrix equation

Unfortunately, the matrix $\left(\begin{array}{cc}7& 14\\ 22& 0\end{array}\right)$ has determinant $-308$, which is not invertible mod 26 (though this matrix could be used to reduce greatly the number of choices for the encryption matrix). Therefore, we replace the last row of the equation, for example, by the fifth block to obtain

In this case, the matrix $\left(\begin{array}{cc}7& 14\\ 20& 19\end{array}\right)$ is invertible mod 26:

We obtain

Because the Hill cipher is vulnerable to this attack, it cannot be regarded as being very strong.

A chosen plaintext attack proceeds by the same strategy, but is a little faster. Again, if you do not know $n$, try various possibilities until one works. So suppose $n$ is known. Choose the first block of plaintext to be $baaa\cdots =1000\dots$, the second to be $abaa\cdots =0100\dots$, and continue through the $n\text{th}$ block being $\dots aaab=\dots 0001$. The blocks of ciphertext will be the rows of the matrix $M$.

For a chosen ciphertext attack, use the same strategy as for chosen plaintext, where the choices now represent ciphertext. The resulting plaintext will be the rows of the inverse matrix $N$.