Information Technology Reference
In-Depth Information
Construct the coecient matrix
H
0
of the set
U
D
, and assume
D
m
≥
D
e
.The
rows of
H
0
consist of all vectors
m
[
f
j
], with 1
≤
j
≤
m
and 0
≤
deg(
m
)
≤
D
m
.
Since we have formed products of
f
j
with all monomials of degree 0
≤
deg(
f
i
), some of the rows in
H
0
will add together to [
f
j
]
f
i
.Wecandothe
same starting with
f
i
and construct some coecient vectors that add up to
[
f
i
]
f
j
.Since[
f
i
]
f
j
=[
f
j
]
f
i
we have identified a linear dependency among some
rows of
H
0
.
During the execution of XL, as long as
D
m
≥
≤
deg(
m
)
D
e
, we will always create linear
dependencies of the form
[
f
j
]
·
f
i
+[
f
i
]
·
f
j
=0
.
The relation
[
f
i
]+[
f
i
]=0
also occurs since we have that
x
i
+
x
i
= 0. These relations are trivial in that
they will always exist for the equation systems over
λ
.
f
i
·
3 Equation Systems from LFSR-Based Stream Ciphers
Equations coming from LFSR-based stream ciphers are examples of equations
that are very interesting with respect to an XL-type algorithm. Assume we are
given a set of equations
F
=
{
f
1
=0
,f
2
=0
,...,f
m
=0
}
coming from a reg-
ularly clocked filter generator. Let
g
(
x
)
∈
F
2
[
x
] denote a primitive generator of
F
2
n
such that the binary sequence
s
t
=
n−
1
i
=0
s
t−n
+
i
c
i
is a sequence with maxi-
mal period 2
n
1 (an m-sequence). Then let
f
(
x
1
,...,x
n
) denote a Boolean
filter function of degree
d
. Then the keystream-sequence
z
=
−
{
z
t
}
t
=0
,
1
,...
is
generated by
z
t
=
f
(
s
t
,s
t
+1
,...,s
t
+
n−
1
)
,
which can be represented by the equations
F
=
f
t
(
s
0
,...,s
n−
1
)+
z
t
=0
t
=0
,
1
,...
,
where
f
(
s
t
,...,s
t
+
n−
1
)=
f
t
(
s
0
,...,s
n−
1
), since
s
t
canbewrittenintermsof
the initial state bits
s
0
,s
1
,...,s
n−
1
.Let
W
d
=
i
=1
i
denote the number of
monomials of degree less or equal to
d
. Then the coecient vector [
f
]maybe
restricted to a length
W
binary vector. Notice that in the direct algebraic attack
we need
W
equations in order to solve the system using a naive linear algebra
attack. Following [RonHel], there exist a
W
W
linear matrix operator
T
,which
is invariant of the filtering function
f
(
x
1
,...,x
n
), but variant of the polynomial
g
(
x
). Using their notation, we may instead write the sequence
z
t
by
×
z
t
=
f
(
s
t
,s
t
+1
,...,s
t
+
n−
1
)
=
s
t
[
f
0
]
=
s
0
T
t
[
f
]
=
s
0
[
f
t
]
,
