Linear Solutions for Irregularly Decimated Generators of Cryptographic Sequences

A. Fúster-Sabater
International Journal of Nonlinear Sciences and Numerical Simulation, vol. 15, no. 6, pp. 377-385

In the present work, it is shown that the sequences obtained from a cryptographic sequence generator, the so-called shrinking generator, are just particular solutions of a type of linear difference equations. Moreover, all these sequences are simple linear combinations of m-sequences weighted by other sequences that correspond to the diagonals of the Sierpinski's triangle. These facts suggest a subtle link between irregular decimation and linearity that can be conveniently exploited in the analysis of cryptographic sequences. Previous ideas can be easily extended to other decimation-based cryptographic generators as well as to interleaved sequence generators.