[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Preliminary Analysis of Interleaving PN-Sequences

  • Conference paper
  • First Online:
Computational Science and Its Applications – ICCSA 2021 (ICCSA 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12949))

Included in the following conference series:

  • 1233 Accesses

Abstract

Some pseudorandom sequences with good crytographic features can be obtained from the interleaving of other families of sequences with unsuitable properties. PN-sequences obtained from maximum-length Linear Feedback Shift Registers exhibit good statistical aspects, such as balancedness, large period, adequate distribution of 0s and 1s and excellent autocorrelation, although their linearity makes them vulnerable against cryptographic attacks. In this work, we present a preliminary analysis on the random features of the interleaving of shifted versions of a PN-sequence. The application of statistical and graphic tests and their corresponding results complete the work.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Wu, H.: The stream cipher HC-128. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 39–47. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68351-3_4

    Chapter  Google Scholar 

  2. Barnsley, M.: Fractals Everywhere. Academic Press, Cambridge (1988)

    MATH  Google Scholar 

  3. Bassham, L., et al.: A statistical test suite for random and pseudorandom number generators for cryptographic applications (16 September 2010). https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=906762

  4. Biryukov, A., Perrin, L.: State of the art in lightweight symmetric cryptography. IACR Cryptol. ePrint Arch. 2017, 511 (2017)

    Google Scholar 

  5. Bishoi, S.K., Senapati, K., Shankar, B.: Shrinking generators based on \(\sigma \)-LFSRs. Discret. Appl. Math. 285, 493–500 (2020). https://www.sciencedirect.com/science/article/pii/S0166218X20303346

  6. Bluestein, L.I.: Interleaving of pseudorandom sequences for synchronization. IEEE Trans. Aerosp. Electron. Syst. AES 4(4), 551–556 (1968)

    Article  Google Scholar 

  7. Caballero-Gil, P., Fúster-Sabater, A., Pazo-Robles, M.E.: New attack strategy for the shrinking generator. J. Res. Pract. Inf. Technol. 41(2), 171–180 (2009)

    Google Scholar 

  8. Cardell, S.D., Aranha, D.F., Fúster-Sabater, A.: Recovering decimation-based cryptographic sequences by means of linear CAs. Logic J. IGPL 28(4), 430–448 (2020)

    Article  MathSciNet  Google Scholar 

  9. Cardell, S.D., Fúster-Sabater, A.: Cryptanalysing the shrinking generator. Procedia Comput. Sci. 51, 2893–2897 (2015)

    Article  Google Scholar 

  10. Cardell, S.D., Fúster-Sabater, A.: Performance of the cryptanalysis over the shrinking generator. In: Herrero, Á., Baruque, B., Sedano, J., Quintián, H., Corchado, E. (eds.) International Joint Conference. CISIS 2015. Advances in Intelligent Systems and Computing, vol. 369. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19713-5_10

  11. Cardell, S.D., Fúster-Sabater, A., Ranea, A.: Linearity in decimation-based generators: an improved cryptanalysis on the shrinking generator. Open Math. 16(1), 646–655 (2018)

    Article  MathSciNet  Google Scholar 

  12. Cardell, S.D., Fúster-Sabater, A., Requena, V.: Interleaving shifted versions of a PN-sequence. Mathematics 9(687), 1–23 (2021)

    Google Scholar 

  13. Cardell, S.D., Fúster-Sabater, A.: Linear models for high-complexity sequences. In: Gervasi, O., et al. (eds.) ICCSA 2017, Part I. LNCS, vol. 10404, pp. 314–324. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62392-4_23

    Chapter  Google Scholar 

  14. Díaz Cardell, S., Fúster-Sabater, A.: Cryptography with Shrinking Generators. SM, Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12850-0

    Book  MATH  Google Scholar 

  15. Coppersmith, D., Herzberg, A., Krawczyk, H.M., Kutten, S., Mansour, Y.: A shrinking generator for cryptosystems (1987). https://patents.google.com/patent/EP0619659A2/en

  16. Coppersmith, D., Krawczyk, H., Mansour, Y.: The shrinking generator. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 22–39. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_3

    Chapter  Google Scholar 

  17. Crilly, T.: Interleaving integer sequences. Math. Gaz. 91(520), 27–33 (2007)

    Article  MathSciNet  Google Scholar 

  18. Doğanaksoy, A., Göloğlu, F.: On Lempel-Ziv complexity of sequences. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 180–189. Springer, Heidelberg (2006). https://doi.org/10.1007/11863854_15

    Chapter  MATH  Google Scholar 

  19. Edemskiy, V.: On the linear complexity of interleaved binary sequences of period 4p obtained from hall sequences or Legendre and hall sequences. Electron. Lett. 50(8), 604–605 (2014)

    Article  Google Scholar 

  20. Eisenbarth, T., Kumar, S., Paar, C., Poschmann, A., Uhsadel, L.: A survey of lightweight-cryptography implementations. IEEE Des. Test Comput. 24(6), 522–533 (2007)

    Article  Google Scholar 

  21. Fluhrer, S.R., McGrew, D.A.: Statistical analysis of the alleged RC4 keystream generator. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) FSE 2000. LNCS, vol. 1978, pp. 19–30. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44706-7_2

    Chapter  Google Scholar 

  22. Fúster-Sabater, A.: Generation of cryptographic sequences by means of difference equations. Appl. Math. Inf. Sci. 8, 475–484 (2014)

    Article  MathSciNet  Google Scholar 

  23. Gennaro, R.: Randomness in cryptography. IEEE Secur. Priv. 4(02), 64–67 (2006)

    Article  Google Scholar 

  24. Golomb, S.W.: Shift Register-Sequences. Aegean Park Press, Laguna Hill (1982)

    MATH  Google Scholar 

  25. Gong, G.: Theory and applications of \(q\)-ary interleaved sequences. IEEE Trans. Inf. Theory 41(2), 400–411 (1995)

    Article  MathSciNet  Google Scholar 

  26. Jiang, S., Dai, Z., Gong, G.: On interleaved sequences over finite fields. Discret. Math. 252, 161–178 (2002)

    Article  MathSciNet  Google Scholar 

  27. Li, N., Tang, X.: On the linear complexity of binary sequences of period \(4n\) with optimal autocorrelation value/magnitude. IEEE Trans. Inf. Theory 57(11), 7597–7604 (2011)

    Article  MathSciNet  Google Scholar 

  28. Martyn, T.: The chaos game revisited: yet another, but a trivial proof of the algorithm’s correctness. Appl. Math. Lett. 25(2), 206–208 (2012). https://www.sciencedirect.com/science/article/pii/S0893965911003922

  29. Massey, J.: Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15(1), 122–127 (1969)

    Article  MathSciNet  Google Scholar 

  30. Mata-Toledo, R.A., Willis, M.A.: Visualization of random sequences using the chaos game algorithm. J. Syst. Softw. 39(1), 3–6 (1997). https://www.sciencedirect.com/science/article/pii/S0164121296001586

  31. Maurer, U.M.: A universal statistical test for random bit generators. J. Cryptol. 5(2), 89–105 (1992). https://doi.org/10.1007/BF00193563

    Article  MathSciNet  MATH  Google Scholar 

  32. Orúe, A.B., Fúster-Sabater, A., Fernández, V., Montoya, F., Hernández, L., Martín, A.: Herramientas gráficas de la criptografía caótica para el análisis de la calidad de secuencias pseudoaleatorias, p. 180–185. Actas de la XIV Reunión Española sobre Criptología y Seguridad de la Información, RECSI XIV, Menorca, Illes Balears, Spain (October 2016)

    Google Scholar 

  33. Orúe, A.B., Hernández, L., Martín, A., Montoya, F.: A lightweight pseudorandom number generator for securing the Internet of Things. IEEE Access 5, 27800–27806 (2017)

    Article  Google Scholar 

  34. Peitgen, H.O., Jurgens, H., Saupe, D.: Chaos and Fractals: New Frontiers of Science. Springer, Heidelberg (2004). https://doi.org/10.1007/b97624

    Book  MATH  Google Scholar 

  35. Pérez, G., Cerdeira, H.A.: Extracting messages masked by chaos. Phys. Rev. Lett. 74, 1970–1973 (1995). https://link.aps.org/doi/10.1103/PhysRevLett.74.1970

  36. Tang, X., Ding, C.: New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value. IEEE Trans. Inf. Theory 56(12), 6398–6405 (2010)

    Article  MathSciNet  Google Scholar 

  37. U.S. Department of Commerce: FIPS 186, Digital signature standard. Federal Information Processing Standards Publication 186, N.I.S.T., National Technical Information Service, Springfield, Virginia (1994)

    Google Scholar 

  38. Xiong, H., Qu, L., Li, C., Fu, S.: Linear complexity of binary sequences with interleaved structure. IET Commun. 7(15), 1688–1696 (2013)

    Article  Google Scholar 

Download references

Acknowledgements

This work was in part supported by Comunidad de Madrid (Spain) under project CYNAMON (P2018/TCS-4566), co-funded by FSE and European Union FEDER funds. The third author is partially supported by Spanish grant VIGROB-287 of the Universitat d’Alacant.

Author information

Authors and Affiliations

  1. Centro de Matemática, Computação e Cognição, UFABC, Santo André-SP, Brazil

    Sara D. Cardell

  2. Instituto de Tecnologías Físicas y de la Información (CSIC), Madrid, Spain

    Amparo Fúster-Sabater

  3. Departamento de Matemáticas, Universidad de Alicante, Alicante, Spain

    Verónica Requena

Authors
  1. Sara D. Cardell
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Amparo Fúster-Sabater
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Verónica Requena
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sara D. Cardell .

Editor information

Editors and Affiliations

  1. University of Perugia, Perugia, Italy

    Osvaldo Gervasi

  2. University of Basilicata, Potenza, Potenza, Italy

    Beniamino Murgante

  3. Covenant University, Ota, Nigeria

    Sanjay Misra

  4. University of Cagliari, Cagliari, Italy

    Chiara Garau

  5. University of Cagliari, Cagliari, Italy

    Ivan Blečić

  6. Monash University, Clayton, VIC, Australia

    David Taniar

  7. Kyushu Sangyo University, Fukuoka, Japan

    Bernady O. Apduhan

  8. University of Minho, Braga, Portugal

    Ana Maria A. C. Rocha

  9. Polytechnic University of Bari, Bari, Italy

    Eufemia Tarantino

  10. Polytechnic University of Bari, Bari, Italy

    Carmelo Maria Torre

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cardell, S.D., Fúster-Sabater, A., Requena, V. (2021). Preliminary Analysis of Interleaving PN-Sequences. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2021. ICCSA 2021. Lecture Notes in Computer Science(), vol 12949. Springer, Cham. https://doi.org/10.1007/978-3-030-86653-2_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-86653-2_21

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-86652-5

  • Online ISBN: 978-3-030-86653-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation