Information Technology Reference
In-Depth Information
recent designs in stream ciphers [4], [14]. This keystream sequence is XORed
with the plaintext (in emission) in order to obtain the ciphertext or with the
ciphertext (in reception) in order to recover the plaintext.
Most keystream generators are based on maximal-length Linear Feedback
Shift Registers (LFSRs) [7] whose output sequences, the so-called m -sequences,
are combined in a non linear way (for instance, non linear filters or irregularly
decimated generators) in order to produce pseudorandom sequences of crypto-
graphic application [5], [11]. Inside the family of irregularly decimated genera-
tors, we can enumerate: a) the shrinking generator proposed by Coppersmith,
Krawczyk and Mansour [2] that includes two LFSRs, b) the self-shrinking gen-
erator designed by Meier and Staffelbach [10] involving only one LFSR and
c) the generalized self-shrinking generator proposed by Hu and Xiao [8] that
includes the self-shrinking generator. Irregularly decimated generators produce
good cryptographic sequences ([6], [11], [12]) characterized by long periods, good
correlation features, excellent run distribution, balancedness, simplicity of im-
plementation, etc. The underlying idea of this kind of generators is the irregular
decimation of an m -sequence according to the bits of another one. The decima-
tion result is the output sequence that will be used as keystream sequence in the
cryptographic procedure.
In this work, it is shown that the generalized self-shrinking sequences are par-
ticular solutions of a type of linear difference equations. At the same time, other
solution sequences not included in the previous family also exhibit good prop-
erties for their application in cryptography. In brief, computing the solutions
of linear difference equations provides one with new binary sequences whose
cryptographic parameters can be easily guaranteed. That is to say, linear dif-
ference equations can contribute very e ciently to the generation of keystream
sequences for stream cipher.
2
Cryptographic Generators Based on Decimations: The
Generalized Self-shrinking Generator
The more general and representative of the irregularly decimated generators is
the generalized self-shrinking generator [8]. It can be described as follows:
1. It makes use of two sequences: an m -sequence
{
a n }
and a shifted version of
.
2. It relates both sequences by means of a simple decimation rule to generate
the output sequence.
such a sequence denoted by
{
v n }
The result of the previous steps is a family of generalized self-shrinking sequences
that can be defined in a more formal way as follows [8]:
Definition 1. Let
{
a n }
be an m-sequence over GF (2) with period 2 L āˆ’
1 gen-
erated from a LFSR of primitive characteristic polynomial of degree L .Let G be
an L-dimensional binary vector defined as:
GF (2) L .
G =( g 0 ,g 1 ,g 2 ,...,g Lāˆ’ 1 )
āˆˆ
(1)
 
Search WWH ::




Custom Search