Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
KIBERNETYKA TA SYSTEMNYI ANALIZ
International Theoretical Science Journal
-->


DOI 10.34229/KCA2522-9664.25.1.2
UDC 519.8
S. Nikolaev1


1 Defence Intelligence Research Institute, Kyiv, Ukraine

divan24@i.ua

ADVANCED BERLEKAMP–MASSEY METHOD AS A BASIS FOR FINDING
PERIODICITIES IN BITSTREAMS

Abstract. The author has proposed an improvement of the Berlekamp–Massey method when used for searching periodicities in bitstreams with errors. The essence of the improvement is another splitting of а bitstream into blocks, using a consistent bit shift before every parameter processing, and making decisions about the register’s length and feedback polynomial based on proposed mathematical formulas.

Keywords: linear feedback shift register, register length, feedback polynomial, bitstream, Berlekamp–Massey method.


full text

REFERENCES

  • 1. Golomb S.W. Shift register sequences. Laguna Hills, CA Aegean: Park Press, 1982. 247 p.

  • 2. Palagin A.V., Opanasenko V.N. Reconfigurable computing technology. Cybernetics and Systems Analysis. 2007. Vol. 43, N 5. P. 675–686. https://doi.org/10.1007/s10559-007-0093-z. .

  • 3. Zadiraka V.K., Oleksiuk O.S. Computer Cryptology. Textbook [in Ukrainian]. Kyiv; Ternopil: Zbruch, 2002. 504 p.

  • 4. Schneier B. Applied cryptography. Protocols, algorithms, source texts in C [in Russian]. Moscow: Triumph, 2002. 816 p.

  • 5. Mhaibes H.I., Abood M.H., Farhan A.K. Simple lightweight cryptographic algorithm to secure imbedded IoT devices. International Journal of Interactive Mobile Technologies. 2022. Vol. 16, N 20. Р. 98–113. https://doi.org/10.3991/ijim.v16i20.34505 .

  • 6. Hardi S., Ramadhani R.S., Zamzami E.M., Tarigan J.T., Jaya I. Security of image file with tiny encryption algorithm and modified significant bit pseudo random number generator. Proc. 4th International Conference on Computing and Applied Informatics 2019 (ICCAI 2019) (26–27 November 2019, Medan, Indonesia. Medan, 2019). Journal of Physics: Conference Series. 2020. Vol. 1566. Article number 012108. https://doi.org/10.1088/1742-6596/1566/1/012108 .

  • 7. Fog A. Pseudo-random number generators for vector processors and multicore processors. Journal of Modern Applied Statistical Methods. 2015. Vol. 14, Iss. 1. P. 308–334. https://doi.org/10.22237/jmasm/1430454120 .

  • 8. Gupta S., Singh P., Shrotriya N., Baweja T. LFSR next bit prediction through deep learning. Journal of Informatics Electrical and Electronics Engineering. 2021. Vol. 2, Iss. 2. P. 1–9. https://doi.org/10.54060/JIEEE/002.02.022 .

  • 9. Alecu A., Salagean A. Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences. Proc. 11th IMA International Conference on Cryptography and Coding (18–20 December 2007, Cirencester, UK). Cirencester, 2007. LNCS. Vol. 4887. P. 220–232. URL: https://hdl.handle.net/2134/3287 .

  • 10. Overton M.A. Romu: Fast nonlinear pseudo-random number generators providing high quality. arXiv: 2002.11331v1[cs.DC] 26 Feb 2020. URL: https://arxiv.org/pdf/2002.11331 .

  • 11. Xing Z., Zhang W., Han G. Improved conditional differential analysis on NLFSR-based block cipher KATAN32 with MILP. Wireless Communications and Mobile Computing. 2020. Vol. 2020. Art. ID 8883557. https://doi.org/10.1155/2020/8883557 .

  • 12. Romanov О.М., Kotiubin V.Y. Periodicity search algorithms in digital sequences with block coding by their correlation properties. Radio Electronics, Computer Science, Control. 2021. N 2. P. 7–18. https://doi.org/10.15588/1607-3274-2021-2-1 .

  • 13. Nikolaev S.N., Romanov A.N. Method for recognition of parameters of error-correcting block-cyclic codes by a generator polynomial. Cybernetics and Systems Analysis. 2021. Vol. 57, N 1. P. 146–154. https://doi.org/10.1007/s10559-021-00338-w .

  • 14. Nyshchuk А., Nikolaev S., Romanov О. Methodology for analyzing bitstreams based on the use of Damerau–Levenshtein distance and other metrics. Cybernetics and Systems Analysis. 2023. Vol. 59, N 6. P. 919–927. https://doi.org/10.1007/s10559-023-00627-6 .

  • 15. Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST SP 800–22 Rev. 1а. April 2010. 131 p. https://doi.org/10.6028/NIST.SP.800-22r1a .

  • 16. Stepien R., Walczak J. Statistical analysis of the LFSR generators in the NIST STS test suite. Computer Applications in Electrical Engineering. 2013. Vol. 11. P. 356–362.

  • 17. Xie H., Wang F., Huang Z. Blind reconstruction of linear scrambler. Journal of Systems Engineering and Electronics. 2014. Vol. 25, N 4. P. 560–565. https://doi.org/10.1109/JSEE.2014.00065. .

  • 18. Berlekamp E.R. Algebraic coding theory. New York: McGraw-Hill, 1968. 466 p.

  • 19. Massey J.L. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory. 1969. Vol. 15, N 1. P. 122–127. https://doi.org/10.1109/TIT.1969.1054260. .

  • 20. Menezes A., van Oorschot P., Vanstone S. The handbook of applied cryptography. CRC Press, 1996. 816 p. URL: https://cacr.uwaterloo.ca/hac/. .

  • 21. Blahut R.E. Theory and practice of error control codes. Corr. ed. Boston: Addison-Wesley, 1983. 500 p.

  • 22. Stream Ciphers. Results of Foreign Open Cryptology [Russian translation]. Moscow: Mir, 1997. 389 p.

  • 23. Krylova V.A. Noise-correcting coding. Methods and algorithms of cyclic BCH codes [in Russian]. Kharkov: NTU "KhPI", 2016. 200 p. URL: https://repository.kpi.kharkov.ua/server/ api/core/bitstreams/ .




© 2025 Kibernetika.org. All rights reserved.