Page 140 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 140
4.2 LFSR based stream ciphers and basic definitions
statistical properties. In relation to Figure 4.5, the update procedure performed in any
LFSR (at the time instance controlled by the system clock) may be summarized as fol-
lows:
1. The content of stage 0 is output and forms a part of the output sequence si , and at
the same time the new content of stage k − 1 is computed using a linear recursion
sk = k −1 s i c k −i .
i =0
2. The content of stage i is moved to stage i − 1, for each 1 ≤ i ≤ k − 1. The next state
of the LFSR is therefore S = (sk , . . . , s1) seen from left to right in Figure 4.5.
For a given length of the LFSR, the period and statistical properties of the sequence de-
pend entirely on the connection polynomial used. The use of a primitive connection
polynomial c (x ) ∈ 2[x ] results in the sequence of maximum length (the length is 2L − 1
for an LFSR of length L) with good statistical properties. Informally, a primitive polyno-
mial p (x ) = a 0 +a 1x +. . .+a k x k of degree k can be defined as an irreducible polynomial
over 2 with the property that {x i (mod p (x )) : i = 0, . . . , 2k − 2} = k \ {0}, using the rep-
2
resentation x i (mod p (x )) = r (x ) = r0 + r1x + . . . + rk −1x k −1 and identifying (r0, . . . , rk −1)
with the elements of k .
2
c1 c2 ck−1 ck
si
sk−1 sk−2 ... s1 s0
Figure 4.5: LFSR of length k with connection polynomial
Let s denote an infinite binary sequence whose terms are s0, s1, . . ., whereas its trun-
cated version of finite length n is denoted by s n , that is, s n = s0, s1, . . . , sn−1. The following
definitions, taken from [6], will be useful in the sequel.
Definition 4.2.1 An LFSR is said to generate a sequence s if there is some initial state of
LFSR for which the output sequence of the LFSR is s . Similarly, an LFSR generates s n if for
some initial state the first n terms of the output sequence of the LFSR coincide with s n .
Definition 4.2.2 The linear complexity of an infinite binary sequence s , denoted L(s ), is
the length of the shortest LFSR that generates s .
Example 4.2.3 For k = 4 (or L = 4) and the primitive connection polynomial C (x ) = x 4 +
x + 1 if we start the LFSR with S = (s0, s1, s2, s3) = (1, 1, 1, 0) it produces the sequence
1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1|1, 1, 1, 0 . . .
statistical properties. In relation to Figure 4.5, the update procedure performed in any
LFSR (at the time instance controlled by the system clock) may be summarized as fol-
lows:
1. The content of stage 0 is output and forms a part of the output sequence si , and at
the same time the new content of stage k − 1 is computed using a linear recursion
sk = k −1 s i c k −i .
i =0
2. The content of stage i is moved to stage i − 1, for each 1 ≤ i ≤ k − 1. The next state
of the LFSR is therefore S = (sk , . . . , s1) seen from left to right in Figure 4.5.
For a given length of the LFSR, the period and statistical properties of the sequence de-
pend entirely on the connection polynomial used. The use of a primitive connection
polynomial c (x ) ∈ 2[x ] results in the sequence of maximum length (the length is 2L − 1
for an LFSR of length L) with good statistical properties. Informally, a primitive polyno-
mial p (x ) = a 0 +a 1x +. . .+a k x k of degree k can be defined as an irreducible polynomial
over 2 with the property that {x i (mod p (x )) : i = 0, . . . , 2k − 2} = k \ {0}, using the rep-
2
resentation x i (mod p (x )) = r (x ) = r0 + r1x + . . . + rk −1x k −1 and identifying (r0, . . . , rk −1)
with the elements of k .
2
c1 c2 ck−1 ck
si
sk−1 sk−2 ... s1 s0
Figure 4.5: LFSR of length k with connection polynomial
Let s denote an infinite binary sequence whose terms are s0, s1, . . ., whereas its trun-
cated version of finite length n is denoted by s n , that is, s n = s0, s1, . . . , sn−1. The following
definitions, taken from [6], will be useful in the sequel.
Definition 4.2.1 An LFSR is said to generate a sequence s if there is some initial state of
LFSR for which the output sequence of the LFSR is s . Similarly, an LFSR generates s n if for
some initial state the first n terms of the output sequence of the LFSR coincide with s n .
Definition 4.2.2 The linear complexity of an infinite binary sequence s , denoted L(s ), is
the length of the shortest LFSR that generates s .
Example 4.2.3 For k = 4 (or L = 4) and the primitive connection polynomial C (x ) = x 4 +
x + 1 if we start the LFSR with S = (s0, s1, s2, s3) = (1, 1, 1, 0) it produces the sequence
1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1|1, 1, 1, 0 . . .
