In classical cryptography, the Hill cipher is a polygraphic substitution cipher based on linear algebra. Invented by Lester S. Hill in 1929, it was the first polygraphic cipher in which it was practical (though barely) to operate on more than three symbols at once.
The following discussion assumes an elementary knowledge of matrices.
Each letter is represented by a number modulo 26. Though this is not an essential feature of the cipher, this simple scheme is often used:
Letter | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Number | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
The matrix used for encryption is the cipher key, and it should be chosen randomly from the set of invertible n × n matrices (modulo 26). The cipher can, of course, be adapted to an alphabet with any number of letters; all arithmetic just needs to be done modulo the number of letters instead of modulo 26.
Consider the message 'ACT', and the key below (or GYBNQKURP in letters):
\begin{pmatrix}6&24&1\ 13&16&10\ 20&17&15\end{pmatrix}
\begin{pmatrix}0\ 2\ 19\end{pmatrix}
\begin{pmatrix}6&24&1\ 13&16&10\ 20&17&15\end{pmatrix}\begin{pmatrix}0\ 2\ 19\end{pmatrix}=\begin{pmatrix}67\ 222\ 319\end{pmatrix}\equiv\begin{pmatrix}15\ 14\ 7\end{pmatrix}\pmod{26}
\begin{pmatrix}2\ 0\ 19\end{pmatrix}
\begin{pmatrix}6&24&1\ 13&16&10\ 20&17&15\end{pmatrix}\begin{pmatrix}2\ 0\ 19\end{pmatrix}=\begin{pmatrix}31\ 216\ 325\end{pmatrix}\equiv\begin{pmatrix}5\ 8\ 13\end{pmatrix}\pmod{26}
In order to decrypt, we turn the ciphertext back into a vector, then simply multiply by the inverse matrix of the key matrix (IFKVIVVMI in letters). We find that, modulo 26, the inverse of the matrix used in the previous example is:
\begin{pmatrix}6&24&1\ 13&16&10\ 20&17&15\end{pmatrix}-1\pmod{26}\equiv\begin{pmatrix}8&5&10\ 21&8&21\ 21&12&8\end{pmatrix}
\begin{pmatrix}8&5&10\ 21&8&21\ 21&12&8\end{pmatrix}\begin{pmatrix}15\ 14\ 7\end{pmatrix}=\begin{pmatrix}260\ 574\ 539\end{pmatrix}\equiv\begin{pmatrix}0\ 2\ 19\end{pmatrix}\pmod{26}
One complications exist in picking the encrypting matrix:
Thus, if we work modulo 26 as above, the determinant must be nonzero, and must not be divisible by 2 or 13. If the determinant is 0, or has common factors with the modular base, then the matrix cannot be used in the Hill cipher, and another matrix must be chosen (otherwise it will not be possible to decrypt). Fortunately, matrices which satisfy the conditions to be used in the Hill cipher are fairly common.
For our example key matrix:
\begin{vmatrix}6&24&1\ 13&16&10\ 20&17&15\end{vmatrix}=6(16 ⋅ 15-10 ⋅ 17)-24(13 ⋅ 15-10 ⋅ 20)+1(13 ⋅ 17-16 ⋅ 20)=441\equiv25\pmod{26}
25=52
26=2 x 13
The risk of the determinant having common factors with the modulus can be eliminated by making the modulus prime. Consequently, a useful variant of the Hill cipher adds 3 extra symbols (such as a space, a period and a question mark) to increase the modulus to 29.
Let
K=\begin{pmatrix}3&3\ 2&5\end{pmatrix}
be the key and suppose the plaintext message is 'HELP'. Then this plaintext is represented by two pairs
HELP\to\begin{pmatrix}H\ E\end{pmatrix},\begin{pmatrix}L\ P\end{pmatrix}\to\begin{pmatrix}7\ 4\end{pmatrix},\begin{pmatrix}11\ 15\end{pmatrix}
Then we compute
\begin{pmatrix}3&3\ 2&5\end{pmatrix}\begin{pmatrix}7\ 4\end{pmatrix}\equiv\begin{pmatrix}7\ 8\end{pmatrix}\pmod{26},
\begin{pmatrix}3&3\ 2&5\end{pmatrix}\begin{pmatrix}11\ 15\end{pmatrix}\equiv\begin{pmatrix}0\ 19\end{pmatrix}\pmod{26}
and continue encryption as follows:
\begin{pmatrix}7\ 8\end{pmatrix},\begin{pmatrix}0\ 19\end{pmatrix}\to\begin{pmatrix}H\ I\end{pmatrix},\begin{pmatrix}A\ T\end{pmatrix}
The matrix K is invertible, hence
K-1
KK-1=K-1K=I2
\begin{pmatrix}a&b\ c&d\end{pmatrix}-1=(ad-bc)-1\begin{pmatrix}d&-b\ -c&a\end{pmatrix}
This formula still holds after a modular reduction if a modular multiplicative inverse is used to compute Hence in this case, we compute
K-1\equiv9-1\begin{pmatrix}5&23\ 24&3\end{pmatrix}\equiv3\begin{pmatrix}5&23\ 24&3\end{pmatrix}\equiv\begin{pmatrix}15&17\ 20&9\end{pmatrix}\pmod{26}
HIAT\to\begin{pmatrix}H\ I\end{pmatrix},\begin{pmatrix}A\ T\end{pmatrix}\to\begin{pmatrix}7\ 8\end{pmatrix},\begin{pmatrix}0\ 19\end{pmatrix}
Then we compute
\begin{pmatrix}15&17\ 20&9\end{pmatrix}\begin{pmatrix}7\ 8\end{pmatrix}=\begin{pmatrix}241\ 212\end{pmatrix}\equiv\begin{pmatrix}7\ 4\end{pmatrix}\pmod{26},
\begin{pmatrix}15&17\ 20&9\end{pmatrix}\begin{pmatrix}0\ 19\end{pmatrix}=\begin{pmatrix}323\ 171\end{pmatrix}\equiv\begin{pmatrix}11\ 15\end{pmatrix}\pmod{26}
Therefore,
\begin{pmatrix}7\ 4\end{pmatrix},\begin{pmatrix}11\ 15\end{pmatrix}\to\begin{pmatrix}H\ E\end{pmatrix},\begin{pmatrix}L\ P\end{pmatrix}\toHELP
The basic Hill cipher is vulnerable to a known-plaintext attack because it is completely linear. An opponent who intercepts
n2
While matrix multiplication alone does not result in a secure cipher it is still a useful step when combined with other non-linear operations, because matrix multiplication can provide diffusion. For example, an appropriately chosen matrix can guarantee that small differences before the matrix multiplication will result in large differences after the matrix multiplication. Indeed, some modern ciphers use a matrix multiplication step to provide diffusion. For example, the MixColumns step in AES is a matrix multiplication. The function g in Twofish is a combination of non-linear S-boxes with a carefully chosen matrix multiplication (MDS).
The key space is the set of all possible keys. The key space size is the number of possible keys. The effective key size, in number of bits, is the binary logarithm of the key space size.
There are
n2 | |
26 |
n2 | |
log | |
2(26 |
)
4.7n2
n2 | |
2 |
(1-1/2)(1-1/22) … (1-1/2n).
n2 | |
13 |
(1-1/13)(1-1/132) … (1-1/13n).
n2 | |
26 |
(1-1/2)(1-1/22) … (1-1/2n)(1-1/13)(1-1/132) … (1-1/13n).
4.64n2-1.7
When operating on 2 symbols at once, a Hill cipher offers no particular advantage over Playfair or the bifid cipher, and in fact is weaker than either, and slightly more laborious to operate by pencil-and-paper. As the dimension increases, the cipher rapidly becomes infeasible for a human to operate by hand.
A Hill cipher of dimension 6 was implemented mechanically. Hill and a partner were awarded a patent for this device, which performed a 6 × 6 matrix multiplication modulo 26 using a system of gears and chains.
Unfortunately the gearing arrangements (and thus the key) were fixed for any given machine, so triple encryption was recommended for security: a secret nonlinear step, followed by the wide diffusive step from the machine, followed by a third secret nonlinear step. (The much later Even–Mansour cipher also uses an unkeyed diffusive middle step). Such a combination was actually very powerful for 1929, and indicates that Hill apparently understood the concepts of a meet-in-the-middle attack as well as confusion and diffusion. Unfortunately, his machine did not sell.
Other practical "pencil-and-paper" polygraphic ciphers include: