Keywords: pseudorandom generator, cellular automata, cryptography.

Pseudorandom sequence generators are widely used in communications and cryptography [6]. The simplest devices employed to implement such generators are the linear feedback shift registers (LFSR). These devices consist of n flip-flops, whose contents are updated simultaneously controlled by a master clock. The content of every cell is moved to the next cell, while the content of the leftmost cell is computed by means of a linear function applied on the contents of several cells.

The period length of the sequences generated by LFSR depends on the linear feedback applied, which can be described by means of a polynomial. The coefficients of this characteristic polynomial represent the flip-flop contributing to the linear feedback. The maximal length of these sequences is 2ⁿ-1 and it is obtained when the feedback polynomial is primitive. Furthermore, maximal length sequences (m-sequences) present an excellent statistical distribution satisfying the Golomb postulates [2]. The main disadvantage is that they are easily predictable, i.e., from 2ⁿ known consecutive bits the entire (2ⁿ-1) sequence can be reproduced.

Several proposals have been presented to improve the randomness of these sequences. In this sense, the unidimensional cellular automata (CA) is proposed by many auhors [1]. However, the randomness of CA sequences suffers from similar problems to that of LFSR.

In order to overcome this weakness, two techniques has been traditionally applied: (i) non-linear combination of these devices, and (ii) non-linear filtering on the output sequence produced by a single device. These two techniques have determined many configurations [6]. On the other hand, a different technique has been proposed by several authors: dynamical modifications (in execution time) of the CA/LFSR configuration [4,5]. This approach seems to be conceptually simpler, although it is equivalent to a configuration in which several maximal length generators are combined. This kind of generators are named programmable CA (or programmable LFSR). In the case of LFSR, the characteristic polynomial is modified producing longer and more robust sequences. Each configuration employed corresponds to a primitive polynomial. In the case of CA, the characteristic matrix is also modified to obtain similar results.

In any case, the properties of these sequences can be analyzed from the characteristic matrix of the CA or the LFSR. This matrix is computed taking into account the matrices of every individual configuration applied to the device.

On the other hand, Gong [3] proposed a model based on interleaved sequences to study most of the existing pseudorandom generators. This model allows us to obtain the period and the linear complexity of the sequences generated.

In this paper, the model propose by Gong is applied to several programmable CA. where a particular class of programmable CA is studied. This CA corresponds to the implementation of certain quadratic functions in the Galois field  [7]

As a consequence of this study, a procedure to obtain the configurations producing maximal sequence length with high linear complexity is established.

1

Chaudhuri, P.P., Chowdhury, D.R., Nandi, S., Chattopadhyay, S., "Additive Cellular Automata. Theory and Applications", IEEE Computer Society Press, 1997.

2

Golomb S.W., "Shift Register Sequences", Revised Edition, Aegean Park Press, Laguna Hills, California, 1982.

3

Gong, G., "Theory and applications of q-ary Interleaved Sequences", IEEE Trans. on Information Theory, Vol. 41 No. 2, 400-411, 1995.

4

Guía, D. de la , Peinado, A., "Pseudorandom number generation based on Nongroup Cellular Automata", Proc 33rd Annual 1999 IEEE International Carnahan Conference on Security Technology, Madrid, October 5-7, 370-376, 1999.

5

Mita, R., Palumbo, G., Pennisi, S. and Poli M., "Pseudorandom bit generator based on dynamic linear feedback topology", Electronic Letters, Vol. 38 No. 19, 1097-1098, 2002. doi:10.1049/el:20020750

6

Menezes A., Oorschot P. van and Vanstone S., "Handbook of Applied Cryptography", CRC Press, 1996

7

Montoya, F., Muñoz, J., Peinado, A., "Iterated Quadratic functions in ", International Journal of Applied Mathematics, 5, (1), 65-83, 2001

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)