Keywords: linear cellular automata, nonlinear sequence generator, concatenation, cryptography.

Stream ciphers have extensive applications in secure communications, e.g. wireless systems, due to practical advantages such as ease of implementation, high speed and good reliability. When designing a stream cipher, the main goal is to expand a short key into a long pseudorandom keystream in such a way that it should not be possible to reconstruct the short key from the keystream. In this work, we focus our attention on binary keystream generators based on linear feedback shift registers (LFSRs) whose output sequences are combined in a nonlinear way. Such generators produce keystreams with high linear complexity, long period and good statistical properties.

On the other hand, one-dimensional binary Cellular Automata (CA) with three site neighborhood and linear transition rules [1] have been found to satisfy randomness properties with application in testing of digital circuits, built-in self-test (BIST) schemes and self-checking. The current interest of these CA stems from the lack of correlation between the bit sequences generated by adjacent cells [2]. In this sense, linear CA are superior to the more common LFSRs [3] which have been traditionally used as pseudorandom keystream generators. Moreover in [5], it is proved that linear CA are isomorphic to conventional LFSRs. Thus, the latter structures can be simply substituted by the former ones in order to accomplish the same goal: the generation of keystreams with cryptographic application. Nevertheless, the main advantage of these CA is that multiple generators designed in terms of LFSRs as nonlinear structures preserve the linearity when they are expressed under the form of CA. Such is the case of the Clock-Controlled generators, Cascade-Clock-Controlled generators, Shrinking generator or the generators producing Kasami sequences, GMW sequences, No sequences, Klapper et al. sequences etc., see [4]. All these generators are made out of one or more than one LFSR and a feed-forward function.

All the sequences mentioned above are included in the class of interleaved sequences [4], that is pseudorandom sequences satisfying a common property: each sequence can be decomposed into a collection of shifts of an unique PN-sequence and zero sequences. The characteristic polynomial of such sequences is of the form where is a primitive polynomial and p a positive integer. Therefore the goal of this work is to model those nonlinear LFSR-based generators in terms of these linear multiplicative polynomial CA.

In this way, the construction of a linear model of keystream generator from the concatenation of a basic automaton is carried out by the following algorithm:

Input: The parameters of a nonlinear keystream generator (LFSR lengths, feedback polynomials and feed-forward function).

• Step 1: Determine the irreducible factor of the characteristic polynomial of each interleaved sequence.
• Step 2: Compute the pair of basic CA whose characteristic polynomial is the irreducible factor mentioned in step 1.
• Step 3: For each one of these basic CA, construct by successive concatenations the longer cellular automaton able to generate the original interleaved sequence.

Output: Two linear CA producing the corresponding keystream sequence.

In this way, any of the previous keystream generators can be easily linearized by means of two CA. The algorithm to convert a nonlinear LFSR-based generator into a linear CA-based model is very simple and can be applied to cryptographic generators in a range of practical interest. The linearity of these cellular models can be advantageously used in the analysis and/or cryptanalysis of such keystream generators.

1

K. Cattell, J.C. Muzio "Synthesis of One-Dimensional Linear Hybrid Cellular Automata", IEEE Trans. Computers-Aided Design, 15, 3, 325-335, 1996. doi:10.1109/43.489103

2

S. J. Cho, C. Un-Sook, H. Yoon-Hee, "Computing Phase Shifts of Maximum-Length 90/150 Cellular Automata Sequences", Proc. of ACRI 2004. Lecture Notes on Computer Science, Springer-Verlag, 3305, 31-39, 2004.

3

S.W. Golomb, "Shift Register-Sequences", Aegean Park Press, Laguna Hill, 1982.

4

G. Gong, "Theory and Applications of q-ary Interleaved Sequences", IEEE Trans. on Information Theory, 41, 2, 400-411, 1995. doi:10.1109/18.370141

5

X. Sun, E. Kontopidi, M. Serra, J.C. Muzio "The Concatenation and Partitioning of Linear Finite State Machines", Int. J. Electronics, 78, 809-839, 1995. doi:10.1080/00207219508926211

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)