Cryptography Reference
In-Depth Information
where 1
j
φ ( q
1) /n , M j is the generator matrix of the sequence and
2. Clearly, M j b 0 is the initial state of the LFSR.
0
k
q
2
T = T 0 ,
where T 0 is a subset of T . We denote these two functions by f 1 and f 2 .Then f 1
differs from f 2 only when x =0and f 1 = f 2 +( x 1 +1)( x 2 +1)
Let T =
F
−{
0
}
. Clearly, there are exactly two f
B n such that 1 f
( x n +1). Given
any LSFR, the keystream generated by using f 1 or f 2 as the filter function is the
same. Therefore, f 1 and f 2 can be viewed as the same function and we consider
the set
···
B n = B n /
{
0 , ( x 1 +1)( x 2 +1)
···
( x n +1)
}
.
B n can be represented by its support set in the form
Then any f
M i 1
j
b 0 ,M i 2
j
b 0 ,...,M i w
j
1 f
=
{
b 0 }
,
where M j
is the generator matrix of the register and 0
i 1 <i 2 < ... < i w
q
2.
4 Equivalence of Boolean Functions
Rønjom and Cid put forward nonlinear equivalence of Boolean functions in [17],
which can be defined as follows.
Definition 1. Let z be a keystream generated by a filter generator where the
LFSR has primitive feedback polynomial g 1 ( x ) and the filter function is f 1 . f 2
B n
f 2 ) if there exists an LFSR which filtered
by f 2 will generate the same keystream. Particularly, if the two LFSRs have
the same generator polynomial, we say that f 1 and f 2 are linear equivalent and
denote it by f 1 L f 2 .Otherwise, f 1 and f 2 are said to be nonlinear equivalent
which is denoted by f 1 N f 2 .
Example 1. Let the generator polynomial be m 1 ( x )= x 5 + x 2 + 1, the initial
statebe(1 , 0 , 0 , 0 , 0) T , and the filter function be f 1 ( x )= x 1 x 3 + x 1 x 4 + x 2 x 4 +
x 3 x 4 + x 4 x 5 + x 5 .Thenafullperiodofkeystreamis
is said to be equivalent to f 1 ( f 1
(0100111110111000101011010000110) .
Let the generator polynomial of another LFSR be m 2 ( x )= x 5 + x 4 + x 3 + x 2 +1,
theinitialstatebe(1 , 0 , 0 , 0 , 0) T , and the filter function be f 2 ( x )= x 3 + x 4 + x 5 .
Then the keystream generated will be the same as the above one. Therefore,
f 1 N f 2 . Clearly, deg( f 1 )=2,
AI
( f 1 )=2and nl ( f 1 ) = 12, while f 2 is a linear
function.
B n ,let
Theorem 1. Given an LFSR and the filter function f
|
1 f |
= w ,where
B n
w
1
w<q
1 . Then the number of g
such that g
L f is q
m ,where m
w
is a positive divisor of w and
( w,q− 1) |
m .
 
Search WWH ::




Custom Search