![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
This allows us to express the five ki′s in terms of k1: So the key is likely to be (k1, k1 + 17, k1 + 4, k1 + 21, k1 + 10) for some
1.2.4 A Known Plaintext Attack on the Hill CipherThe Hill Cipher is more difficult to break with a ciphertext-only attack, but it succumbs easily to a known plaintext attack. Let us first assume that the opponent has determined the value of m being used. Suppose he has at least m distinct pairs of m-tuples, xj = (x1,j, x2,j, . . . , xm,j) and yj = (y1,j, y2,j, . . . , ym,j) (1 ≤ j ≤ m), such that yj = eK(xj), 1 ≤ j ≤ m. If we define two m × m matrices X = (xi,j) and Y = (yi,j), then we have the matrix equation Y = XK, where the m × m matrix K is the unknown key. Provided that the matrix X is invertible, Oscar can compute K = X-1Y and thereby break the system. (If Y is not invertible, then it will be necessary to try other sets of m plaintext-ciphertext pairs.) Lets look at a simple example. Example 1.12 Suppose the plaintext friday is encrypted using a Hill Cipher with m = 2, to give the ciphertext PQCFKU. We have that eK (5, 17) = (15, 16), eK (8, 3) = (2, 5) and eK (0, 24) = (10, 20). From the first two plaintext-ciphertext pairs, we get the matrix equation Using Theorem 1.3, it is easy to compute so This can be verified by using the third plaintext-ciphertext pair. What would the opponent do if he does not know m? Assuming that m is not too big, he could simply try m = 2, 3, . . . , until the key is found. If a guessed value of m is incorrect, then an m × m matrix found by using the algorithm described above will not agree with further plaintext-ciphertext pairs. In this way, the value of m can be determined if it is not already known. 1.2.5 Cryptanalysis of the LFSR-based Stream CipherRecall that the ciphertext is the sum modulo 2 of the plaintext and the keystream, i.e., yi = xi + zi mod 2. The keystream is produced from z1, . . . , zm using the linear recurrence relation where Since all operations in this cryptosystem are linear, we might suspect that the cryptosystem is vulnerable to a known-plaintext attack, as is the case with the Hill Cipher. Suppose Oscar has a plaintext string x1x2 . . . xn and the corresponding ciphertext string y1y2 . . . yn. Then he can compute the keystream bits zi = xi + yi mod 2, 1 ≤ i ≤ n. Let us also suppose that Oscar knows the value m. Then Oscar needs only to compute c0, . . . , cm-1 in order to be able to reconstruct the entire keystream. In other words, he needs to be able to determine the values of m unknowns. Now, for any i ≥ 1, we have which is a linear equation in the m unknowns. If n ≥ 2m, then there are m linear equations in m unknowns, which can subsequently be solved. The system of m linear equations can be written in matrix form as follows: If the coefficient matrix has an inverse (modulo 2), we obtain the solution In fact, the matrix will have an inverse if m is the degree of the recurrence used to generate the keystream (see the exercises for a proof). Lets illustrate with an example. Example 1.13 Suppose Oscar obtains the ciphertext string
corresponding to the plaintext string
Then he can compute the keystream bits:
Suppose also that Oscar knows that the keystream was generated using a 5-stage LFSR. Then he would solve the following matrix equation, which is obtained from the first 10 keystream bits: It can be checked that This yields = (1, 0, 1, 1, 0). Thus the recurrence used to generate the keystream is
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |