Hill cipher

Last updated October 18, 2024

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.

Encryption

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

To encrypt a message, each block of n letters (considered as an n-component vector) is multiplied by an invertible n×n matrix, against modulus 26. To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption.

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 GYB/NQK/URP 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}}={\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 (IFK/VIV/VMI 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}}

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}}={\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}

which gets us back to 'ACT', as expected.

One complication exists in picking the encrypting matrix:

Not all matrices have an inverse. The matrix will have an inverse if and only if its determinant is inversible modulo n, where n is 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}}=6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)=441\equiv 25{\pmod {26}}

So, modulo 26, the determinant is 25. Since $25=5^{2}$ and $26=2\times 13$ , 25 has no common factors with 26, and 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{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}},

and

{\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}$ exists such that $KK^{-1}=K^{-1}K=I_{2}$ . The inverse of K can be computed by using the formula ${\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 $(ad-bc)^{-1}$ . Hence in this case, we compute

K^{-1}\equiv 9^{-1}{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv 3{\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}},

and

{\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}}\to HELP

.

Security

The basic Hill cipher is vulnerable to a known-plaintext attack because it is completely linear. An opponent who intercepts $n^{2}$ 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. 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).

Key space size

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 $26^{n^{2}}$ matrices of dimension n × n. Thus $\log _{2}(26^{n^{2}})$ or about $4.7n^{2}$ 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,Z₂). 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,Z₁₃)) 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.64n^{2}-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. (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.^{[ citation needed ]}

Related Research Articles

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission. The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks. That system was declassified in 1997.

In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices $A$ and $B$ is denoted as $AB$ .

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In linear algebra, an invertible matrix is a square matrix which has an inverse. In other words, if some other matrix is multiplied by the invertible matrix, the result can be multiplied by an inverse to undo the operation. Invertible matrices are the same size as their inverse.

In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an $complex matrix is an matrix obtained by transposing and applying complex conjugation to each entry. There are several notations, such as or,, or .$

In mathematics, scalar multiplication is one of the basic operations defining a vector space in linear algebra. In common geometrical contexts, scalar multiplication of a real Euclidean vector by a positive real number multiplies the magnitude of the vector without changing its direction. Scalar multiplication is the multiplication of a vector by a scalar, and is to be distinguished from inner product of two vectors.

In number theory, given a positive integer n and an integer a coprime to n, the multiplicative order of a modulo n is the smallest positive integer k such that $.$

The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is an NTRU lattice-based alternative to RSA and elliptic curve cryptography (ECC) and is based on the shortest vector problem in a lattice.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In cryptography, mod n cryptanalysis is an attack applicable to block and stream ciphers. It is a form of partitioning cryptanalysis that exploits unevenness in how the cipher operates over equivalence classes modulo n. The method was first suggested in 1999 by John Kelsey, Bruce Schneier, and David Wagner and applied to RC5P and M6. These attacks used the properties of binary addition and bit rotation modulo a Fermat prime.

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys.

In mathematics, the Smith normal form is a normal form that can be defined for any matrix with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module. It is named after the Irish mathematician Henry John Stephen Smith.

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number $p$ , then this root can be lifted to a unique root modulo any higher power of $p$ . More generally, if a polynomial factors modulo $p$ into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of $p$ .

<span class="mw-page-title-main">Weighing matrix</span> Mathematical weight device

In mathematics, a weighing matrix of order $and weight is a matrix with entries from the set such that:$

In algebra, the zero-product property states that the product of two nonzero elements is nonzero. In other words,

A Frobenius matrix is a special kind of square matrix from numerical analysis. A matrix is a Frobenius matrix if it has the following three properties:

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ . In the standard notation of modular arithmetic this congruence is written as

<span class="mw-page-title-main">Matrix (mathematics)</span> Array of numbers

In mathematics, a matrix is a rectangular array or table of numbers, symbols, or expressions, with elements or entries arranged in rows and columns, which is used to represent a mathematical object or property of such an object.

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)

External links

"Hill Cipher Web App" implements the Hill cipher and shows the matrices involved
"Hill Cipher Explained" illustrates the linear algebra behind the Hill Cipher
"Hill's Cipher Calculator" outlines the Hill Cipher with a Web page

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.