Aspects of Linearity in Cryptographic Sequence Generators

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 kind of linear difference equations. Moreover, all these sequences are simple linear combinations of m-sequences weighted by other primary sequences. This fact establishes a subtle link between irregular decimation and linearity that can be conveniently exploited in the cryptanalysis of such sequence generators. These ideas can be easily extended to other decimation-based cryptographic generators as well as to interleaved sequence generators.