Received 16.03.2023, Revised 21.06.2023, Accepted 25.07.2023

Implementation of arbitrary bitness permutations based on combined cascades of structural units

Oleksand Teslenko, Maksym Bondarchuk

The most crucial aspects of permutations are their speed and ease of implementation. This article examines the implementation of arbitrary bitness permutations in computer engineering using a particular class of combination structures with linear complexity, namely, combined cascades of structural units. The reflection formed by this linear structure is identical to that of the corresponding Mealy finite state machine, which allows for the exploration of the properties of structural units and the cascade in the context of the theory of digital automata. The purpose of this permutation is to convert large volumes of data using hardware or software quickly and simply that can be used in various research fields. The paper investigates the bijectivity and equivalence of the reflection and presents an algorithm for constructing finite-state machines for both direct and inverted permutations, along with examples of state and output table construction. The article also provides examples of hardware implementation using field-programmable gate arrays and estimates the size of state and output tables for software implementation. The theoretical speed of bijective reflection transformations is calculated for both field-programmable gate arrays and software implementation, and the paper compares the speed of software implementations based on combined and one-dimensional cascades of constructive units. The practical verification of processing speed is made with software implementation. Finally, the article proposes areas of application for this arbitrary bitness permutation

permutation functions, Mealy machine, bijective reflection, field-programmable gate arrays, cascades of structural units
63-77
Teslenko, O., & Bondarchuk, M. (2023). Implementation of arbitrary bitness permutations based on combined cascades of structural units. Information Technologies and Computer Engineering, 20(2), 63-77. https://doi.org/10.31649/1999-9941-2023-57-2-63-77

References

[1] Hazewinkel, M. (Ed.). (2000). Encyclopedia of mathematics (Vol. 2). Berlin: Springer. doi: 10.1007/978-94-015-1279-4.

[2] Peng, L. (2019). The Generation of (n,n(n-1),n-1) Permutation group codes for communication systems. IEEE Transactions on Communications, 67(7), 4535-4549. doi: 10.1109/TCOMM.2019.2902149.

[3] Boss, E., Grosso, V., Güneysu, T., Leander, G., Moradi, A., & Schneider, T. (2017). Strong 8-bit sboxes with ecient masking in hardware. Journal of Cryptographic Engineering, 7, 149-165. doi: 10.1007/s13389-017-0156-7.

[4] Fomin, D., & Trifonov, D. (2019). On hardware implementation of one class of byte substitutions. Applied Discrete Mathematics. Appendix, 12, 134-137. doi: 10.17223/2226308X/12/39.

[5] Oliinikov, R., Gorbenko, I., Kazimirov, O., Ruzhentsev, V., & Gorbenko, Yu. (2015). Principles of construction and main properties of the new national standard of block encryption of Ukraine. Protection of information, 17(2), 142-157. doi: 10.18372/2410-7840.17.8789.

[6] National Institute of Standards and Technology. (2001). Advanced Encryption Standard (AES). doi: 10.6028/NIST.FIPS.197.

[7] Tarasenko, V., Teslenko, O., & Yanovska, O. (2007). Problems of hardware implementation of substitutions. UNDIZ Scientific Notes, 2, 52-58,

[8] Tarasenko, V., Teslenko, O., & Yanovska, O. (2010). Properties of complete substitutions realized by the simplest unidirectional regular one-dimensional cascade of constructive modules. Radioelectronic and Computer Systems, 6, 123-128.

[9] Tarasenko, V., Teslenko, O., & Yanovska, O. (2012). Possibilities of the simplest bidirectional regular one-dimensional cascades of constructive modules regarding the implementation of various complete substitutions. Radioelectronic and Computer Systems, 7, 147-153.

[10] Teslenko, O., & Bondarchuk, M. (2020). Implementation of arbitrary bitness permutations in one of the classes of linear structures. Herald of Advanced Information Technology, 3(1), 406-417. doi: 10.15276/hait01.2020.7.

[11] Teslenko, O., & Bondarchuk, M. (2022). Using implementations of substitutions of arbitrary bitness for cryptographic transformations. Scientific News of KPI, 1-2. doi: 10.20535/kpisn.2022.12.263225.

[12] Glushkov, V. (1967). Synthesis of digital automata. Kyiv: Publishing House of the Academy of Sciences of the Ukrainian SSR.

[13] Karandashov, M. (2014). Investigation of bijective automatic subtractions displayed on a ring modulo 2k. Computer Sciences and Information Technologies, 2, 148-152.

[14] Gill, A. (1962). Introduction to the theory of finite-state machines. New York: McGraw-Hill.

[15] Bondarchuk, M. (n.d.). Algorithm for generating a table of transitions as a table of a connected numbered unidirectional graph. Retrieved from https://github.com/MaksymBondarchuk/Article-3materials/blob/master/ConnectedGraphStateAlgorithm.cs.

[16] Bondarchuk, M. (n.d.). Algorithm for generating a table of outputs with unique values in each row. Retrieved from https://github.com/MaksymBondarchuk/Article-3materials/blob/master/RandomNonRepeatingRowsOutputAlgorithm.cs.

[17] Frobenius G., & Stickelberger, L. (1879). Ueber Gruppen von vertauschbaren Elementen. Journal für die Reine und Angewandte Mathematik, 86, 217-262. doi: 10.1515/crll.1879.86.217.

[18] Bondarchuk, M. (n.d.). Algorithm for generating inverse automata. Retrieved from https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/ReversedMachine.cs .

[19] Summary of Virtex-6 FPGA Features. Virtex-6 Family Overview. XILINX DS150 (v2.5). (n.d.). Retrieved from https://www.xilinx.com/support/documentation/data_sheets/ds150.pdf.

[20] Sequence A001349 – Number of connected graphs with n nodes. (n.d.). Retrieved from http://oeis.org/A001349.

[21] Van Lint, J., & Wilson, R. (1992). A course in combinatorics. Cambridge University Press.

[22] Sequence A001187 – Number of connected labeled graphs with n nodes. (n.d.). Retrieved from http://oeis.org/A001187.

[23] SiSoftware Official Live Ranker "SiSoftware Zone". (n.d.). Retrieved from https://ranker.sisoftware.co.uk/top_device_all.php?q=d6ebdb.

[24] Memory Performance in a Nutshell. (n.d.). Retrieved from https://www.intel.com/content/www/us/en/developer/articles/technical/memory-performance-in-anutshell.html.

[25] RAM UserBenchmarks – 115 Memory Kits Compared. (n.d.). Retrieved from https://ram.userbenchmark.com.

[26] SSD UserBenchmarks – 1071 Solid State Drives Compared. (n.d.). Retrieved from https://ssd.userbenchmark.com.

[27] HDD UserBenchmarks – 1015 Hard Drives Compared. (n.d.). Retrieved from https://hdd.userbenchmark.com.

[28] Yanovska, O., Tarasenko, V., & Teslenko, O. (2013). Using direct and inverse substitutions of arbitrary bit rate to improve the efficiency of existing data compression tools. In Abstracts of reports of the Fourth International Scientific and Practical Conference "Methods and means of coding, protection and compression of information (pp. 223-226), Vinnytsia: VNTU.

[29] Tarasenko, V., Teslenko, O., & Yanovska, O. (2010). Analysis of the influence of substitutions on the decomposition of Boolean functions. Bulletin of the University "Ukraine", 8, 40-47.

[30] Klyatchenko, Ya., Tarasenko, V., Teslenko, O., & Yanovska, O. (2011). Using substitutions for non-algorithmic implementation of encoders and decoders of interference-tolerant coding. In Modern Computer Systems and Networks: Development and Use (ACSN'2011) (pp. 191-193). Lviv: Lviv Polytechnic National University.

[31] Melnikova O., & Maslennikova, A. (2017). Substitutions for increasing the efficiency of software implementation of algorithms that use symbolic-digital representations. Mathematical and Computer Modeling, 15, 126-132.

[32] Abornev, A. (2014). Nonlinear substitutions on a vector space recursively generated over a Galois ring of characteristic 4. Applied Discrete Mathematics. Appendix, 7, 40-41.