Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
-->


DOI 10.34229/KCA2522-9664.25.1.2
УДК 519.8

С.М. НІКОЛАЄВ
Науково-дослідний інститут воєнної розвідки, Київ, Україна,
divan24@i.ua


УДОСКОНАЛЕНИЙ МЕТОД БЕРЛЕКЕМПА–МЕССІ ЯК ОСНОВА
ПОШУКУ ПЕРІОДИЧНОСТЕЙ У БІТОВИХ ПОТОКАХ

Анотація. Запропоновано вдосконалення методу Берлекемпа–Мессі у разі його застосування для пошуку періодичностей у бітових потоках з помилками. Суть удосконалення полягає в інакшому розбитті бітового потоку на блоки, використанні послідовного побітового зсуву перед кожним обчисленням параметрів, а також у прийнятті рішення про довжину регістра і значення полінома зворотного зв’язку на основі запропонованого математичного виразу.

Ключові слова: регістр зсуву з лінійним зворотним зв’язком, довжина регістра, поліном зворотного зв’язку, бітовий потік, метод Берлекемпа–Мессі.


повний текст

СПИСОК ЛІТЕРАТУРИ

  • 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. Задірака В.К., Олексюк О.С. Комп’ютерна криптологія. Підручник. Київ; Тернопіль: Збруч, 2002. 504 с.

  • 4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Москва: Триумф, 2002. 816 с.

  • 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. Поточные шифры. Результаты зарубежной открытой криптологии. Москва: Мир, 1997. 389 с.

  • 23. Крылова В.А. Помехоустойчивое кодирование. Методы и алгоритмы циклических БЧХ кодов. Харьков: НТУ «ХПИ», 2016. 200 с. URL: https://repository.kpi.kharkov.ua/server/ api/core/bitstreams/ .




© 2025 Kibernetika.org. All rights reserved.