Hill cipher

The Hill cipher belongs to classical cryptography , more precisely to the area of polyalphabetic substitution based on linear algebra . It was invented by Lester S. Hill in 1929. He was a professor at Hunter College in New York City and first published this method in his article "Cryptography in an Algebraic Alphabet". At that time, the cryptographer was the first monoalphabetic cryptographer who can practically (if hardly) operate on more than three symbols at the same time. The following paragraphs assume a basic knowledge of the matrices .

Encryption

Each letter is represented by a number modulo 26. (Usually the simple scheme A = 0, B = 1,…, Z = 25 is used, but this type of coding is not mandatory.) To encrypt a message, a block of n letters (as an n-component vector ) by an invertible n × n matrix - again modulo 26 - multiplied. To decrypt the message, each block is multiplied by the inverse of the matrix that was used for encryption. The matrix used for encryption is the encryption key and should be chosen at random 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 operations must then be carried out modulo the number of letters instead of modulo 26. If you now consider the message "ACT" and the key as a matrix (or in letters "GYBNQKURP"):

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}}$

Since A = 0, C = 2 and T = 19, the message consists of the vector:

${\displaystyle {\begin{pmatrix}0\\2\\19\end{pmatrix}}}$

With this the encrypted vector is calculated:

${\displaystyle {\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}}}$

This corresponds to the ciphertext of "POH". Assuming that our message is now "CAT":

${\displaystyle {\begin{pmatrix}2\\0\\19\end{pmatrix}}}$

This time the same encryption matrix is ​​used, but the calculation shows:

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}\equiv {\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}{\pmod {26}}}$

which corresponds to the ciphertext of "FIN". Every letter has changed. The Hill cipher now reaches Shannon's diffusion and an n -dimensional Hill cipher can diffuse over n symbols at once .

Decryption

To decrypt the ciphertext, we multiply the text by the inverse matrix of the encryption matrix (in letters this is “IFKVIVVMI”). (To compute an inverse matrix, see Matrix inversion .) This is the inverse matrix of the encryption matrix from the previous example:

${\displaystyle {\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}^{-1}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\pmod {26}}}$

If you apply the previously encrypted ciphertext "POH" to it, you get:

${\displaystyle {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}\equiv {\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}}$

This gives you the plain text "ACT", our starting word. The problem that exists in the selection of the encryption matrix has not yet been discussed. Not all have an inverse matrix (see invertible matrix ). A matrix can become an inverse if, and only if, the determinant is not zero and has no factors in common with the modular base, i.e. This means that the determinant and the modulo number must not have any common factors. If you now operate in modulo 26, as above, the determinant must not be equal to zero and must not be divisible by 2 or 13. If the determinant is zero or the factors with the modular base are equal, then the matrix cannot be used for the Hill cipher. Another matrix must be selected, otherwise the ciphertext can no longer be decoded. Fortunately, the matrices that match these conditions are relatively common. From the example above, let the encryption matrix be:

${\displaystyle {\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}\equiv 6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)\equiv 441\equiv 25{\pmod {26}}}$

With modulo 26 the determinant is 25. Since 25 has no factors in common with the modulo number 26, this matrix can be used for the Hill cipher. The risk that the determinant has factors in common with the modular base can be reduced by using a prime number as the modular base . Consequently, a useful variant of the Hill cipher is to add three symbols to the alphabet (e.g. question mark, space and period) in order to arrive at the prime number 29 as a modular basis.

It is also possible to choose an involutive matrix for the encryption matrix , so that there is no need to determine the inverse matrix . ${\displaystyle A}$ ${\displaystyle A^{-1}=A}$

safety

Key room

For an alphabet with letters ( are different prime numbers, i.e. in prime factorization) the key space for n × n matrices comprises ${\displaystyle m=\prod _{i}{p_{i}^{k_{i}}}}$ ${\displaystyle p_{i}}$ ${\displaystyle m}$

${\displaystyle \prod _{i}\left({p_{i}^{(k_{i}-1)n^{2}}\prod _{j=0}^{n-1}\left(p_{i}^{n}-p_{i}^{j}\right)}\right)}$ Key.

The key space is therefore key for the order at its greatest when it selects as prime power, that is . ${\displaystyle m}$ ${\displaystyle m=p^{k}}$

See also

• Playfair encryption

Web links

• " Hill Cipher " explains, encodes and decodes
• " Hill Cipher Web App " encodes and decodes the entered messages and shows the matrices used
• " Hill Cipher Explained " illustrates the linear algebra behind the Hill cipher
• " Hill's Cipher Calculator "

swell

1. ^ Lester S. Hill: Cryptography in an Algebraic Alphabet . In: The American Mathematical Monthly . tape 36 , no. 6 June 1929, p. 306 , doi : 10.2307 / 2298294 ( marksmath.com [PDF; accessed June 11, 2014]).
2. ↑ Ryan Doyle: Hill's Cipher: Linear Algebra in Cryptography (PDF file).
3. ↑ ^{a b} Jeffrey Overbey, William Traves and Jerzy Wojdyło: On The Keys Pace Of The Hill Cipher . Cryptologia (PDF file).