Abstract
In the present work, it is shown that the binary sequences obtained from a cryptographic generator, the so-called generalized self-shrinking generator, are just particular solutions of a type of linear difference equations. Cryptographic parameters e.g. period, linear complexity or balancedness of the previous sequences can be analyzed in terms of linear equation solutions. In brief, computing the solutions of linear difference equations is an easy method of generating new sequences with guaranteed cryptographic parameters.
Keywords: pseudorandom sequence, linear difference equation, sequence generator, stream cipher, cryptography.
Introduction
It is a well known fact that pseudorandom binary sequences are typically used in a wide variety of applications such as: spread spectrum communication systems, multiterminal system identification, global positioning systems, software testing, error-correcting codes or cryptography. This work deals specifically with this last application.
In order to keep the confidentiality of sensitive information, an encryption function currently called cipher converts the plaintext or original message into the so-called ciphertext. Symmetric key encryption functions are usually divided into two separated classes: stream ciphers and block-ciphers depending on whether the encryption function is applied either to each individual bit or to a block of bits of the plaintext, respectively. Stream ciphers are the fastest among the encryption procedures so they are implemented in many technological applications e.g. RC4 for encrypting Internet traffic [13] or the encryption function E0 in Bluetooth specifications [1]. Stream ciphers try to imitate the mythic one-time pad cipher or Vernam cipher [11] and are designed to generate a long sequence (the keystream sequence) of pseudorandom bits. See the most 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 cryptographic application [5], [11]. Inside the family of irregularly decimated generators, we can enumerate: a) the shrinking generator proposed by Coppersmith, Krawczyk and Mansour [2] that includes two LFSRs, b) the self-shrinking generator 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 implementation, 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 decimation 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 particular solutions of a type of linear difference equations. At the same time, other solution sequences not included in the previous family also exhibit good properties 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 difference equations can contribute very efficiently to the generation of keystream sequences for stream cipher.
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 {an} and a shifted version of such a sequence denoted by {vn}.
2. It relates both sequences by means of a simple decimation rule to generate the output sequence.
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 {an} be an m-sequence over GF(2) with period 2L — 1 generated from a LFSR of primitive characteristic polynomial of degree L. Let G be an L-dimensional binary vector defined as:
The n-th element of the sequence {vn} is defined as:
where the sub-indexes of the sequence {an} are reduced mod 2L — 1 and the symbol ® represents the XOR logic operation. For n > 0 the decimation rule is very simple:
1. If an = 1, then vn is output.
2. If an = 0, then vn is discarded and there is no output bit.
In this way, a balanced output sequence bo bi b2 … denoted by {bn} or {6(G)} is generated. Such a sequence is called the generalized self-shrinking sequence associated with G.
Let us see a simple example. For the 4-degree m-sequence {an} = {011110101 100100} whose characteristic polynomial is x4 + x3 + 1, we get 16 generalized self-shrinking sequences based on {an}:
Notice that the generated sequences are not 16 different sequences as some of them are shifted versions of the others.
Cryptographic Sequences as Solutions of Linear Difference Equations
In this section, structural properties of the previous sequences will be studied in terms of solutions of linear difference equations.
In this work, the following homogeneous linear difference equations with binary coefficients will be considered:
where
is the n-th term of a binary sequence {zn} that satisfies the previous equation. The symbol E denotes the shifting operator that operates on the terms zn of a solution sequence, i.e.
The coefficients Cj are binary coefficients
r is an integer and the symbol
represents the XOR logic operation. The r-degree characteristic polynomial of (3) is:
If P (x) is a primitive polynomial [9] and a is one of its roots, then
are the r different roots of such a polynomial. In this case, it can be proved [3] that the solution of (3) is a sequence of the form:
where A is an arbitrary element in GF(2)r. That is {zn} is an m-sequence [7] of characteristic polynomial P(x) and period 2r — 1 whose starting point is determined by the value of A.
Let us generalize the previous difference equations to a more complex type of linear difference equations whose roots have a multiplicity greater than 1. In fact, we are going to consider difference equations of the form:
p being an integer p > 1. The characteristic polynomial PM (x) of this type of equations is:
In this case, the roots of PM(x) are the same as those of the polynomial P(x), that is
but with multiplicity p. Now the solutions of (7) are [3]:
where
and the
are binomial coefficients modulo 2.
In brief, the n-th term of a solution sequence {zn} is the bit-wise XOR logic operation of the n-th term of p sequences
weighted by binomial coefficients.
Table 1. Binomial coefficients, primary sequences and periods Ti
|
Binomial coeff. |
Primary sequences |
Ti |
 |
 |
To = 1 |
 |
 |
Ti = 2 |
 |
 |
T2 = 4 |
 |
 |
T3 = 4 |
 |
 |
r4 = 8 |
 |
 |
Tb = 8 |
 |
 |
Te = 8 |
 |
 |
T7 = 8 |
 |
 |
In fact, when n takes successive values each binomial coefficient
defines a primary sequence with constant period Ti. In Table 1, the first binomial coefficients with their corresponding primary sequences and periods are depicted.
Now the main results concerning generalized self-shrinking sequences and linear difference equations are introduced.
Theorem 1. The family of generalized self-shrinking sequences B(a) based on the m-sequence {an} are particular solutions of the homogeneous linear difference equation:
whose characteristic polynomial is
Sketch of proof: According to [8], the periods of the generalized self-shrinking sequences B(a) are
It is a well known fact in binary sequences [9] that if the period T of a binary sequence is a power of 2, then its characteristic polynomial f (x) is a power of (x + 1). Thus,
where LC is its linear complexity (the shortest linear recursion satisfied by such a sequence). At the same time, the linear complexity of a periodic sequence is less than or equal to its period that is
Therefore, the characteristic polynomial f (x) of any generalized self-shrinking sequence divides the characteristic polynomial of (10). In addition, the generalized self-shrinking sequences satisfied (10) and consequently they are particular solutions of such an homogeneous linear difference equation. □
Now the characteristics of the sequences that satisfy the previous linear difference equation are analyzed in detail. According to (9), the solutions of the difference equation given in (10) are of the form:
where
are binary coefficients, a = 1 is the unique root with multiplicity p of the polynomial (x +1) of degree r =1 and the
are binomial coefficients mod 2. Remark that the sequence {zn} is just the bitwise XOR logic operation of primary sequences weighted by the corresponding coefficients Aj.
It must be noticed that not all the solutions {zn} of (10) are generalized self-shrinking sequences although all generalized self-shrinking sequences are solutions of (10). From (12), particular features of the solution sequences and consequently of the generalized self-shrinking sequences can be easily determined. All of them are related with the choice of the p-tuple (A0, Ai,A2,…, Ap-i) of binary coefficients.
Periods of the Solution Sequences
According to Table 1, the periods of the primary sequences are just powers of 2. Moreover, according to (12) {zn} is the bit-wise XOR of sequences with different periods all of them powers of 2. Thus, the period of {zn} is the maximum period of the primary sequences involved in (12), that is the T corresponding to the primary sequence with the greatest index i such that
Concerning the generalized self-shrinking sequences, we have:
— A generalized self-shrinking sequence:
with period T =1 corresponding to
in (12).
— A generalized self-shrinking sequence:
with period T = 2 corresponding to
in (12).
— Different generalized self-shrinking sequences with period
corresponding to any
Linear Complexity of the Solution Sequences
According to [9], the linear complexity of a sequence equals the number and multiplicity of the characteristic polynomial roots that appears in its linear recurrence relationship. Therefore coming back to (12) and analyzing the coefficients Aj, the linear complexity of {zn} can be computed. In fact, we have a unique root 1 with maximal multiplicity p. Thus, if i is the greatest index
for which
then the linear complexity LC of the sequence {zn} will be:
as it will be the multiplicity of the root 1.
Concerning the generalized self-shrinking sequences, the main result related to their linear complexity can be stated as follows:
Theorem 2. The linear complexity LC of the generalized self-shrinking sequences with period
satisfies:
Theorem 2. The linear complexity LC of the generalized self-shrinking sequences with period
satisfies:
Sketch of proof: The result follows from the fact that those generalized self-shrinking sequences involve primary sequences
with i in the range 
that is precisely the range of values of their corresponding linear complexity. □
Generation of Cryptographic Sequences in Terms of Primary Sequences
From the previous section, it can be deduced that the bit-wise addition of correct primary sequences (or equivalently a correct choice of the p-tuple (A0,Ai,A2, … ,Ap-i)) results in the generation of sequences with controllable period and linear complexity. Nevertheless, from a cryptographic point of view balancedness must be taken into account.
In this sense, it must be noticed that the complementation of the last bit of a generalized self-shrinking sequence with period 2L-i means that the resulting sequence includes the primary sequence
That is the identically null sequence except for the last element that is 1. This implies that the obtained sequence will have period
maximum linear complexity
and quasi-balancedness as the difference between the number of 1′s and 0′s will be just one. For a cryptographic range L = 128, this difference is negligible. In brief, the selection of coefficients Ai allows one to control period, linear complexity and balancedness of the solution sequences.
Conclusions
In this work, it is shown that generalized self-shrinking sequences are particular solutions of homogeneous linear difference equations with binary coefficients. At the same time, there are other many solution sequences not included in the previous class that can be used for cryptographic purposes. The choice of the p-tuple (A0, Ai, A2,…, Ap-i) of binary coefficients allows one:
1. To get all the solutions of the above linear difference equation (12), among them there are sequences with application in stream cipher.
2. To obtain sequences with controllable period, linear complexity and bal-ancedness.
It must be noticed that, although generalized self-shrinking sequences and self-shrinking sequences are generated from LFSRs by irregular decimation, in practice they are simple solutions of linear equations. Thus, the solutions of linear difference equations with binary coefficients appear as excellent binary sequences with cryptographic application. An efficient computation of such sequences seems to be a good tool for the generation of keystream sequences in stream ciphers.
