Contemporary Mathematics
Volume XXX, 2008
Cellular Automata in Stream Ciphers
Amparo F´uster-Sabater
Abstract. A wide family of nonlinear sequence generators, the so-called clock-
controlled shrinking generators, has been analyzed and identified 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.
1. Introduction
Cellular Automata (CA) are particular forms of finite state machines that can
be investigated by the usual analytic techniques ([10], [17], [19], [25]). CA have
been used in application areas so different as physical system simulation, biologi-
cal process, species evolution, socio-economical models or test pattern generation.
They are defined as arrays of identical cells in an n-dimensional space and char-
acterized by different parameters [26]: the cellular geometry, the neighborhood
specification, 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) [11] 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
cryptography.
In recent years, one-dimensional CA have been proposed as an alternative to
LFSRs ([2], [3], [19], [26]) in the sense that every sequence generated by a LFSR can
1991 Mathematics Subject Classification. Primary 40B05, 40C05; Secondary 68R01.
Key words and phrases. Cellular automata, clock-controlled generators, sequence reconstruc-
tion, cryptography.
Work supported by Ministerio de Educaci´ on y Ciencia (Spain) Projects SEG2004-02418 and
SEG2004-04352-C04-03.
2008 American Mathematical Society
1
Contemporary Mathematics
Volume 477 , 2009
cc 2009 American Mathematical Society
1
http://dx.doi.org/10.1090/conm/477/09301
Previous Page Next Page