Cryptography Reference
In-Depth Information
Fig. 2.6
Linear feedback shift register of degree 3 with initial values
s
2
,
s
1
,
s
0
Table 2.2
Sequence of states of the LFSR
clk
FF
2
FF
1
FF
0
=
s
i
0
1
0
0
1
0
1
0
2
1
0
1
3
1
1
0
4
1
1
1
5
0
1
1
6
0
0
1
7
1
0
0
8
0
1
0
starts to repeat after clock cycle 6. This means the LFSR output has period of length
7 and has the form:
0010111 0010111 0010111
...
There is a simple formula which determines the functioning of this LFSR. Let's
look at how the output bits
s
i
are computed, assuming the initial state bits
s
0
,
s
1
,
s
2
:
s
3
≡
s
1
+
s
0
mod 2
s
4
≡
s
2
+
s
1
mod 2
s
5
≡
s
3
+
s
2
mod 2
.
In general, the output bit is computed as:
s
i
+3
≡
s
i
+1
+
s
i
mod 2
where
i
= 0
,
1
,
2
,...
This was, of course, a simple example. However, we could already observe many
important properties. We will now look at general LFSRs.