![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
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 26m, 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 × 107. 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 CipherIn 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 For example, if m = 2, we could write a plaintext element as x = (x2, x2) and a ciphertext element as y = (y1, y2). Here, y1 would be a linear combination of x1 and x2, as would y2. 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 ki,j, then we write K = (ki,j). For x = (x1, . . . , xm) 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 = (ai,j) is an for 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 Im, is the m × m matrix with 1′s on the main diagonal and 0′s elsewhere. Thus, the 2 × 2 identity matrix is Im is termed an identity matrix since AIm = A for any 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.) Lets 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 = (ai,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 Im = 1; and the multiplication rule det(AB) = det A × det B.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |