Cryptography: Theory and Practice:Classical Cryptography | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

To decrypt, we can use the same keyword, but we would subtract it modulo 26 instead of adding.

Observe that the number of possible keywords of length m in a Vigenere Cipher is 26^m, so even for relatively small values of m, an exhaustive key search would require a long time. For example, if we take m = 5, then the keyspace has size exceeding 1.1 × 10⁷. This is already large enough to preclude exhaustive key search by hand (but not by computer).

In a Vigenere Cipher having keyword length m, an alphabetic character can be mapped to one of m possible alphabetic characters (assuming that the keyword contains m distinct characters). Such a cryptosystem is called polyalphabetic. In general, cryptanalysis is more difficult for polyalphabetic than for monoalphabetic cryptosystems.

1.1.5 The Hill Cipher

In this section, we describe another polyalphabetic cryptosystem called the Hill Cipher. This cipher was invented in 1929 by Lester S. Hill. Let m be a positive integer, and define . The idea is to take m linear combinations of the m alphabetic characters in one plaintext element, thus producing the m alphabetic characters in one ciphertext element.

For example, if m = 2, we could write a plaintext element as x = (x₂, x₂) and a ciphertext element as y = (y₁, y₂). Here, y₁ would be a linear combination of x₁ and x₂, as would y₂. We might take

Of course, this can be written more succinctly in matrix notation as follows:

In general, we will take an m × m matrix K as our key. If the entry in row i and column j of K is k_i,j, then we write K = (k_i,j). For x = (x₁, . . . , x_m) and , we compute y = e_K(x) = (y₁, . . . , y_m) as follows:

In other words, y = xK.

We say that the ciphertext is obtained from the plaintext by means of a linear transformation. We have to consider how decryption will work, that is, how x can be computed from y. Readers familiar with linear algebra will realize that we use the inverse matrix K^-1 to decrypt. The ciphertext is decrypted using the formula x = yK^-1.

Here are the definitions of necessary concepts from linear algabra. If A = (a_i,j) is an matrix and B = (b_j,k) is an m × n matrix, then we define the matrix product AB = (c_i,k) by the formula

for and 1 ≤ k ≤ n. That is, the entry in row i and column k of AB is formed by taking the ith row of A and the kth column of B, multiplying corresponding entries together, and summing. Note that AB is an matrix.

This definition of matrix multiplication is associative (that is, (AB)C = A(BC) but not, in general, commutative (it is not always the case that AB = BA, even for square matrices A and B).

The m × m identity matrix, denoted by I_m, is the m × m matrix with 1′s on the main diagonal and 0′s elsewhere. Thus, the 2 × 2 identity matrix is

I_m is termed an identity matrix since AI_m = A for any matrix A and I_mB = B for any m × n matrix B. Now, the inverse matrix to an m × m matrix A (if it exists) is the matrix A^-1 such that AA^-1 = A^-1 A = I_m. Not all matrices have inverses, but if an inverse exists, it is unique.

With these facts at hand, it is easy to derive the decryption formula given above: since y = xK, we can multiply both sides of the formula by K^-1, obtaining

(Note the use of the associativity property.)

We can verify that the encryption matrix above has an inverse in

since

Remember that all arithmetic operations are done modulo 26.)

Let’s now do an example to illustrate encryption and decryption in the Hill Cipher.

Example 1.5

Suppose the key is

From the computations above, we have that

Suppose we want to encrypt the plaintext july. We have two elements of plaintext to encrypt: (9, 20) (corresponding to ju) and (11, 24) (corresponding to ly). We compute as follows:

and

Hence, the encryption of july is DELW. To decrypt, Bob would compute:

and

Hence, the correct plaintext is obtained.

At this point, we have shown that decryption is possible if K has an inverse. In fact, for decryption to be possible, it is necessary that K has an inverse. (This follows fairly easily from elementary linear algebra, but we will not give a proof here.) So we are interested precisely in those matrices K that are invertible.

The invertibility of a (square) matrix depends on the value of its determinant. To avoid unnecessary generality, we will confine our attention to the 2 × 2 case.

DEFINITION 1.5 The determinant of the 2 × 2 matrix A = (a_i,j) is the value

REMARK The determinant of an m × m square matrix can be computed by elementary row operations: see any text on linear algebra.

Two important properties of determinants are that det I_m = 1; and the multiplication rule det(AB) = det A × det B.

Table of Contents