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 , for example . The key is an matrix 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 . 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 remained unchanged is a random occurrence; it is not a defect of the method.)
In order to decrypt, we need the determinant of to satisfy
This means that there is a matrix with integer entries such that , where is the identity matrix.
In our example, . The inverse of is
Since 17 is the inverse of mod 26, we replace by 17 and reduce mod 26 to obtain
The reader can check that .
For more on finding inverses of matrices mod , see Section 3.8. See also Example 15 in the Computer Appendices.
The decryption is accomplished by multiplying by , as follows:
In the general method with an matrix, break the plaintext into blocks of characters and change each block to a vector of integers between 0 and 25 using . For example, with the matrix as above, suppose our plaintext is
This becomes (we add an to fill the last space)
Now multiply each vector by , 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 letters of ciphertext. For example, if is changed to , the first three letters of ciphertext change from to . This makes frequency counts less effective, though they are not impossible when 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 , change each to a vector, and multiply on the right by the inverse matrix . 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 , we can try various values until we find the right one. So suppose is known. If we have of the blocks of plaintext of size , then we can use the plaintext and the corresponding ciphertext to obtain a matrix equation for (or for , which might be more useful). For example, suppose we know that and we have the plaintext
corresponding to the ciphertext
The first two blocks yield the matrix equation
Unfortunately, the matrix has determinant , 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 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 , try various possibilities until one works. So suppose is known. Choose the first block of plaintext to be , the second to be , and continue through the block being . The blocks of ciphertext will be the rows of the matrix .
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 .