Recursive Algorithm for Forming Structured Sets of Information Blocks that Increase the Speed of Performing Procedures for Determining Their Source

Purpose of research. The article examines the features of the synthesis of specialized devices that control the integrity and authenticity of individual information blocks based on CBC codes. Approaches aimed at reducing computational and resource costs when performing such procedures are considered. The dependencies between the performance indicators and the requirements for the volume of internal memory of specialized computers processing data in CBC mode are formulated..
Methods. The implementation of data source authentication procedures using encoding in the mode of concatenation of individual data blocks is an effective method of increasing reliability in conditions of a limited size of verified authentication sequences. At the same time, its implementation in receivers requires the creation of specialized calculators that process tree-like structures that arise during data decoding, consisting of separate data blocks. To reduce resource and computational costs when processing such structures, indirect addressing is used, in which block data is stored in RAM, and their addresses are stored in the high-speed register memory of the computer itself.
Results. A model of indirect addressing of data blocks in RAM has been created. Pointers to blocks are stored in a separate register memory and each pointer is placed according to the decoded sequence number of the block in the sequence. Each block address in RAM is supplemented by a set of pointers to subsequent blocks in the branches of the tree structure. The created mathematical model made it possible to estimate the size in bits of all the pointers involved and their number, which made it possible to determine the need for a computer processing a tree structure in register memory.
Conclusion. The paper shows that using a combination of matrix and list organization of block address storage reduces the need for register memory of the calculator by 50-60%. At the same time, the computer can process the tree-like structure of information blocks using high-performance iterative algorithms, which would be impossible if only the list organization of address storage was used.

1. Tsaregorodtsev K.D. Analiz rezhimov shifrovaniya dlya realizatsii v ustroistvakh RFID [Analysis of encryption modes for implementation in RFID devices]. Prikladnaya diskretnaya matematika. Prilozhenie = Applied Discrete Mathematics. Application, 2020, no. 13, pp. 67-69. DOI 10.17223/2226308X/13/20.

2. Malchukov A.N., Osokin A.N. Sistema avtomatizirovannogo proektirovaniya kodekov pomekhoustoichivykh kodov korotkoi dliny [A computer-aided design system for short-length error-correcting codes]. Izvestiya Tomskogo politekhnicheskogo universiteta = Bulletin of the Tomsk Polytechnic University, 2008, vol. 312, no. 5, pp. 70-75.

3. Mytsko E.A., Malchukov A.N., Ivanov S.D. Issledovanie algoritmov vychisleniya kontrol'noi summy CRC8 v mikroprotsessornykh sistemakh pri defitsite resursov [Investigation of algorithms for calculating the CRC8 checksum in microprocessor systems with a shortage of resources]. Pribory i sistemy. Upravlenie, kontrol', diagnostika = Devices and Systems. Management, Control, Diagnostics, 2018, no. 6, pp. 22-29.

4. Hang S.J., Oh H.S., Park J. The improved Data Encryption Standard (DES) Algorithm. IEEE 4th International Conference on Spread Spectrum Techniques and Applications Proceedings, 1996, pp. 1310-1314.

5. Kruti S., Gambhava B. New Approach of Data Encryption Standard Algorithm. Int. J. Soft Comput. Eng. 2012, vol. 2, no. 1, pp. 322–325.

6. Sumathi R. A Secure Data Transfer Mechanism Using Single-Handed Re-Encryption Technique. International Conference on Emerging Trends in Science, Engineering and Technology. Tiruchirapalli, India, 2012, pp. 1-9.

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

8. Kruti S., Gambhava B. New Approach of Data Encryption Standard Algorithm. Int. J. Soft Comput. Eng, 2012, vol. 2, no. 1, pp. 322–325.

9. Mandal P.C. Evaluation of performance of the Symmetric Key Algorithms: DES, 3DES, AES and Blowfish. Glob. Res. Comput. Sci, 2012, vol. 3, no. 8, pp. 67–70.

10. Xie J., Pan X. An improved rc4 stream cipher. International Confer-ence on Computer Application and System Modeling. 2010. doi: 10.1109 / IC-CASM.2010.5620800.

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

12. Predvaritel'nyi natsional'nyi standart RF. Informatsionnye tekhnologii. Internet veshchei. Protokol obmena dlya vysokoemkikh setei s bol'shim radiusom deistviya i nizkim energopotrebleniem [Preliminary national standard of the Russian Federation. Information Technology. Internet of Things. An exchange protocol for high-capacity networks with a long range and low energy consumption]. Available at: http://docs.cntd.ru/document/554596382 (date of access 15.03.2021).

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

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

15. Tanygin. M.O. Algoritm opredeleniya istochnika fragmentirovannykh soobshchenii [Algorithm for determining the source of fragmented messages]. Izvestiya VUZov. Priborostroenie = Izvestiya VUZov. Instrumentation, 2020, vol. 63, no. 8, pp.702 – 710.

16. Tanygin M. O., Alshaea H. Y. A., Dobritsa V. P., Dobroserdov O. G. Recursive Algorithm for Forming Structured Sets of Information Blocks to Increase the Speed of Their Source Determination Procedures. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University. 2021; 25(2): 51-64 (In Russ.). https://doi.org/ 10.21869/2223-1560-2021-25-2-51-64.

17. Yağdereli E., Gemci C. A study on cyber-security of autonomous and unmanned vehicles. Journal of Defense Modeling and Simulation. 2015. https://doi.org/ 10.1177/1548512915575803.

18. Bespilotnye aviatsionnye sistemy. Chast' 3 [Unmanned aircraft systems. Part 3]. Ekspluatatsionnye protsedury. [Operational procedures]. Standard ISO 21384-3: 2019 (E). Available at: https://cdn.standards.iteh.ai/sam-ples/70853/7ec34c8a22bf46958423b7e3a2e43693/ISO-21384-3-2019.pdf (accessed 15.09.2020).

19. Leccadito M. A Hierarchical Architectural Framework for Securing Unmanned Aerial Systems. Virginia Commonwealth University. 2016. https://doi.org/10.25772/0DK3-E418.

20. Pasechnikov K.A., Ivanova G.S. Sintez optimal'nykh struktur dannykh dlya resheniya zadach na grafakh [Synthesis of optimal data structures for solving problems on graphs]. Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta im. N.E. Baumana. Seriya Priborostroenie. = Bulletin of the Bauman Moscow State Technical University. Instrumentation, 2008, no. 4(73), pp. 29-37.

21. Kolganov A.S. Parallel'naya realizatsiya algoritma poiska minimal'nykh ostovnykh derev'ev s ispol'zovaniem tsentral'nogo i graficheskogo protsessorov [Parallel implementation of minimum spanning tree algorithm on CPU and GPU]. Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya: Vychislitel'naya matematika i informatika = Bulletin of the South Ural State University. Computational Mathematics and Software Engineering, 2016, vol. 5, no. 3, pp. 5-19. DOI 10.14529/cmse160301.

22. Tasci S., Demirbas M. Employing in-memory data grids for distributed graph processing. IEEE 2015 IEEE International Conference on Big Data (Big Data), 2015, pp. 1856–1864. doi:10.1109/bigdata.2015.7363959

23. Paradies M, Lehner W, Bornhövd C GRAPHITE: an extensible graph traversal framework for relational database management systems. In: DBM. ACM, 2015, pp 29:1–29:12. DOI: 10.1145/2791347.2791383

24. Babionitakis K., Doumenis G.A., Georgakarakos G. et al. A real-time motion estimation FPGA architecture. J Real-Time Image Proc, 2008. 3, 3–20. https://doi.org/10.1007/s11554-007-0070-9

25. Panagiotis Papadimitratos, Zygmunt J. Haas Secure message transmission in mobile ad hoc networks. Ad Hoc Networks, 2003, no. 1, pp. 193-209.

26. Shi X., Xiao Shi D., X. A reversible watermarking authentication scheme for wireless sensor networks. Information Sciences, 2013, vol. 240, pp. 173-183. DOI: 10.1016/j.ins.2013.03.031.

27. Shant D., Premkumar P. Block Level Data Integrity Assurance Using Matrix Dialing Method towards High Performance Data Security on Cloud Storage. Scientific Research Publishing, 2016, vol. 7, no. 11, pp. 3626-3644.

28. Tanygin М.О., Alshaia Kh.A., Dobritsa V.P. Otsenka vliyaniya organizatsii bufernoi pamyati na skorost' vypolneniya protsedur opredeleniya istochnika soobshchenii [Assessment of the influence of the organization of buffer memory on the speed of execution of procedures for determining the source of messages]. Trudy MAI = Proceedings of the MAI, 2020, no. 5 (114), p.15.

29. Tanygin M.O. Raschet veroyatnosti vozniknoveniya kollizii pri ispol'zovanii algoritma kontrolya podlinnosti soobshchenii [Calculation of the probability of collisions when using the message authenticity control algorithm]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie = Proceedings of the Southwest State University. Series: Control, Computing Engineering, Information Science. Medical Instruments Engineering, 2012, no. 2-2, pp. 179-182.

30. Tanygin M.O. Teoreticheskie osnovy identifikatsii istochnikov informatsii, peredavaemoi blokami ogranichennogo razmera [Theoretical foundations for identifying sources of information transmitted by blocks of limited size]. Kursk, 2020. 198 p.