Information Technology Reference
In-Depth Information
with carry shit register (FCSR) with a maximal period,
i.e.
S
is an
-sequence.
This class of pseudo-random generators was introduced by Klapper and Goresky
in [6]. FCSRs and LFSRs are very similar in terms of properties [7,8]. However,
FCSRs have a non-linear feedback which is a significant property to thwart al-
gebraic attacks [9] in cryptographic applications [10].
The design of sub-sequences generators has been investigated in the case of
LFSRs [11,12] and two solutions have been proposed. The first solution [13,14]
is based on the classical synthesis of shift registers,
i.e.
the Berlekamp-Massey
algorithm, to define each sub-sequence. The second solution [11] is based on
a multiple steps design of the LFSR. We have applied those two solutions to
FCSRs. The contributions of the paper are as follows:
•
We explore the decimation properties of
-sequences for the design of a sub-
sequences generator by using an FCSR synthesis algorithm.
•
We show how to implement a multiple steps FCSR in Fibonacci and Galois
configuration.
The next section presents the motivation of this work and recalls the different
representations of LFSRs and FCSRs. In Section 3, the existing results on LFSRs
are described and we show multiple steps implementations of the Galois and
the Fibonacci configuration. We describe in Section 4 our main results on the
synthesis of sub-sequences generators in the case of
-sequences. Then, we give
some conclusions in Section 5.
2 Motivation and Preliminaries
The decimation is the main tool to transform a 1-bit output generator into a
sub-sequences generator. This allows us to increase the throughput of a pseudo-
random sequence generator (PRSG). Let
S
=(
s
0
,s
1
,s
2
,
···
) be an infinite binary
sequence of period
T
,thus
s
j
∈{
0. For a given
integer
d
,a
d
-decimation
of
S
is the set of sub-sequences defined by:
0
,
1
}
and
s
j
+
T
=
s
j
for all
j
≥
S
d
=(
s
i
,s
i
+
d
,s
i
+2
d
,
···
,s
i
+
jd
,
···
)
where
i
∈
[0
,d
−
1] and
j
=0
,
1
,
2
,
···
. Hence, a sequence
S
is completely
described by the sub-sequences:
S
d
=(
s
0
,s
d
,
···
)
S
d
=
s
1
,s
1+
d
,
···
)
.
.
.
S
d−
2
d
=(
s
d−
2
,s
2
d−
2
,
···
)
S
d−
1
d
=(
s
d−
1
,s
2
d−
1
,
···
)
.
A single automaton is often used to generate the pseudo-random sequence
S
.
In this case, it is dicult to achieve parallelism. The decomposition into sub-
sequences overcomes this issue as shown by Lempel and Eastman in [11]. Each
