Cryptanalysing the shrinking generator

S. D. Cardell, and A. Fúster-Sabater
Procedia Computer Science, Volume 51, Issue 1, pp. 2893-2897

In this work, we propose a cryptanalysis of the nonlinear sequence generator called the shrinking generator. The output sequence of this cryptographic generator, the shrunken sequence, can be modelled as one of the output sequences of linear cellular automata (CA). The shrunken sequence and the other sequences generated by the CA can be reduced to a combination of PN-sequences generated by the same characteristic polynomial. Therefore, all these PN-sequences are the same but shifted. We propose an efficient cryptanalysis that takes advantage of the linearity of these PN-sequences and the CA.

This work was partially supported by project S2013/ICE-3095-CIBERDINE-CM of Comunidad de Madrid. The work of the first author was also supported by a grant for postdoctoral students from the Generalitat Valenciana with reference APOSTD/2013/081