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

This allows us to express the five k_i′s in terms of k₁:

So the key is likely to be (k₁, k₁ + 17, k₁ + 4, k₁ + 21, k₁ + 10) for some Hence, we suspect that the keyword is some cyclic shift of AREVK. It now does not take long to determine that the keyword is JANET. The complete decryption is the following:

The almond tree was in tentative blossom. The days were longer, often ending with magnificent evenings of corrugated pink skies. The hunting season was over, with hounds and guns put away for six months. The vineyards were busy again as the well-organized farmers treated their vines and the more lackadaisical neighbors hurried to do the pruning they should have done in November.³

³P. Mayle, A Year in Provence, A. Knopf, Inc., 1989.

1.2.4 A Known Plaintext Attack on the Hill Cipher

The 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, x_j = (x_1,j, x_2,j, . . . , x_m,j) and y_j = (y_1,j, y_2,j, . . . , y_m,j) (1 ≤ j ≤ m), such that y_j = e_K(x_j), 1 ≤ j ≤ m. If we define two m × m matrices X = (x_i,j) and Y = (y_i,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.)

Let’s 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 e_K (5, 17) = (15, 16), e_K (8, 3) = (2, 5) and e_K (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

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 Cipher

Recall that the ciphertext is the sum modulo 2 of the plaintext and the keystream, i.e., y_i = x_i + z_i mod 2. The keystream is produced from z₁, . . . , z_m using the linear recurrence relation

where (and c₀ = 1).

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 x₁x₂ . . . x_n and the corresponding ciphertext string y₁y₂ . . . y_n. Then he can compute the keystream bits z_i = x_i + y_i mod 2, 1 ≤ i ≤ n. Let us also suppose that Oscar knows the value m. Then Oscar needs only to compute c₀, . . . , c_m-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). Let’s illustrate with an example.

Example 1.13

Suppose Oscar obtains the ciphertext string

101101011110010

corresponding to the plaintext string

011001111111000.

Then he can compute the keystream bits:

110100100001010.

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

Table of Contents