Linear Solutions for Irregularly Decimated Generators of Cryptographic Sequences

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.