American Institute of Mathematical Sciences

Advanced
November  2016, 10(4): 797-809. doi: 10.3934/amc.2016041

Modelling the shrinking generator in terms of linear CA

Sara D. Cardell 1, and  Amparo Fúster-Sabater 2,

1. 

Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas (UNICAMP), R. Sérgio Buarque de Holanda, 651, Cidade Universitária, Campinas - SP, 13083-859
2. 

Instituto de Tecnologías Físicas y de la Información, Consejo Superior de Investigaciones Científicas, C/Serrano 144, 28006, Madrid, Spain

Received  December 2014 Revised  June 2016 Published  November 2016

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.
Keywords: Shrinking generator, interleaved PN-sequences, cellular automata, characteristic polynomial., rule 102, shrunken sequence.
Mathematics Subject Classification: Primary: 37B15, 11B85; Secondary: 12E0.
Citation: Sara D. Cardell, Amparo Fúster-Sabater. Modelling the shrinking generator in terms of linear CA. Advances in Mathematics of Communications, 2016, 10 (4) : 797-809. doi: 10.3934/amc.2016041
References:
[1]

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

[2]

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.), (2015), 111.   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

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.   Google Scholar

[7]

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

[8]

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

[9]

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

[10]

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.   Google Scholar

[11]

S. W. Golomb, Shift Register-Sequences,, Aegean Park Press, (1982).   Google Scholar

[12]

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, (2014), 427.   Google Scholar

[13]

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

[14]

R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications,, Cambridge Univ. Press, (1986).   Google Scholar

[15]

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

[16]

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

[17]

W. Meier and O. Staffelbach, The self-shrinking generator,, in Adv. Crypt. - EUROCRYPT 1994, (1994), 205.  doi: 10.1007/BFb0053436.  Google Scholar

[18]

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography,, CRC Press, (1996).   Google Scholar

[19]

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.   Google Scholar

[20]

C. Paar and J. Pelzl, Understanding Cryptography,, Springer, (2010).   Google Scholar

[21]

S. Wolfram, Cellular automata as simple self-organizing system,, Caltrech preprint, (1982), 68.   Google Scholar

[22]

S. Wolfram, Cryptography with cellular automata,, in Adv. Crypt. - EUROCRYPT 1985, (1985), 429.   Google Scholar

show all references

References:
[1]

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

[2]

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.), (2015), 111.   Google Scholar

[3]

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

[4]

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

[5]

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

[6]

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.   Google Scholar

[7]

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

[8]

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

[9]

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

[10]

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.   Google Scholar

[11]

S. W. Golomb, Shift Register-Sequences,, Aegean Park Press, (1982).   Google Scholar

[12]

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, (2014), 427.   Google Scholar

[13]

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

[14]

R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications,, Cambridge Univ. Press, (1986).   Google Scholar

[15]

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

[16]

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

[17]

W. Meier and O. Staffelbach, The self-shrinking generator,, in Adv. Crypt. - EUROCRYPT 1994, (1994), 205.  doi: 10.1007/BFb0053436.  Google Scholar

[18]

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography,, CRC Press, (1996).   Google Scholar

[19]

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.   Google Scholar

[20]

C. Paar and J. Pelzl, Understanding Cryptography,, Springer, (2010).   Google Scholar

[21]

S. Wolfram, Cellular automata as simple self-organizing system,, Caltrech preprint, (1982), 68.   Google Scholar

[22]

S. Wolfram, Cryptography with cellular automata,, in Adv. Crypt. - EUROCRYPT 1985, (1985), 429.   Google Scholar

[1]

T.K. Subrahmonian Moothathu. Homogeneity of surjective cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 13 (1) : 195-202. doi: 10.3934/dcds.2005.13.195
[2]

Achilles Beros, Monique Chyba, Oleksandr Markovichenko. Controlled cellular automata. Networks & Heterogeneous Media, 2019, 14 (1) : 1-22. doi: 10.3934/nhm.2019001
[3]

Marcus Pivato. Invariant measures for bipermutative cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 723-736. doi: 10.3934/dcds.2005.12.723
[4]

Achilles Beros, Monique Chyba, Kari Noe. Co-evolving cellular automata for morphogenesis. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2053-2071. doi: 10.3934/dcdsb.2019084
[5]

Jon Chaika, David Constantine. A quantitative shrinking target result on Sturmian sequences for rotations. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 5189-5204. doi: 10.3934/dcds.2018229
[6]

Bernard Host, Alejandro Maass, Servet Martínez. Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1423-1446. doi: 10.3934/dcds.2003.9.1423
[7]

Marcelo Sobottka. Right-permutative cellular automata on topological Markov chains. Discrete & Continuous Dynamical Systems - A, 2008, 20 (4) : 1095-1109. doi: 10.3934/dcds.2008.20.1095
[8]

Xinxin Tan, Shujuan Li, Sisi Liu, Zhiwei Zhao, Lisa Huang, Jiatai Gang. Dynamic simulation of a SEIQR-V epidemic model based on cellular automata. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 327-337. doi: 10.3934/naco.2015.5.327
[9]

Akinori Awazu. Input-dependent wave propagations in asymmetric cellular automata: Possible behaviors of feed-forward loop in biological reaction network. Mathematical Biosciences & Engineering, 2008, 5 (3) : 419-427. doi: 10.3934/mbe.2008.5.419
[10]

Said Hadd, Rosanna Manzo, Abdelaziz Rhandi. Unbounded perturbations of the generator domain. Discrete & Continuous Dynamical Systems - A, 2015, 35 (2) : 703-723. doi: 10.3934/dcds.2015.35.703
[11]

Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115
[12]

Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050
[13]

I-Lin Wang, Ju-Chun Lin. A compaction scheme and generator for distribution networks. Journal of Industrial & Management Optimization, 2016, 12 (1) : 117-140. doi: 10.3934/jimo.2016.12.117
[14]

Jimmy Tseng. On circle rotations and the shrinking target properties. Discrete & Continuous Dynamical Systems - A, 2008, 20 (4) : 1111-1122. doi: 10.3934/dcds.2008.20.1111
[15]

Kevin Kuo, Phong Luu, Duy Nguyen, Eric Perkerson, Katherine Thompson, Qing Zhang. Pairs trading: An optimal selling rule. Mathematical Control & Related Fields, 2015, 5 (3) : 489-499. doi: 10.3934/mcrf.2015.5.489
[16]

Piotr Jaworski, Marcin Pitera. The 20-60-20 rule. Discrete & Continuous Dynamical Systems - B, 2016, 21 (4) : 1149-1166. doi: 10.3934/dcdsb.2016.21.1149
[17]

Dmitry Kleinbock, Xi Zhao. An application of lattice points counting to shrinking target problems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 155-168. doi: 10.3934/dcds.2018007
[18]

Petr Kůrka. On the measure attractor of a cellular automaton. Conference Publications, 2005, 2005 (Special) : 524-535. doi: 10.3934/proc.2005.2005.524
[19]

Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015
[20]

Vittorio Martino. On the characteristic curvature operator. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1911-1922. doi: 10.3934/cpaa.2012.11.1911

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences