Hubbry Logo
search
logo
Hill cipher avatar
Hill cipher
Hill cipher
current hub
2107129

Hill cipher

logo
Community Hub0 Subscribers
Read side by side
Hill cipher
View on Wikipedia
from Wikipedia
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.

Encryption

[edit]

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):

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

Thus the enciphered vector is given by:

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

This time, the enciphered vector is given by:

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

[edit]

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:

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

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

One complication exists in picking the encrypting matrix:

  1. 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:

So, modulo 26, the determinant is 25. Since and , 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 as 27 is 3 cubed and 28 is 2 times 14 or 4 times 7 .

Example

[edit]

Let

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

Then we compute

and

and continue encryption as follows:

The matrix K is invertible, hence exists such that . The inverse of K can be computed by using the formula

This formula still holds after a modular reduction if a modular multiplicative inverse is used to compute . Hence in this case, we compute

Then we compute

and

Therefore,

.

Security

[edit]

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

[edit]

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 matrices of dimension n × n. Thus or about 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

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

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

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 . For a 5 × 5 Hill cipher, that is about 114 bits. Of course, key search is not the most efficient known attack.

Mechanical implementation

[edit]

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]

See also

[edit]

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

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Hill cipher

View on Grokipedia
from Grokipedia
The Hill cipher is a polygraphic substitution cipher that uses linear algebra to encrypt blocks of plaintext letters, representing them as numerical vectors and applying matrix multiplication with a secret key matrix modulo the size of the alphabet (typically 26 for English). Invented by American mathematician Lester S. Hill in 1929, it was the first practical method to perform higher-order linear transformations on multiple letters simultaneously, offering a form of diffusion where each plaintext symbol affects multiple ciphertext symbols.[1] In operation, the plaintext is divided into blocks of length n (the dimension of the square key matrix), with each letter mapped to a number from 0 to 25; the n-dimensional vector is then multiplied by the n × n key matrix K to yield the ciphertext vector, computed modulo 26. Decryption reverses this process using the modular inverse matrix K-1, which exists if the determinant of K is coprime to 26, ensuring invertibility over the ring of integers modulo 26.[2] Hill's original formulation emphasized efficient computation for large n (up to 8–10), suggesting mechanical aids like telephone switchboards to handle the matrix operations without manual calculation.[1] While innovative for its era, the cipher's security relies on keeping the key matrix secret; it resists frequency analysis for block sizes n > 4 due to the mixing of plaintext dependencies, but remains susceptible to known-plaintext attacks, where an attacker with n pairs of plaintext and corresponding ciphertext can set up and solve a system of linear equations to recover K.[3] Despite these vulnerabilities, the Hill cipher has influenced modern block ciphers and serves as a foundational example of linear algebra in cryptography, often used in educational contexts to illustrate matrix applications.[4]

Introduction

History and Development

The Hill cipher was invented by American mathematician Lester S. Hill and first described in his 1929 paper "Cryptography in an Algebraic Alphabet," published in The American Mathematical Monthly. In this work, Hill introduced a polygraphic substitution method based on linear transformations, marking an early application of matrix algebra to cryptographic systems.[5] Lester Sanders Hill (1890–1961), who earned his B.A. from Columbia University in 1911 and his Ph.D. from Yale University in 1926, pursued a career in applied mathematics with a focus on communications and cryptography during the interwar period.[6] His motivation stemmed from a desire to leverage algebraic structures for secure message encoding, building on his broader research into mathematical models for error detection and transmission systems.[7] Hill later patented a mechanical device in 1932 (U.S. Patent No. 1,845,947) to implement a 6×6 version of his cipher using gears and wheels, aiming to make the computationally intensive process practical without electronic aids.[8] Despite these innovations, the Hill cipher saw limited practical adoption in the 1930s and during World War II, overshadowed by more operational mechanical systems like the Enigma machine, which better suited wartime needs for speed and simplicity.[9] Its reliance on manual matrix operations rendered it tedious and error-prone without computational support, confining it largely to theoretical exploration.[10]

Overview and Basic Principles

The Hill cipher, invented by Lester S. Hill in 1929, is a polygraphic substitution cipher that applies linear algebra to encrypt messages in blocks, treating the process as a transformation over a finite alphabet. As a symmetric-key algorithm, it uses the same key for both encryption and decryption, relying on modular arithmetic modulo 26 to map the 26 letters of the English alphabet to integers from 0 to 25. This modular framework ensures that all operations remain within the alphabet's bounds, forming a ring structure that supports the necessary algebraic manipulations.[11] At its core, the cipher divides the plaintext into fixed-size blocks of length n, where each block is represented as an n-dimensional vector over the integers modulo 26—for instance, n=2 corresponds to digraphs (pairs of letters). Encryption proceeds by multiplying each plaintext vector by an invertible n × n key matrix, also with entries modulo 26, to yield a corresponding ciphertext vector; the resulting components are then converted back to letters. This matrix multiplication embodies the cipher's polygraphic nature, substituting multiple letters simultaneously rather than individually, which enhances diffusion across the message.[11] The symmetry of the algorithm stems from the invertibility of the key matrix: decryption reverses the process by multiplying the ciphertext vectors by the modular inverse of the key matrix, recovering the original plaintext provided the matrix's determinant is coprime to 26. This reliance on matrix inverses highlights the cipher's foundation in linear transformations within the vector space (Z/26Z)n(\mathbb{Z}/26\mathbb{Z})^n, though the method assumes only basic familiarity with such structures without requiring advanced derivations. Larger block sizes n increase the key space and security potential, but the core principles remain consistent across implementations.[11]

Mathematical Foundations

Linear Algebra Prerequisites

In the context of cryptographic systems like the Hill cipher, linear algebra operations are performed over the ring of integers modulo mm, denoted Z/mZ\mathbb{Z}/m\mathbb{Z}, where mm is typically the size of the alphabet, such as 26 for the English alphabet. A vector is a column (or row) of nn elements from {0,1,…,m−1}\{0, 1, \dots, m-1\}, representing a point in (Z/mZ)n(\mathbb{Z}/m\mathbb{Z})^n. A matrix is an n×kn \times k array of such elements, with square matrices (n=kn = k) being particularly relevant for transformations. These structures generalize real linear algebra but restrict entries and operations to modular arithmetic to ensure finite, discrete computations.[12] Vector addition and scalar multiplication in Z/mZ\mathbb{Z}/m\mathbb{Z} are defined componentwise: for vectors u=(u1,…,un)\mathbf{u} = (u_1, \dots, u_n) and v=(v1,…,vn)\mathbf{v} = (v_1, \dots, v_n), the sum is u+v=(u1+v1mod  m,…,un+vnmod  m)\mathbf{u} + \mathbf{v} = (u_1 + v_1 \mod m, \dots, u_n + v_n \mod m); for a scalar c∈Z/mZc \in \mathbb{Z}/m\mathbb{Z}, the product is cu=(cu1mod  m,…,cunmod  m)c\mathbf{u} = (c u_1 \mod m, \dots, c u_n \mod m). These operations preserve the modular structure, ensuring results remain in {0,1,…,m−1}\{0, 1, \dots, m-1\}. For example, with m=26m=26, adding (5,22)(5, 22) and (18,3)(18, 3) yields (23,25)(23, 25), and multiplying by scalar 4 gives (20,18)(20, 18). Such operations form the basis for combining modular elements efficiently.[13][12] Matrix multiplication extends these via row-by-column dot products with modular reduction. For an r×nr \times n matrix AA and n×cn \times c matrix BB, the product C=ABC = AB has entry cij=∑k=1naikbkjmod  mc_{ij} = \sum_{k=1}^n a_{ik} b_{kj} \mod m. Each dot product ai⋅bj=∑k=1naikbkj\mathbf{a}_i \cdot \mathbf{b}_j = \sum_{k=1}^n a_{ik} b_{kj} is computed over integers before reducing modulo mm. Consider a simple 2×22 \times 2 example with m=26m=26:
A=(3142),B=(57810). A = \begin{pmatrix} 3 & 1 \\ 4 & 2 \end{pmatrix}, \quad B = \begin{pmatrix} 5 & 7 \\ 8 & 10 \end{pmatrix}.
The (1,1) entry is (3⋅5+1⋅8)mod  26=23mod  26=23(3 \cdot 5 + 1 \cdot 8) \mod 26 = 23 \mod 26 = 23; similarly, (1,2) is (3⋅7+1⋅10)mod  26=31mod  26=5(3 \cdot 7 + 1 \cdot 10) \mod 26 = 31 \mod 26 = 5, (2,1) is (4⋅5+2⋅8)mod  26=36mod  26=10(4 \cdot 5 + 2 \cdot 8) \mod 26 = 36 \mod 26 = 10, and (2,2) is (4⋅7+2⋅10)mod  26=48mod  26=22(4 \cdot 7 + 2 \cdot 10) \mod 26 = 48 \mod 26 = 22. Thus,
C=(2351022). C = \begin{pmatrix} 23 & 5 \\ 10 & 22 \end{pmatrix}.
This row-by-column process ensures associativity and distributivity hold modulo mm.[13][12] A square matrix A∈Mn(Z/mZ)A \in M_n(\mathbb{Z}/m\mathbb{Z}) is invertible if there exists BB such that AB=BA=InAB = BA = I_n, the identity matrix; this requires the determinant det⁡(A)\det(A) to be coprime to mm (i.e., gcd⁡(det⁡(A),m)=1\gcd(\det(A), m) = 1), ensuring det⁡(A)\det(A) has a modular inverse. Individual elements a∈Z/mZa \in \mathbb{Z}/m\mathbb{Z} have inverses if gcd⁡(a,m)=1\gcd(a, m) = 1, found via the extended Euclidean algorithm, as solutions to ax≡1mod  ma x \equiv 1 \mod m exist uniquely modulo mm under this condition. For m=26=2×13m = 26 = 2 \times 13, a prime power product, invertibility is complicated because Z/26Z\mathbb{Z}/26\mathbb{Z} is not a field—not every nonzero element (or determinant) is invertible, as units are only those coprime to 26 (e.g., 1, 3, 5, ..., 25 excluding multiples of 2 or 13). Thus, matrices with det⁡(A)\det(A) sharing factors with 26 (like 2 or 13) lack inverses, unlike in prime modulus cases where nonzero determinants suffice. Focus on coprime determinants ensures reliable reversibility in applications.[12][13]

Key and Message Representation

In the Hill cipher, plaintext messages are encoded using the standard English alphabet, where each letter is mapped to an integer from 0 to 25, with A corresponding to 0, B to 1, and so on up to Z at 25.[3][14] Spaces and punctuation are typically omitted from the plaintext or replaced with padding characters to ensure the message consists solely of letters, facilitating numerical conversion.[15] This mapping allows the cipher to operate within the finite field of integers modulo 26, aligning with the 26-letter alphabet.[3] The encoded plaintext is then divided into fixed-length blocks to form column vectors suitable for matrix multiplication. For a key matrix of size $ n \times n $, the message is segmented into vectors of length $ n $, such as pairs of letters for $ n=2 $ (e.g., "AB" becomes the vector $ \begin{pmatrix} 0 \ 1 \end{pmatrix} $).[14][15] If the message length is not a multiple of $ n $, it is padded with additional letters, often 'X' (encoded as 23), to complete the final block; this padding is later removed during decryption if recognizable.[3][15] The resulting ciphertext vectors are converted back to letters by mapping the modular integers to A-Z (e.g., 0 to A, 1 to B).[14] The key in the Hill cipher is an $ n \times n $ matrix $ K $ with integer entries between 0 and 25, selected randomly from the set of such matrices.[3] For the cipher to be reversible, $ K $ must be invertible modulo 26, which requires that the greatest common divisor of its determinant and 26 is 1 (i.e., $ \gcd(\det(K), 26) = 1 $).[3][14] This condition ensures the existence of a modular inverse matrix for decryption.[15] Matrices failing this invertibility criterion are invalid keys, as they would render decryption impossible. For instance, consider the 2×2 matrix $ K = \begin{pmatrix} 2 & 4 \ 1 & 2 \end{pmatrix} $; its determinant is $ \det(K) = (2 \cdot 2) - (4 \cdot 1) = 0 $, so $ \gcd(0, 26) = 26 \neq 1 $, making it singular and unsuitable.[3] To verify a key, compute $ \det(K) \mod 26 $ and check the gcd with 26.[14]

Encryption and Decryption

Encryption Algorithm

The encryption algorithm of the Hill cipher transforms blocks of plaintext into ciphertext through matrix multiplication over the integers modulo 26, treating the English alphabet as numerical vectors where A=0, B=1, ..., Z=25. The plaintext message is first divided into consecutive blocks of length nn, where nn is the dimension of the square key matrix KK, with each block represented as a column vector Pi\mathbf{P}_i.[16] If the message length is not a multiple of nn, it is padded with pre-arranged null letters, such as "X", to form complete blocks. For each plaintext block vector Pi=(pi,1,pi,2,…,pi,n)T\mathbf{P}_i = (p_{i,1}, p_{i,2}, \dots, p_{i,n})^T, the corresponding ciphertext block Ci\mathbf{C}_i is computed as Ci=[K](/page/K)Pimod  26\mathbf{C}_i = [K](/page/K) \mathbf{P}_i \mod 26. Component-wise, this is given by
ci,j=∑k=1nkj,k⋅pi,k(mod26) c_{i,j} = \sum_{k=1}^n k_{j,k} \cdot p_{i,k} \pmod{26}
for j=1,2,…,nj = 1, 2, \dots, n, where kj,kk_{j,k} are the entries of the key matrix KK. Each resulting ci,jc_{i,j} is then mapped back to a letter in the alphabet (e.g., 0=A, 1=B, ..., 25=Z) to form the ciphertext block.[3] The full ciphertext is obtained by concatenating the encrypted blocks in order.[16] The process can be outlined in the following steps:
  1. Convert the plaintext string to a sequence of numerical values modulo 26.
  2. Pad the sequence if necessary to ensure its length is a multiple of nn.
  3. Partition the numerical sequence into nn-dimensional column vectors P1,P2,…,Pm\mathbf{P}_1, \mathbf{P}_2, \dots, \mathbf{P}_m.
  4. For each i=1i = 1 to mm, compute Ci=KPimod  26\mathbf{C}_i = K \mathbf{P}_i \mod 26.
  5. Convert each Ci\mathbf{C}_i back to letters and concatenate to form the ciphertext string.[3]

Decryption Algorithm

The decryption process in the Hill cipher reverses the encryption by applying the modular inverse of the key matrix to the ciphertext blocks. For successful decryption, the key matrix $ K $ must be invertible modulo 26, which requires that the greatest common divisor of its determinant and 26 is 1 (i.e., gcd⁡(det⁡K,26)=1\gcd(\det K, 26) = 1).[3] If this condition is not met, the matrix has no inverse modulo 26, and a different key must be selected to ensure invertibility.[3] To decrypt, first compute the inverse matrix $ K^{-1} $ such that $ K \cdot K^{-1} \equiv I \pmod{26} $, where $ I $ is the identity matrix. One method to find $ K^{-1} $ is the adjugate formula:
K−1≡(det⁡K)−1⋅\adj(K)(mod26), K^{-1} \equiv (\det K)^{-1} \cdot \adj(K) \pmod{26},
where $ \adj(K) $ is the adjugate matrix (the transpose of the cofactor matrix), and $ (\det K)^{-1} $ is the modular multiplicative inverse of $ \det K $ modulo 26, which exists precisely when $ \gcd(\det K, 26) = 1 $.[17] Alternatively, Gaussian elimination (or row reduction) can be applied to the augmented matrix $ [K \mid I] $ modulo 26, using only elementary row operations with multipliers that are invertible modulo 26, to transform it into $ [I \mid K^{-1}] $.[18] Once $ K^{-1} $ is obtained, the plaintext blocks are recovered as follows. Divide the ciphertext into vectors $ C_i $ of length equal to the dimension of $ K $ (e.g., column vectors for an $ n \times n $ matrix), where each entry is the numerical representation of a letter (A=0, B=1, ..., Z=25). For each block $ i $, compute
Pi≡K−1⋅Ci(mod26), P_i \equiv K^{-1} \cdot C_i \pmod{26},
yielding the plaintext vector $ P_i $. Convert the resulting numerical values back to letters. For the full message, process all blocks sequentially and concatenate the plaintext letters; if padding was added during encryption to make the message length a multiple of $ n $, remove the extraneous characters at the end (typically 'X').[18][17]

Examples and Applications

Numerical Example

To illustrate the Hill cipher's matrix operations, consider a simple case with block size n=2n=2 over the modulus 26, using abstract numerical vectors rather than letter mappings. The key matrix is
K=(3257)(mod26). K = \begin{pmatrix} 3 & 2 \\ 5 & 7 \end{pmatrix} \pmod{26}.
The determinant of KK is det⁡(K)=(3⋅7)−(2⋅5)=21−10=11\det(K) = (3 \cdot 7) - (2 \cdot 5) = 21 - 10 = 11. Since gcd⁡(11,26)=1\gcd(11, 26) = 1, the determinant is coprime to 26, ensuring that KK is invertible modulo 26 and thus suitable as a key for encryption and decryption. Let the plaintext vector be P=(114)P = \begin{pmatrix} 1 \\ 14 \end{pmatrix}. Encryption computes the ciphertext vector C=K⋅P(mod26)C = K \cdot P \pmod{26}. Perform the matrix-vector multiplication step by step:
  • First component: 3⋅1+2⋅14=3+28=313 \cdot 1 + 2 \cdot 14 = 3 + 28 = 31, and 31mod  26=531 \mod 26 = 5.
  • Second component: 5⋅1+7⋅14=5+98=1035 \cdot 1 + 7 \cdot 14 = 5 + 98 = 103, and 103mod  26=25103 \mod 26 = 25 (since 103−3⋅26=103−78=25103 - 3 \cdot 26 = 103 - 78 = 25).
Thus, C=(525)C = \begin{pmatrix} 5 \\ 25 \end{pmatrix}. For decryption, first find the inverse key matrix K−1(mod26)K^{-1} \pmod{26}. The formula for the inverse of a 2×2 matrix is 1det⁡(K)⋅\adj(K)\frac{1}{\det(K)} \cdot \adj(K), where \adj(K)=(7−2−53)\adj(K) = \begin{pmatrix} 7 & -2 \\ -5 & 3 \end{pmatrix}. Modulo 26, this is \adj(K)≡(724213)(mod26)\adj(K) \equiv \begin{pmatrix} 7 & 24 \\ 21 & 3 \end{pmatrix} \pmod{26} (noting −2≡24-2 \equiv 24 and −5≡21-5 \equiv 21). The modular inverse of det⁡(K)=11\det(K) = 11 modulo 26 is 19, since 11⋅19=209≡1(mod26)11 \cdot 19 = 209 \equiv 1 \pmod{26} (as 209−8⋅26=209−208=1209 - 8 \cdot 26 = 209 - 208 = 1). Now multiply:
  • Top-left: 19⋅7=133≡3(mod26)19 \cdot 7 = 133 \equiv 3 \pmod{26} (since 133−5⋅26=133−130=3133 - 5 \cdot 26 = 133 - 130 = 3).
  • Top-right: 19⋅24=456≡14(mod26)19 \cdot 24 = 456 \equiv 14 \pmod{26} (since 456−17⋅26=456−442=14456 - 17 \cdot 26 = 456 - 442 = 14).
  • Bottom-left: 19⋅21=399≡9(mod26)19 \cdot 21 = 399 \equiv 9 \pmod{26} (since 399−15⋅26=399−390=9399 - 15 \cdot 26 = 399 - 390 = 9).
  • Bottom-right: 19⋅3=57≡5(mod26)19 \cdot 3 = 57 \equiv 5 \pmod{26} (since 57−2⋅26=57−52=557 - 2 \cdot 26 = 57 - 52 = 5).
So, K−1=(31495)(mod26)K^{-1} = \begin{pmatrix} 3 & 14 \\ 9 & 5 \end{pmatrix} \pmod{26}. Decrypt by computing P′=K−1⋅C(mod26)P' = K^{-1} \cdot C \pmod{26}:
  • First component: 3⋅5+14⋅25=15+350=365≡1(mod26)3 \cdot 5 + 14 \cdot 25 = 15 + 350 = 365 \equiv 1 \pmod{26} (since 365−14⋅26=365−364=1365 - 14 \cdot 26 = 365 - 364 = 1).
  • Second component: 9⋅5+5⋅25=45+125=170≡14(mod26)9 \cdot 5 + 5 \cdot 25 = 45 + 125 = 170 \equiv 14 \pmod{26} (since 170−6⋅26=170−156=14170 - 6 \cdot 26 = 170 - 156 = 14).
This recovers the original P=(114)P = \begin{pmatrix} 1 \\ 14 \end{pmatrix}, verifying the process.

Text-Based Example

To illustrate the application of the Hill cipher to textual messages, consider a block size of n=2n=2 and an encryption key matrix K=(3257)K = \begin{pmatrix} 3 & 2 \\ 5 & 7 \end{pmatrix}, where letters are mapped to numbers with A=0, B=1, ..., Z=25, and all operations are performed modulo 26. A simple example uses the plaintext "HI". Convert to numerical vectors: H=7, I=8, forming the column vector (78)\begin{pmatrix} 7 \\ 8 \end{pmatrix}. Encrypt by computing C=K(78)mod  26C = K \begin{pmatrix} 7 \\ 8 \end{pmatrix} \mod 26:
(3257)(78)=(3⋅7+2⋅85⋅7+7⋅8)=(21+1635+56)=(3791)mod  26=(1113). \begin{pmatrix} 3 & 2 \\ 5 & 7 \end{pmatrix} \begin{pmatrix} 7 \\ 8 \end{pmatrix} = \begin{pmatrix} 3 \cdot 7 + 2 \cdot 8 \\ 5 \cdot 7 + 7 \cdot 8 \end{pmatrix} = \begin{pmatrix} 21 + 16 \\ 35 + 56 \end{pmatrix} = \begin{pmatrix} 37 \\ 91 \end{pmatrix} \mod 26 = \begin{pmatrix} 11 \\ 13 \end{pmatrix}.
The resulting ciphertext numbers 11 and 13 correspond to L and N, yielding "LN". To decrypt, first find the inverse matrix K−1mod  26K^{-1} \mod 26. The determinant of KK is 3⋅7−2⋅5=113 \cdot 7 - 2 \cdot 5 = 11, and the modular inverse of 11 modulo 26 is 19 (since 11⋅19=209≡1mod  2611 \cdot 19 = 209 \equiv 1 \mod 26). The adjugate is (7−2−53)\begin{pmatrix} 7 & -2 \\ -5 & 3 \end{pmatrix}, so
K−1=19(724213)mod  26=(31495), K^{-1} = 19 \begin{pmatrix} 7 & 24 \\ 21 & 3 \end{pmatrix} \mod 26 = \begin{pmatrix} 3 & 14 \\ 9 & 5 \end{pmatrix},
where negative entries are adjusted modulo 26 (-2 ≡ 24, -5 ≡ 21). Now decrypt: P=K−1(1113)mod  26P = K^{-1} \begin{pmatrix} 11 \\ 13 \end{pmatrix} \mod 26:
(31495)(1113)=(3⋅11+14⋅139⋅11+5⋅13)=(33+18299+65)=(215164)mod  26=(78), \begin{pmatrix} 3 & 14 \\ 9 & 5 \end{pmatrix} \begin{pmatrix} 11 \\ 13 \end{pmatrix} = \begin{pmatrix} 3 \cdot 11 + 14 \cdot 13 \\ 9 \cdot 11 + 5 \cdot 13 \end{pmatrix} = \begin{pmatrix} 33 + 182 \\ 99 + 65 \end{pmatrix} = \begin{pmatrix} 215 \\ 164 \end{pmatrix} \mod 26 = \begin{pmatrix} 7 \\ 8 \end{pmatrix},
recovering H and I. For a longer message, consider the plaintext "PAYMOREMONEY" (length 12, a multiple of n=2n=2), with no padding required. Convert to numbers: P=15, A=0, Y=24, M=12, O=14, R=17, E=4, M=12, O=14, N=13, E=4, Y=24. Form blocks as column vectors and encrypt each:
  • PA: (15[0](/page/0))\begin{pmatrix} 15 \\ [0](/page/0) \end{pmatrix} → (3⋅15+2⋅[0](/page/0)5⋅15+7⋅[0](/page/0))mod  26=(4575)mod  26=(1923)\begin{pmatrix} 3 \cdot 15 + 2 \cdot [0](/page/0) \\ 5 \cdot 15 + 7 \cdot [0](/page/0) \end{pmatrix} \mod 26 = \begin{pmatrix} 45 \\ 75 \end{pmatrix} \mod 26 = \begin{pmatrix} 19 \\ 23 \end{pmatrix} (T=19, X=23) → "TX"
  • YM: (2412)\begin{pmatrix} 24 \\ 12 \end{pmatrix} → (3⋅24+2⋅125⋅24+7⋅12)mod  26=(96204)mod  26=(1822)\begin{pmatrix} 3 \cdot 24 + 2 \cdot 12 \\ 5 \cdot 24 + 7 \cdot 12 \end{pmatrix} \mod 26 = \begin{pmatrix} 96 \\ 204 \end{pmatrix} \mod 26 = \begin{pmatrix} 18 \\ 22 \end{pmatrix} (S=18, W=22) → "SW"
  • OR: (1417)\begin{pmatrix} 14 \\ 17 \end{pmatrix} → (3⋅14+2⋅175⋅14+7⋅17)mod  26=(76189)mod  26=(247)\begin{pmatrix} 3 \cdot 14 + 2 \cdot 17 \\ 5 \cdot 14 + 7 \cdot 17 \end{pmatrix} \mod 26 = \begin{pmatrix} 76 \\ 189 \end{pmatrix} \mod 26 = \begin{pmatrix} 24 \\ 7 \end{pmatrix} (Y=24, H=7) → "YH"
  • EM: ([4](/page/4)12)\begin{pmatrix} [4](/page/4) \\ 12 \end{pmatrix} → (3⋅[4](/page/4)+2⋅125⋅[4](/page/4)+7⋅12)mod  26=(36104)mod  26=(10[0](/page/0))\begin{pmatrix} 3 \cdot [4](/page/4) + 2 \cdot 12 \\ 5 \cdot [4](/page/4) + 7 \cdot 12 \end{pmatrix} \mod 26 = \begin{pmatrix} 36 \\ 104 \end{pmatrix} \mod 26 = \begin{pmatrix} 10 \\ [0](/page/0) \end{pmatrix} (K=10, A=0) → "KA"
  • ON: (1413)\begin{pmatrix} 14 \\ 13 \end{pmatrix} → (3⋅14+2⋅135⋅14+7⋅13)mod  26=(68161)mod  26=(16[5](/page/5))\begin{pmatrix} 3 \cdot 14 + 2 \cdot 13 \\ 5 \cdot 14 + 7 \cdot 13 \end{pmatrix} \mod 26 = \begin{pmatrix} 68 \\ 161 \end{pmatrix} \mod 26 = \begin{pmatrix} 16 \\ [5](/page/5) \end{pmatrix} (Q=16, F=5) → "QF"
  • EY: ([4](/page/4)24)\begin{pmatrix} [4](/page/4) \\ 24 \end{pmatrix} → (3⋅[4](/page/4)+2⋅245⋅[4](/page/4)+7⋅24)mod  26=(60188)mod  26=(86)\begin{pmatrix} 3 \cdot [4](/page/4) + 2 \cdot 24 \\ 5 \cdot [4](/page/4) + 7 \cdot 24 \end{pmatrix} \mod 26 = \begin{pmatrix} 60 \\ 188 \end{pmatrix} \mod 26 = \begin{pmatrix} 8 \\ 6 \end{pmatrix} (I=8, G=6) → "IG"
The full ciphertext is "TXSWYHKAQFIG". Decryption applies K−1K^{-1} to each ciphertext block, recovering the original plaintext blocks sequentially, as verified for the first block above. If the plaintext length is not a multiple of nn (e.g., adding an extra letter to make "PAYMOREMONEYX", length 13), pad the final block with a neutral letter like X (Z=25) to form complete digraphs, such as treating the last as YX for the 12th and 13th letters; during decryption, remove known padding based on message conventions. In practice, text-based implementation ignores non-letters (e.g., spaces, punctuation) by preprocessing to uppercase letters only, ensuring even block alignment through padding. Misalignment from odd lengths without padding can lead to incomplete blocks or errors in reconstruction, while non-alphabetic characters require separate handling to avoid disrupting the modular arithmetic.

Security Analysis

Key Space and Strength

The key space of the Hill cipher, for an n × n encryption matrix over the alphabet of 26 letters, consists of all invertible matrices in GL(n, ℤ/26ℤ). Although there are 26^{n^2} possible n × n matrices with entries in ℤ/26ℤ, only the invertible ones qualify as valid keys, as noninvertible matrices lack modular inverses required for decryption. The exact size of this key space is the order of the general linear group GL(n, ℤ/26ℤ).[19] By the Chinese Remainder Theorem, since 26 = 2 × 13 and ℤ/26ℤ ≅ ℤ/2ℤ × ℤ/13ℤ as rings, the order factors as |GL(n, ℤ/26ℤ)| = |GL(n, ℤ/2ℤ)| × |GL(n, ℤ/13ℤ)|, where each is the order of the general linear group over the respective finite field. For n = 2, this yields a key space of 157,248 valid matrices.[19] The cipher's theoretical strength, under the assumption of brute-force exhaustive search as the optimal attack and perfect uniformity and secrecy of the key, equates to the binary logarithm of the key space size, or approximately \log_2(157{,}248) \approx 17.3 bits for n = 2. This provides negligible protection against modern computational resources, as cryptographic standards mandate a minimum security strength of 112 bits for symmetric ciphers.[19][20] Increasing the block size n expands the key space exponentially with n^2, since |GL(n, ℤ/26ℤ)| \sim 26^{n^2} \prod_{p \mid 26} \prod_{k=1}^n (1 - 1/p^k), where the product over primes p = 2, 13 approaches 1 for large n, yielding super-exponential growth in security bits relative to n. This scaling underscores the role of n in balancing security and efficiency, though practical limits arise from matrix operations' O(n^3) complexity. Security further assumes keys are selected uniformly at random from the invertible matrices and remain undisclosed.[19]

Known Attacks and Vulnerabilities

The Hill cipher is highly susceptible to known-plaintext attacks, in which an attacker obtains n plaintext-ciphertext block pairs (where n is the dimension of the key matrix) and recovers the key by solving a system of linear equations modulo 26.[21] For consecutive blocks represented as column vectors $ \mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_n $ and corresponding ciphertexts $ \mathbf{c}_1, \mathbf{c}_2, \dots, \mathbf{c}_n $, the encryption relation $ \mathbf{c}_i = K \mathbf{p}_i \mod 26 $ for each i allows stacking into matrices P and C such that $ C = K P \mod 26 $.[22] Solving for the key then involves computing $ K = C P^{-1} \mod 26 $, assuming P is invertible over the ring of integers modulo 26; if not, an additional (n+1)th pair provides redundancy to resolve the system via Gaussian elimination or similar methods.[21] This attack exploits cribs—predictable plaintext segments like salutations or signatures—and requires only a small amount of matching text, making it practical even for larger n if such pairs are available.[23] Ciphertext-only attacks are also feasible, particularly for small n, due to the limited alphabet size modulo 26 and the ability to apply frequency analysis to encrypted blocks.[24] For instance, in a 2×2 Hill cipher, attackers can guess common digram mappings (e.g., assuming frequent ciphertext digrams correspond to English bigrams like "th" or "he") and test potential keys, leveraging the non-uniform distribution of letter frequencies to narrow candidates.[23] More advanced techniques divide the key matrix columns and use the Chinese Remainder Theorem to decompose the problem modulo 2 and 13, achieving complexity O(d × 13^d) for d×d matrices; this renders attacks viable for d ≤ 10 on standard hardware with sufficient ciphertext (roughly 12.5 d^2 symbols).[24] The vulnerabilities of the Hill cipher have been theoretically understood since its 1929 invention, stemming directly from its linear algebraic structure, though practical ciphertext-only methods remained limited until recent advances.[24] On modern computers, brute-force enumeration of all possible invertible keys is feasible in seconds for n=2 (key space ≈ 1.57 × 10^5), but for n=3 (key space ≈ 1.63 × 10^{12}), it requires substantial time (e.g., minutes to hours on standard hardware, depending on implementation and validation checks). To mitigate these weaknesses, increasing the matrix dimension n enlarges the search space against brute force, but introduces challenges like message padding to multiples of n, which can create exploitable patterns or predictability in block alignments.[24] Nonetheless, the cipher remains insecure against known-plaintext recovery via advanced linear algebra and is potentially vulnerable to quantum algorithms that accelerate matrix inversion or system solving over finite fields, though its classical scale limits the practical impact of such threats.[22] Fundamentally, the Hill cipher's insecurity arises from its perfect linearity, which permits superposition of equations and direct algebraic solution for the key without exhaustive trial, bypassing the full key space in targeted attacks.[21]

Implementations and Variants

Mechanical Implementations

In 1929, Lester S. Hill proposed a mechanical realization of his cipher in the paper "Cryptography in an Algebraic Alphabet," describing wiring diagrams that could implement matrix multiplication modulo 26 using gears or electrical switches to handle the linear transformations required for encryption. This approach aimed to automate the algebraic operations on blocks of letters represented as numerical vectors, facilitating polygraphic substitution without manual computation. Hill, in collaboration with Louis Weisner, secured U.S. Patent 1,845,947 in 1932 for a dedicated ciphering and deciphering device that mechanically executed a 6×6 Hill cipher.[25] The machine employed a system of interconnected gears and cams to perform the matrix-vector multiplication modulo 26, where input plaintext digits (corresponding to letters A-Z as 0-25) were fed into gear trains that computed weighted sums and applied modular reduction through notched wheels and counters. Key components included input dials for the plaintext block, a fixed gear matrix representing the key, and output indicators for the ciphertext, all driven by manual cranks to propagate the mechanical computations across the six dimensions. This design drew loose analogy to earlier mechanical ciphers like the Jefferson disk, but substituted rotational alignments for matrix-based linear operations, highlighting potential adaptations in rotor machines for achieving similar affine transformations.[25] Mechanical implementations of the Hill cipher faced significant limitations, particularly becoming bulky and cumbersome for matrices larger than 2×2, as the gear assemblies required increases in components to handle higher dimensions without errors. Modular arithmetic in purely mechanical systems proved error-prone, susceptible to wear in gears, which could introduce inaccuracies in the ciphertext output during prolonged use.

Modern Computational Variants

Software implementations of the Hill cipher leverage modern programming languages and libraries to perform matrix operations efficiently. In Python, the NumPy library is commonly used for key generation, encryption, and decryption by handling matrix multiplications modulo 26, converting plaintext to numerical vectors, and applying the invertible key matrix.[26] Similar approaches in Java utilize built-in linear algebra tools for the same modular arithmetic tasks, enabling rapid prototyping and simulation of the cipher's block-based encryption.[27] Variants extend the original Hill cipher to broader domains. The affine Hill cipher incorporates a translation vector alongside the linear transformation, generalizing the structure to $ \mathbf{c} = K \mathbf{p} + \mathbf{b} \pmod{m} $, where $ \mathbf{b} $ is the vector and $ m $ is the modulus, enhancing flexibility for substitution ciphers.[28] Generalizations to larger moduli, such as modulo 256, adapt the cipher for byte-oriented data, mapping ASCII characters (0-255) to support binary file encryption beyond alphabetic text.[29] The unimodular Hill cipher restricts keys to matrices with determinant 1, ensuring invertibility and simplifying computations while maintaining the core linear algebra foundation.[30] These computational adaptations find applications in education and resource-constrained environments. Interactive software tools, such as online encoders, serve as educational aids for demonstrating matrix-based cryptography concepts.[31] In embedded systems and IoT devices, lightweight modified Hill ciphers provide efficient encryption due to their low overhead, often integrated into hybrid schemes for data transmission security.[32] They also appear as components in hybrid ciphers, such as combinations with RSA, to balance computational cost and security in practical systems.[33] Modern hardware enables larger $ n $, yielding large key spaces of invertible matrices modulo 26 and feasible encryption times, though the cipher remains insecure for standalone use due to linear vulnerabilities. Open-source extensions, including integrations with libraries like PyCryptodome for AES-HILL hybrids, support advanced implementations.[34] For quantum resistance, lattice-based analogs replace linear modular arithmetic with non-linear lattice operations, embedding keys in harder-to-solve structures.[35]

References

  1. http://links.jstor.org/sici?sici=0002-9890%28192906%2F07%2936%3A6%3C306%3ACIAAA%3E2.0.CO%3B2-J
  2. [PDF] 10.7 Linear Algebra for Cryptography - MIT Mathematics
  3. [PDF] Hill Ciphers
  4. [PDF] Lecture 5 - CPSC 467: Cryptography and Security
  5. CRYPTOGRAPHY IN AN ALGEBRAIC ALPHABET by Lester S. Hill
  6. Lester Hill Revisited - ResearchGate
  7. Lester Hill Revisited: Cryptologia - Taylor & Francis Online
  8. US1845947A - Message protector - Google Patents
  9. Enigma History - Crypto Museum
  10. [PDF] The Evolution of Cryptography Through Number Theory
  11. Hill Cipher - Practical Cryptography
  12. None
  13. [PDF] modular arithmetic - keith conrad
  14. [PDF] 10.7 Linear Algebra for Cryptography - MIT Mathematics
  15. [PDF] Study of the Hill Cipher Encryption/Decryption Algorithm - DTIC
  16. Hill Cipher - Crypto Corner - Interactive Maths
  17. None
  18. [PDF] Cryptography in an Algebraic Alphabet Lester S. Hill The American ...
  19. [PDF] Hill Substitution Ciphers - Math
  20. [PDF] Hill Cipher - Williams College
  21. Cryptography in An Algebraic Alphabet - Taylor & Francis Online
  22. https://doi.org/10.1080/0161-110591893771
  23. [PDF] NIST Special Publication 800-131A
  24. None
  25. Known-plaintext attacks - Secgroup @ Ca' Foscari
  26. [PDF] Ciphertext-only attack on d × d Hill in O(d13d)
  27. [PDF] Hill Cipher
  28. https://www.math.utah.edu/~gustafso/s2019/2270/labs/lab5-hillcipher.pdf
  29. Cryptography - Hill Cipher - Tutorials Point
  30. Hill Cipher - GeeksforGeeks
  31. [PDF] Affine Ciphers - Koc Lab
  32. [PDF] Implementation of the Hill Cipher Algorithm with a Random ...
  33. (PDF) A Survey on the Unimodular Hill Cipher and Its Applications in ...
  34. Hill Cipher - Decoder, Encoder, Solver - Online Calculator - dCode
  35. [PDF] Enhancing Data Transmission Security through the Modified Hill ...
  36. Research on An Encryption Method Combining RSA and Hill Cipher
  37. [PDF] Modifying of Hill Cipher using Randomized Approach
  38. [PDF] Strengthening Image Security with Unimodular Hill Cipher and ...
  39. [PDF] Enhancing the Security of Hill Cypher Algorithm - IAEME Publication
User Avatar
No comments yet.