Cryptography Reference
In-Depth Information
where 1
(
f
) [24]. To resist fast algebraic attacks, the Boolean
functions used in stream ciphers should have high fast algebraic immunity and
it is known that
≤
deg
g<
AI
n
[10,24].
Two Boolean functions
f
and
g
are said to be ane equivalent if there exist
FAI
(
f
)
≤
A
2
such that
g
(
x
)=
f
(
Ax
+
b
). Clearly, algebraic degree,
algebraic immunity and nonlinearity are all invariant under ane transforma-
tion.
In what follows,
q
=2
n
and we denote an element of
∈
GL
n
(
F
2
)and
b
∈
F
2
by a column vector.
For simplicity, we consider a stream cipher being a filter generator that consists of
an LFSR of length
n
that generates an
m
-sequence and a filter function
f
F
∈
B
n
.
3 Representations of Sequences and Boolean Functions
Let the register generate an
m
-sequence of period
q
−
1, and the sequence
{
s
t
}
obey the recursion
n
m
j
s
t
+
j
=0
,m
j
∈
F
2
,
j
=0
where
m
0
=
m
n
=1.Thatis,
m
(
x
)=
m
0
+
m
1
x
+
...
+
m
n−
1
x
n−
1
+
x
n
is its
generator polynomial, and is primitive. The (transpose) companion matrix
M
(we call it the generator matrix of the sequence) is
⎛
⎝
⎞
⎠
01
···
00
00
··· ··· ··· ···
00
···
M
=
···
.
01
m
0
m
1
m
2
... m
n−
1
00
···
Let (
s
t
,s
t
+1
,...,s
t
+
n−
1
)
T
denote the state of the register at time
t
. Then the
next state is determined by (
s
t
+1
,s
t
+2
,...,s
t
+
n
)
T
=
M
(
s
t
,s
t
+1
,...,s
t
+
n−
1
)
T
=
M
t
+1
(
s
0
,s
1
,...,s
n−
1
)
T
. If the initial state of the register is
b
, then the sequence
can be represented by
S
=(
b, M b, ..., M
q−
2
b
). Here
b
can be any nonzero
n
-
dimensional column vector and hence there are exactly
q
−
1such
S
which
correspond to
q
−
1 different
m
-sequences. Let
b
0
=(1
,
0
,
···
,
0)
T
. Then these
sequences can be represented by
S
k
=(
M
k
b
0
,M
k
+1
b
0
, ..., M
k
+
q−
2
b
0
)
,
where 0
2.
Since the number of primitive polynomials of degree
n
is
φ
(
q
≤
k
≤
q
−
−
1)
/n
,thereare
φ
(
q
1)
/n
LFSRs generating
m
-sequences, and different LFSRs correspond to
different sequences. Therefore, there are exactly (
q
−
−
1)
φ
(
q
−
1)
/n m
-sequences,
and each sequence can be represented by
S
jk
=(
M
j
b
0
,M
k
+1
b
0
, ..., M
k
+
q−
2
b
0
)
,
j
j
Search WWH ::
Custom Search