Hill cipher

Hill cipher
Hill's cipher machine, from figure 4 of the patent

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.

Contents

Operation

Each letter is first encoded as a number. Often the simplest scheme is used: A = 0, B =1, ..., Z=25, but this is not an essential feature of the cipher. A block of n letters is then considered as a vector of n dimensions, and multiplied by an n × n matrix, modulo 26. (If one uses a larger number than 26 for the modular base, then a different number scheme can be used to encode the letters, and spaces or punctuation can also be used.) The whole matrix is considered the cipher key, and should be random provided that the matrix is invertible in \mathbb{Z}_{26}^n (to ensure decryption is possible). A Hill cipher is another way of working out the equation of a matrix.

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}

Since 'A' is 0, 'C' is 2 and 'T' is 19, the message is the vector:

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

Thus the enciphered vector is given by:

\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}

which corresponds to a ciphertext of 'POH'. Now, suppose that our message is instead 'CAT', or:

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

This time, the enciphered vector is given by:

\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 a ciphertext of 'FIN'. Every letter has changed. The Hill cipher has achieved Shannon's diffusion, and an n-dimensional Hill cipher can diffuse fully across n symbols at once.

Decryption

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). (There are standard methods to calculate the inverse matrix; see matrix inversion for details.) We find that in \mathbb{Z}_{26}^n the inverse matrix of the one in the previous example is:

\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}

Taking the previous example ciphertext of 'POH', we get:

\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}

which gets us back to 'ACT', just as we hoped.

We have not yet discussed one complication that exists in picking the encrypting matrix. Not all matrices have an inverse (see invertible matrix). The matrix will have an inverse if and only if its determinant is not zero, and does not have any common factors with the modular base. 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} \equiv 6(16\cdot15-10\cdot17)-24(13\cdot15-10\cdot20)+1(13\cdot17-16\cdot20) \equiv 441 \equiv 25 \pmod{26}

So, modulo 26, the determinant is 25. Since this has no common factors with 26, this matrix can be used for the Hill cipher.

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.

Example

Let

K= \begin{vmatrix} 3 & 3 \\ 2 & 5 \end{vmatrix}

and suppose the plaintext message is HELP. Then this plaintext is represented by two pairs

HELP \to \begin{vmatrix} H \\ E \end{vmatrix} , \begin{vmatrix} L \\ P \end{vmatrix} \to \begin{vmatrix} 7 \\ 4 \end{vmatrix} , \begin{vmatrix} 11 \\ 15 \end{vmatrix}

Then we compute

\begin{vmatrix} 3 & 3 \\ 2 & 5 \end{vmatrix} \begin{vmatrix} 7 \\ 4 \end{vmatrix} = \begin{vmatrix} 7 \\ 8 \end{vmatrix}, \begin{vmatrix} 3 & 3 \\ 2 & 5 \end{vmatrix} \begin{vmatrix} 11 \\ 15 \end{vmatrix} = \begin{vmatrix} 0 \\ 19 \end{vmatrix}

and continue encryption as follows:

\begin{vmatrix} 7 \\ 8 \end{vmatrix}, \begin{vmatrix} 0 \\ 19 \end{vmatrix} \to \begin{vmatrix} H \\ I \end{vmatrix}, \begin{vmatrix} A \\ T \end{vmatrix}

The matrix K is invertible, hence K − 1 exists such that KK − 1 = K − 1K = I2. To implement decrypting, we compute

K^{-1} = 9^{-1} \begin{vmatrix} 5 & 23 \\ 24 & 3 \end{vmatrix} = 3 \begin{vmatrix} 5 & 23 \\ 24 & 3 \end{vmatrix} = \begin{vmatrix} 15 & 17 \\ 20 & 9 \end{vmatrix}

HIAT \to \begin{vmatrix} H \\ I \end{vmatrix}, \begin{vmatrix} A \\ T \end{vmatrix} \to \begin{vmatrix} 7 \\ 8 \end{vmatrix}, \begin{vmatrix} 0 \\ 19 \end{vmatrix}

Then we compute

\begin{vmatrix} 15 & 17 \\ 20 & 9 \end{vmatrix}\begin{vmatrix} 7 \\ 8 \end{vmatrix} = \begin{vmatrix} 7 \\ 4 \end{vmatrix}, \begin{vmatrix} 15 & 17 \\ 20 & 9 \end{vmatrix}\begin{vmatrix} 0 \\ 19 \end{vmatrix} = \begin{vmatrix} 11 \\ 15 \end{vmatrix}

Therefore

\begin{vmatrix} 7 \\ 4 \end{vmatrix}, \begin{vmatrix} 11 \\ 15 \end{vmatrix} \to \begin{vmatrix} H \\ E \end{vmatrix}, \begin{vmatrix} L \\ P \end{vmatrix} \to HELP.

Security

Unfortunately, the basic Hill cipher is vulnerable to a known-plaintext attack because it is completely linear. An opponent who intercepts n2 plaintext/ciphertext character pairs can set up a linear system which can (usually) be easily solved; if it happens that this system is indeterminate, it is only necessary to add a few more plaintext/ciphertext pairs. Calculating this solution by standard linear algebra algorithms then takes very little time.

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. Some modern ciphers use indeed 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). Recently, some publications tried to make the Hill cipher secure.

Key size

The key size is the binary logarithm of the number of possible keys. There are 26^{n^2} matrices of dimension n × n. Thus \log_2(26^{n^2}) or about 4.7n2 is an upper bound on the key size of the Hill cipher using n × n matrices. This is only an upper bound because not every matrix is invertible and thus usable as a key. The number of invertible matrices can be computed via the Chinese Remainder Theorem. I.e., a matrix is invertible modulo 26 if and only if it is invertible both modulo 2 and modulo 13. The number of invertible n × n matrices modulo 2 is equal to the order of the general linear group GL(n,Z2). It is

2^{n^2}(1-1/2)(1-1/2^2)\cdots(1-1/2^n).

Equally, the number of invertible matrices modulo 13 (i.e. the order of GL(n,Z13)) is

13^{n^2}(1-1/13)(1-1/13^2)\cdots(1-1/13^n).

The number of invertible matrices modulo 26 is the product of those two numbers. Hence it is

26^{n^2}(1-1/2)(1-1/2^2)\cdots(1-1/2^n)(1-1/13)(1-1/13^2)\cdots(1-1/13^n).

Additionally it seems to be prudent to avoid too many zeroes in the key matrix, since they reduce diffusion. The net effect is that the effective keyspace of a basic Hill cipher is about 4.64n2 − 1.7. For a 5 × 5 Hill cipher, that is about 114 bits. Of course, key search is not the most efficient known attack.

Mechanical implementation

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 (U.S. Patent 1,845,947) 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. 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.

See also

Other practical "pencil-and-paper" polygraphic ciphers include:

References

  • Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, June-July 1929, pp.306–312. (PDF)
  • Lester S. Hill, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly Vol.38, 1931, pp.135–154.
  • Jeffrey Overbey, William Traves, and Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol.29, No.1, January 2005, pp59–72. (CiteSeerX) (PDF)
  • Shahrokh Saeednia, How to Make the Hill Cipher Secure, Cryptologia, Vol.24, No.4, October 2000, pp.353–360.
  • I.A. Ismail, Mohammed Amin, and Hossam Diab, How to repair the Hill cipher, Journal of Zhejiang University-Science A, Vol.7, No.12, pp.2022–2030, Dec. 2006.
  • Mohsen Toorani, and Abolfazl Falahati, A Secure Variant of the Hill Cipher, Proceedings of the 14th IEEE Symposium on Computers and Communications (ISCC'09), pp.313–316, July 2009. (CiteSeerX) (PDF)

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Hill (disambiguation) — Hill usually refers to a raised landform. Hill may also refer to: * Hill (surname), the surname of many people * Hill (constructor), a 1970s Formula One teamIn places:Canada *Hill Island, NunavutEngland*Hill, Gloucestershire *Hill, Warwickshire… …   Wikipedia

  • Substitution cipher — In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the units may be single letters (the most common), pairs of letters, triplets of letters,… …   Wikipedia

  • National Cipher Challenge — The National Cipher Challenge is an annual cryptographic competition organised by the University of Southampton School of Mathematics. Competitors attempt to break cryptograms published on the competition website. In the 2007/08 challenge, 1301… …   Wikipedia

  • Caesar cipher — The action of a Caesar cipher is to replace each plaintext letter with one fixed number of places down the alphabet. This example is with a shift of three, so that a B in the p …   Wikipedia

  • Classical cipher — A cipher is a means of concealing a message, where letters of the message are substituted or transposed for other letters, letter pairs, and sometimes for many letters. In cryptography, a classical cipher is a type of cipher that was used… …   Wikipedia

  • Transposition cipher — In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext… …   Wikipedia

  • Book cipher — A book cipher is a cipher in which the key is some aspect of a book or other piece of text; books being common and widely available in modern times, users of book ciphers take the position that the details of the key is sufficiently well hidden… …   Wikipedia

  • Playfair cipher — The Playfair cipher or Playfair square is a manual symmetric encryption technique and was the first literal digraph substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair who promoted the… …   Wikipedia

  • Lorenz cipher — Tunny redirects here. For the fish, see Tuna. The Lorenz SZ 40 and SZ 42 ( Schlüsselzusatz , meaning cipher attachment ) were German cipher machines used during World War II for teleprinter circuits. British codebreakers, who referred to… …   Wikipedia

  • Pigpen cipher — The pigpen cipher uses graphical symbols assigned according to a key similar to the above diagram.[1] The pigpen cipher (sometimes referred to as the masonic cipher, Freemason s cipher, Rosicrucian cipher, or Tic tac toe cipher) …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”