DEFINITION 1.6  A Stream Cipher is a tuple , where the following conditions are satisfied:

1.   is a finite set of possible plaintexts

2.   is a finite set of possible ciphertexts

3.  , the keyspace, is a finite set of possible keys

4.   is a finite set called the keystream alphabet

5.   is the keystream generator. For i ≥ 1,

6.  For each , there is an encryption rule and a corresponding decryption rule and are functions such that d_z(e_z(x)) = x for every plaintext .

We can think of a block cipher as a special case of a stream cipher where the keystream is constant: z_i = K for all i ≥ 1.

Here are some special types of stream ciphers together with illustrative examples. A stream cipher is synchronous if the keystream is independent of the plaintext string, that is, if the keystream is generated as a function only of the key K. In this situation, we think of K as a “seed” that is expanded into a keystream z₁z₂ . . ..

A stream cipher is periodic with period d if Z_i+d = z_i for all integers i ≥ 1. The Vigenere Cipher with keyword length m can be thought of as a periodic stream cipher with period m. In this case, the key is K = (k₁, . . . , k_m). K itself provides the first m elements of the keystream: z_i = k_i, 1 ≤ i ≤ m. Then the keystream just repeats itself from that point on. Observe that in this stream cipher setting for the Vigenere Cipher, the encryption and decryption functions are identical to those used in the Shift Cipher: e_z(x) = x + z and d_z (y) = y - z.

Stream ciphers are often described in terms of binary alphabets, i.e., . In this situation, the encryption and decryption operation are just addition modulo 2:

and

If we think of “0” as representing the boolean value “false” and “1” as representing “true,” then addition modulo 2 corresponds to the exclusive-or operation. Hence, encryption (and decryption) can be implemented very efficiently in hardware.

Let’s look at another method of generating a (synchronous) keystream. Suppose we start with (k₁, . . . , k_m) and let z_i = k_i, 1 ≤ i ≤ m (as before), but we now generate the keystream using a linear recurrence relation of degree m:

where c₀, . . . , are predetermined constants.

REMARK  This recurrence is said to have degree m since each term depends on the previous m terms. It is linear because z_i+m is a linear function of previous terms. Note that we can take c₀ = 1 without loss of generality, for otherwise the recurrence will be of degree m - 1.

Here, the key K consists of the 2m values k₁, . . . , k_m, c₀, . . . , c_m-1. If

then the keystream consists entirely of 0’s. Of course, this should be avoided, as the ciphertext will then be identical to the plaintext. However, if the constants c₀, . . . , c_m-1 are chosen in a suitable way, then any other initialization vector (k₁, . . . , k_m) will give rise to a periodic keystream having period 2^m - 1. So a “short” key can give rise to a keystream having a very long period. This is certainly a desirable property: we will see in a later section how the Vigenere Cipher can be cryptanalyzed by exploiting the fact that the keystream has short period.

Here is an example to illustrate.

Example 1.7

Suppose m = 4 and the keystream is generated using the rule

(i ≥ 1). If the keystream is initialized with any vector other than (0, 0, 0, 0), then we obtain a keystream of period 15. For example, starting with (1, 0, 0, 0), the keystream is

Any other non-zero initialization vector will give rise to a cyclic permutation of the same keystream.

Another appealing aspect of this method of keystream generation is that the keystream can be produced efficiently in hardware using a linear feedback shift register, or LFSR. We would use a shift register with m stages. The vector (k₁, . . . , k_m) would be used to initialize the shift register. At each time unit, the following operations would be performed concurrently:

1.  k₁ would be tapped as the next keystream bit

2.  k₂, . . . , k_m would each be shifted one stage to the left

3.  the “new” value of k_m would be computed to be

(this is the “linear feedback”).

Figure 1.8  A Linear Feedback Shift Register

Figure 1.9  Autokey Cipher

Observe that the linear feedback is carried out by tapping certain stages of the register (as specified by the constants c_j having the value “1”) and computing a sum modulo 2 (which is an exclusive-or). This is illustrated in Figure 1.8, where we depict the LFSR that will generate the keystream of Example 1.7.

An example of a non-synchronous stream cipher that is known as the Autokey Cipher is given in Figure 1.9. It is apparently due to Vigenere.

The reason for the terminology “autokey” is that the plaintext is used as the key (aside from the initial “priming key” K). Here is an example to illustrate: