Recursive Algorithm for Forming Structured Sets of Information Blocks to Increase the Speed of Their Source Determination Procedures

Purpose of research. In some classes of information systems, it is impossible to use well-known algorithms for the identification and the authentication the data blocks sources. The reason for this is the duration of the full data processing cycle. The article considers the original algorithm for determining sources for a group of data blocks. It allows you to detect errors faster than the usual iterative algorithm for forming tree structures of blocks by changing the order of base operations. The purpose of the work is to reduce the computational and resource costs for the receiver to perform identification the sources of blocks, each of them has a size not exceeding a few bytes.
Methods. The identification method based on the forming a tree structure of incoming information blocks and subsequent analysis of tree branches. It allows selecting a chain of blocks formed by the target source. In the article the formal description of the algorithm is given. The results of the simulation of the procedures for determining the source are presented. In this case, the characteristics of the recursive algorithm were compared with those obtained for the known iterative one.
Results. The relationships between the average number of typical hash comparison operations, the average number of tree structure branches, and the number of accepted blocks obtained as a result of simulation modeling. This made it possible to determine the conditions for applying the recursive and iterative algorithms.
Conclusion. It is shown that the using of a recursive algorithm for forming a tree structure of frames can reduce the average number of base operations performed by the receiver by 5-10 % and reduce the memory cost for storing tree structure branches by up to 30%.

1. Malchukov A.N., Osokin A.N. Sistema avtomatizirovannogo proektirovaniya kodekov pomekhoustojchivyh kodov korotkoj dliny [Computer-aided design system for shortlength noise-resistant codecs]. Izvestiya Tomskogo politekhnicheskogo universiteta = Bulletin of the Tomsk Polytechnic University, 2008, vol. 312, no. 5, pp. 70-75 (In Russ.).

2. Mycko E.A., Mal'chukov A.N., Ivanov S.D. Issledovanie algoritmov vychisleniya kontrol'noj summy CRC8 v mikroprocessornyh sistemah pri deficite resursov [Investigation of algorithms for calculating the CRC8 checksum in microprocessor systems with a shortage of resources]. Pribory i sistemy. Upravlenie, kontrol', diagnostika = Instrements and Systems: Monitoring, Control and Diagnostics, 2018, no. 6, pp. 22-29 (In Russ.).

3. Xie J., Pan X. An improved rc4 stream cipher. International Conference on Computer Application and System Modeling. 2010. https://doi.org:10.1109/IC-CASM.2010.5620800

4. Zhang W., Gong X., Han G. An improved ant colony algorithm for path planning in one scenic area with many spots. Mathematical Problems in Engineering, 2016. https://doi.org:10.1155/2016/7672839

5. Allouch A., Cheikhrouhou O., Koubaa A. MAVSec: Securing the MAVLink Protocol for Ardupilot/PX4 Unmanned Aerial Systems. International Wireless Communications and Mobile Computing Conference (IWCMC). Morrocco, 2019. https://doi.org:10.1109/IWCMC.2019.8766667

6. Iwata T., Kurosawa K. OMAC: one-key CBC MAC. Fast Software Encryption. 2003, pp. 129 – 53.

7. Liu C., Ji J., Liu Z. Implementation of DES Encryption Arithmetic based on FPGA. AASRI Procedia, 2013, vol. 5, pp. 209–213.

8. Black J., Rogaway P. CBC MACs for arbitrary-length messages: The three-key constructions. J. Cryptol, 2015, vol. 18, no.2, pp. 111–131.

9. Stallings W. NIST Block Cipher Modes of Operation for Confidentiality. Cryptologia, 2010, no. 34(2), pp. 163 – 175.

10. Ben Othman S., Alzaid H., Trad A., Youssef H. An efficient secure data aggregation scheme for wireless sensor networks. IISA, 2013. https://doi.org:10.1109/ iisa.2013.6623701

11. Fangfang Dai, Yue Shi, Nan Meng, Liang Wei and Zhiguo Ye From Bitcoin to Cybersecurity: a Comparative Study of Blockchain Application and Security Issues. The 2017 4th International Conference on Systems and Informatics (ICSAI 2017). Hangzhou, China 2017.

12. Levitin A. V. Algoritmy. Vvedenie v razrabotku i analiz [Introduction to development and analysis]. Moscow, Vil'yams Publ., 2006. 576 p. (In Russ.).

13. Kormen T. H., Lejzerson CH. I., Rivest R. L., SHtajn K. Algoritmy. Postroenie i analiz [Algorithms. Construction and analysis]. Moscow, Vil'yams Publ., 2019. 1328 p. (In Russ.).

14. Tanygin M.O., Alshaia H.YA., Altuhova V.A. Ob odnom metode kontrolya celostnosti peredavae-moj poblokovo informacii [On one method of controlling the integrity of the information transmitted by the block]. Telekommunikacii = Telecommunications, 2019, no. 3, pp. 12-21 (In Russ.).

15. Tanygin M.O., Alshaia H.A., Dobrica V.P. Ocenka vliyaniya organizacii bufernoj pamyati na skorost' vypolneniya procedur opredeleniya istochnika soobshchenij [Assessment of the impact of the organization of the buffer memory to the speed of the procedures for determining the source of the message]. Trudy MAI = Proceedings of MAI, 2020, no. 5(114), p.15 (In Russ.).

16. Tanygin M.O. Teoreticheskie osnovy identifikacii istochnikov informacii, peredavaemoj blokami ogranichennogo razmera [Theoretical bases of identification of sources of information transmitted blocks of limited size]. Kursk, 2020. 198 p. (In Russ.).

17. Kelton V., Lou A. Imitacionnoe modelirovanie [Simulation modeling]. Saint Petersburg, Piter Publ., 2004. 874 p. (In Russ.).

18. Strogalev V.P., Tolkacheva I.O. Imitacionnoe modelirovanie [Simulation modeling]. Moscow, MGTU im. Baumana Publ., 2008. 279 p. (In Russ.).

19. Horovitz P. Iskusstvo skhemotekhniki [The art of circuit engineering]. Moscow, 2012. 600 p. (In Russ.).

20. Tanenbaum E., Ostin T. Arhitektura komp'yutera [Computer Architecture]. Saint Petersburg, Piter Publ., 2012. 816 p. (In Russ.).

21. Predvaritel'nyj nacionalnyj standart RF. Informacionnye tekhnologii. Internet veshchej. Protokol obmena dlya vysokoemkih setej s bolshim radiusom dejstviya i nizkim energopotrebleniem [Preliminary National Standard of the Russian Federation. Information technologies. The Internet of Things. Exchange protocol for high-capacity networks with a long range and low power consumption]. Available at: http://docs.cntd.ru/document/554596382 (accessed 15.03.2021) (In Russ.).