Cryptography Reference
In-Depth Information
. /
B
Figure 10.13
An FSR.
content of the rightmost register cell is the output of the FSR (for this clock cycle).
This procedure is repeated for every clock cycle. Consequently, the FSR may be
used to generate a sequence of (pseudorandom) output values. Because the length
of the register and the alphabet in use are finite, the FSR represents an FSM and
can be illustrated with a State diagram. If the register has
n
cells and the alphabet
comprises
q
characters or symbols, then the FSR represents an FSM with
q
n
states at
most. This also means that the FSR has a maximal period of
q
n
(needless to say that
a large period is preferred from a security viewpoint). The mathematical or graph-
theoretical instrument of choice to investigate on FSRs is the
Good-deBruijn graph
.
This is not further addressed in this topic.
. /
E
Figure 10.14
An exemplary LFSR.
In practice, LFSRs are most widely deployed. An FSR is linear if it operates
in a field and the feedback function is linear over this field. Note that a function
f
:
X
→
Y
is
linear
if
f
(
x
1
+
x
2
)=
f
(
x
1
)+
f
(
x
2
) for all
x
1
,x
2
∈
X
and
Z
2
=
f
(
αx
)=
αf
(
x
) for all
x
F
2
,
then the feedback function is linear if and only if it represents the modulo 2 sum of
∈
X
and
α
∈
R
. If we consider an FSR in
