Nieliniowe rejestry przesuwne i łączenie skrzyżowanych par stanów

• Autorzy: Mykkeltveit J. , Szmidt J.

Warianty tytułu

EN

Nonlinear Feedback Shift Registers and Joining of Cross-Pairs States

• Języki publikacji: PL

Abstrakty

PL

Wyjaśniamy pochodzenie funkcji sprzężenia zwrotnego dla Nieliniowych Rejestrów Przesuwnych ze Sprzężeniem Zwrotnym (NFSR), które generują binarne ciągi de Bruijna. Funkcje te powstają przez zastosowanie operacji łączenia skrzyżowanych par stanów do wybranego rejestru przesuwnego generującego ciąg binarny o maksymalnym okresie; np. rejestru liniowego, który zawsze istnieje dla danego rzędu n. Otrzymany wynik pozwala konstruować wszystkie nieliniowe rejestry przesuwne generujące ciągi binarne o okresie 2ⁿ -1.

EN

We explain the origins of Boolean feedback functions of Nonlinear Feedback Shift Registers (NFSR) of fixed order n generating de Bruijn binary sequences. They all come into existence by cross joining operations starting from one maximum period feedback shift register, e.g., a linear one which always exists for any order n. The result obtained yields some constructions of NFSR generating maximum period 2ⁿ -1 binary sequences.

Słowa kluczowe

PL

nieliniowe rejestry przesuwne; sprzężenie zwrotne; ciągi de Bruijna; metoda łączenia skrzyżowanych par stanów

EN

nonlinear feedback shift registers; de Bruijn sequences; method of joining of cross-pairs states

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 271--284
• Opis fizyczny: Bibliogr. 30 poz.

Twórcy

autor

Mykkeltveit J.

• International Research Institute, Bergen, Norway

autor

Szmidt J.

• Wojskowy Instytut Łączności, Zegrze, Poland

Bibliografia

• [1] S. Babbage, M. Dodd, ”The MICKEY stream ciphers”, in New Stream Cipher Designs: The eSTREAM Finalists. LNCS vol. 4986, pp. 191–209. Springer-Verlag, 2008.
• [2] N. G. de Bruijn, A combinatorial problem, Indag. Math., 8(1946), pp. 461–467.
• [3] A. H. Chan, R. A. Games, J. J. Rushanan, On the quadratic m-sequences, Proceedings of Fast Software Encryption, LNCS vol. 809, pp. 166–173. Springer-Verlag, 1994.
• [4] C. Canniere, B. Preneel, ”Trivium”, in New Stream Cipher Designs: The eSTREAM Finalists, LNCS vol. 4986, pp. 244–266. Springer-Verlag, 2008.
• [5] P. Dąbrowski, G. Łabuzek, T. Rachwalik, J. Szmidt, Searching for nonlinear feedback shift registers with parallel computing, Inform. Proc. Letters, 114(2014), pp. 268–272.
• [6] E. Dubrova, A scalable method for constructing Galois NLFSRs with period 2n −1 using cross-join pairs, IEEE Trans. on Inform. Theory, 59(1), 2013, pp. 703–709.
• [7] J. C. Fletcher, M. Perlman, Nonlinear nonsingular feedback shift registers, United States Patent 3911330, 1975.
• [8] C. Flye Sainte-Marie, Solution to question nr. 48. L’Intermédiaire des Mathématiciens, 1(1894). pp. 107–110.
• [9] H. Fredricksen, A class of nonlinear de Bruijn cycles, J. of Combinatorial Theory (A), 19(1975), pp. 192–199.
• [10] H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms, SIAM Review, 24(2), 1982, pp. 195–221.
• [11] B. M. Gammel, R. Goetffert, O. Kniffler, Achterbahn 128/80, The eSTREAM project, www.ecrypt.eu.org/stream/ , www.matpack.de/achterbahn/
• [12] S. W. Golomb, Shift register sequences. San Francisco, Holden-Day, 1967, revised edition, Laguna Hills, CA, Aegean Park Press, 1982.
• [13] S. W. Golomb, G. Gong, Signal Design for Good Correlation. For Wireless Communication, Cryptography, and Radar, Cambridge University Press, 2005.
• [14] E. R. Hauge, T. Helleseth, De Bruijn sequences, irreducible codes and cyclotomy, Discrete Math., 159(1996), pp. 143–154.
• [15] M. Hell, T. Johansson, A. Maximov, W. Meier, ”The Grain Family of Stream Ciphers”, in New Stream Cipher Designs: The eSTREAM Finalists. LNCS vol. 4986, pp. 179–190. Springer-Verlag, 2008.
• [16] T. Helleseth, T. Kløve, The number of cross-join pairs in maximum length linear sequences, IEEE Trans. on Inform. Theory, 31(1991), pp. 1731–1733.
• [17] F. Hemmati, A large class of nonlinear shift register sequences, IEEE Trans. on Inform. Theory, vol. 28, pp. 355-359, 1982.
• [18] C. J. A. Jansen, Investigations on nonlinear streamcipher systems: Construction and evaluation methods, Ph.D. Thesis, Technical University of Delft, 1989.
• [19] R. Lidl, H. Niederreiter, Introduction to Finite Fields and their Applications (Revised Edition), Cambridge University Press, Cambridge, 1994.
• [20] K. B. Magleby, The synthesis of nonlinear feedback shift registers, Technical Report no. 6207-1. Stanford Electronics Laboratories, 1963.
• [21] K. Mandal, G. Gong, Cryptographically strong de Bruijn sequences with large periods. Selected Areas in Cryptography. L. R. Knudsen, K. Wu (Eds.). LNCS, vol. 7707, pp. 104–118. Springer-Verlag, 2012.
• [22] G. L. Mayhew, S. W. Golomb, Linear spans of modified de Bruijn sequences, IEEE Trans. Inform. Theory, 36(5), 1990, pp. 1166–1167.
• [23] J. Mykkeltveit Generating and counting the double adjacencies in a pure cyclic shift register, Trans. on Computers, C-24, 1975, pp. 299–304.
• [24] J. Mykkeltveit, M-K. Siu, P. Tong, On the cyclic structure of some nonlinear shift register sequences, Inform. and Control, 43(1979), pp. 202–215.
• [25] J. Mykkeltveit, J. Szmidt On cross joining de Bruijn sequences, Contemporary Mathematics, vol. 632, pp. 333–344, American Mathematical Society, 2015.
• [26] T. Rachwalik, J. Szmidt, R. Wicik, J. Zabłocki, Generation of nonlinear feedback shift registers with special purpose hardware, Military Communications and Information Systems Conference, MCC 2012, IEEE Xplore Digital Library, 2012, pp. 151–154.
• [27] R. Wicik, T. Rachwalik, Modified alternating step generators, Military Communications and Information Systems Conference, MCC 2013. IEEE Xplore Digital Library, 2013, pp. 203-215.
• [28] M. S. Turan, On the nonlinearity of maximum-length NFSR feedbacks, Cryptography and Communications, 4(3-4), 2012, pp. 233-243.
• [29] Python Programming Language, http://www.python.org
• [30] SAGE Mathematical Software, Version 5.8. http://www.sagemath.org

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).