The sequences produced by the cryptographic sequence generator known as the shrinking generator can be modelled as the output sequences of linear elementary cellular automata. These sequences are composed of interleaved m-sequences produced by linear structures based on feedback shifts. This profitable characteristic can be used in the cryptanalysis of this generator. In this work we propose an algorithm that takes advantage of the inherent linearity of these cellular automata and the interleaved m-sequences. Although irregularly decimated generators have been conceived and designed as non-linear sequence generators, in practice they can be easily analysed in terms of simple linear structures.
The first author was partially support by Sao Paulo State Research Council (FAPESP) grant 2015/07246-0 and CAPES. This research has been partially supported by Ministerio de Economa, Industria y Competitividad (MINECO), Agencia Estatal de Investigacion (AEI), and Fondo Europeo de Desarrollo Regional (FEDER, UE) under project COPCIS, reference TIN2017-84844-C2-1-R, and by Comunidad de Madrid (Spain) under project reference S2013/ICE-3095-CIBERDINE-CM, also co-funded by European Union FEDER funds.
