Volume XXX, 2008
Cellular Automata in Stream Ciphers
Abstract. A wide family of nonlinear sequence generators, the so-called clock-
controlled shrinking generators, has been analyzed and identiﬁed with a subset
of linear cellular automata. The algorithm that converts the given generator
into a linear model based on automata is very simple and can be applied in a
range of practical interest. Due to the linearity of these automata as well as
the characteristics of this class of generators, a cryptanalytic approach can be
proposed. Linear cellular structures easily model keystream generators with
application in stream cipher cryptography.
Cellular Automata (CA) are particular forms of ﬁnite state machines that can
be investigated by the usual analytic techniques (, , , ). CA have
been used in application areas so diﬀerent as physical system simulation, biologi-
cal process, species evolution, socio-economical models or test pattern generation.
They are deﬁned as arrays of identical cells in an n-dimensional space and char-
acterized by diﬀerent parameters : the cellular geometry, the neighborhood
speciﬁcation, the number of contents per cell and the transition rule to compute
the successor state. Their simple, modular and cascable structure makes them very
attractive for VLSI implementations.
On the other hand, Linear Feedback Shift Registers (LFSRs)  are linear
structures currently used in the generation of pseudorandom sequences. The in-
herent simplicity of LFSRs, their ease of implementation and the good statistical
properties of their output sequences turn them into natural building blocks for the
design of pseudorandom sequence generators with applications in spread-spectrum
communications, circuit testing, error-correcting codes, numerical simulations or
In recent years, one-dimensional CA have been proposed as an alternative to
LFSRs (, , , ) in the sense that every sequence generated by a LFSR can
1991 Mathematics Subject Classiﬁcation. Primary 40B05, 40C05; Secondary 68R01.
Key words and phrases. Cellular automata, clock-controlled generators, sequence reconstruc-
Work supported by Ministerio de Educaci´ on y Ciencia (Spain) Projects SEG2004-02418 and
2008 American Mathematical Society
Volume 477 , 2009
cc 2009 American Mathematical Society