Advanced Search
Article Contents
Article Contents

Modelling the shrinking generator in terms of linear CA

Abstract Related Papers Cited by
  • This work analyses the output sequence from a cryptographic non-linear generator, the so-called shrinking generator. This sequence, known as the shrunken sequence, can be built by interleaving a unique PN-sequence whose characteristic polynomial serves as basis for the shrunken sequence's characteristic polynomial. In addition, the shrunken sequence can be also generated from a linear model based on cellular automata. The cellular automata here proposed generate a family of sequences with the same properties, period and characteristic polynomial, as those of the shrunken sequence. Moreover, such sequences appear several times along the cellular automata shifted a fixed number. The use of discrete logarithms allows the computation of such a number. The linearity of these cellular automata can be advantageously employed to launch a cryptanalysis against the shrinking generator and recover its output sequence.
    Mathematics Subject Classification: Primary: 37B15, 11B85; Secondary: 12E05.


    \begin{equation} \\ \end{equation}
  • [1]

    S. D. Cardell and A. Fúster-Sabater, Cryptanalysing the shrinking generator, Proc. Comp. Sci., 51 (2015), 2893-2897.


    S. D. Cardell and A. Fúster-Sabater, Performance of the cryptanalysis over the shrinking generator, in Int. Joint Conf. CISIS'15 and ICEUTE'15 (eds. A.H. et al.), Springer, 2015, 111-121.


    S. D. Cardell and A. Fúster-Sabater, Linear models for the self-shrinking generator based on CA, J. Cell. Autom., 11 (2016), 195-211.


    K. Cattell and J. C. Muzio, One-dimensional linear hybrid cellular automata, IEEE Trans. Comp.-Aided Des., 15 (1996), 325-335.doi: 10.1109/12.508317.


    D. Coppersmith, H. Krawczyk and Y. Mansour, The shrinking generator, in Adv. Crypt. - CRYPTO '93, Springer-Verlag, 1993, 23-39.doi: 10.1007/3-540-48329-2_3.


    A. K. Das, A. Ganguly, A. Dasgupta, S. Bhawmik and P. P. Chaudhuri, Efficient characterisation of cellular automata, IEEE Proc. Comp. Dig. Techn., 137 (1990), 81-87.


    S. Das and D. RoyChowdhury, Car30: A new scalable stream cipher with rule 30, Crypt. Commun., 5 (2013), 137-162.doi: 10.1007/s12095-012-0079-1.


    P. F. Duvall and J. C. Mortick, Decimation of periodic sequences, SIAM J. Appl. Math., 21 (1971), 367-372.


    A. Fúster-Sabater and P. Caballero-Gil, Linear solutions for cryptographic nonlinear sequence generators, Phys. Lett. A, 369 (2007), 432-437.doi: 10.1063/1.2827050.


    A. Fúster-Sabater, M. E. Pazo-Robles and P. Caballero-Gil, A simple linearization of the self-shrinking generator by means of cellular automata, Neural Netw., 23 (2010), 461-464.


    S. W. Golomb, Shift Register-Sequences, Aegean Park Press, Laguna Hill, California, 1982.


    J. Jose, S. Das and D. RoyChowdhury, Inapplicability of fault attacks against trivium on a cellular automata based stream cipher, in 11th Int. Conf. Cell. Autom. Res. Ind. ACRI 2014, Springer-Verlag, 2014, 427-436.


    A. Kanso, Modified self-shrinking generator, Comp. Electr. Engin., 36 (2010), 993-1001.


    R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge Univ. Press, New York, NY, 1986.


    J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.


    W. Meier and O. Staffelbach, Analysis of pseudo random sequences generated by cellular automata, in Adv. Crypt. - EUROCRYPTO '91, Springer-Verlag, Berlin, 1991, 186-199.doi: 10.1007/3-540-46416-6_17.


    W. Meier and O. Staffelbach, The self-shrinking generator, in Adv. Crypt. - EUROCRYPT 1994, Springer-Verlag, 1994, 205-214.doi: 10.1007/BFb0053436.


    A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, FL, 1996.


    M. Mihaljević, Y. Zheng and H. Imai, A fast and secure stream cipher based on cellular automata over GF(q), in Proc. Global Telecomm. Conf. GLOBECOM 1998, 1998, 3250-3255.


    C. Paar and J. Pelzl, Understanding Cryptography, Springer, Berlin, 2010.


    S. Wolfram, Cellular automata as simple self-organizing system, Caltrech preprint, CALT-68-938, 1982.


    S. Wolfram, Cryptography with cellular automata, in Adv. Crypt. - EUROCRYPT 1985, Springer-Verlag, 1985, 429-432.

  • 加载中

Article Metrics

HTML views() PDF downloads(294) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint