IMPLEMENTATION OF ARBITRARY BITNESS PERMUTATIONS BASED ON COMBINED CASCADES OF STRUCTURAL UNITS
DOI:
https://doi.org/10.31649/1999-9941-2023-57-2-63-77Keywords:
permutation functions, Mealy machine, bijective reflection, field-programmable gate arrays, cascades of structural unitsAbstract
Abstract. 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.
References
M. Hazewinkel, Encyclopedia of Mathematics. Springer Science+Business Media B. V. Kluwer Academic Publishers, 2000, doi: 10.1007/978-94-015-1279-4.
L. Peng, “The Generation of (n,n(n-1),n-1) Permutation Group Codes for Communication Systems”, IEEE Transactions on Communications, vol. 67, no. 7, pp. 4535-4549, 2019, doi: 10.1109/TCOMM.2019.2902149.
E. Boss, V. Grosso, T. Güneysu, G. Leander, A. Moradi and T. Schneider, “Strong 8-bit sboxes with ecient masking in hardware”, Journal of Cryptographic Engineering. no. 7, pp. 149-165, doi: 10.1007/s13389-017-0156-7.
Д. Фомин и Д. Трифонов, «Об аппаратной реализации одного класса байтовых подстановок», Прикладная дискретная математика. Приложение, № 12, с. 134–137, 2019, doi: 10.17223/2226308X/12/39.
Р. Олійников, І. Горбенко, О. Казимиров, В. Руженцев та Ю. Горбенко, «Принципи побудови і основні властивості нового національного стандарту блокового шифрування України», Захист інформації, т. 17, № 2, с. 142-157, 2015, doi: 10.18372/2410-7840.17.8789.
National Institute of Standards and Technology. (2001, Nov. 26). Advanced Encryption Standard (AES). [Online]. Available: https://doi.org/10.6028/NIST.FIPS.197.
В. Тарасенко, О. Тесленко та О. Яновська, «Проблеми апаратної реалізації підстановок», Наукові записки УНДІЗ, № 2, с 52-58, 2007.
В. Тарасенко, О. Тесленко та О. Яновська, «Властивості повних підстановок, які реалізуються найпростішим однонаправленим регулярним одновимірним каскадом конструктивних модулів», Радіоелектронні і комп’ютерні системи, № 6, с.123-128, 2010.
В. Тарасенко, О. Тесленко та О. Яновська, «Можливості найпростіших двонаправлених регуляр-них одновимірних каскадів конструктивних модулів щодо реалізації різних повних підстановок», Радіоелектронні і комп’ютерні системи, № 7, с. 147-153, 2012.
O. Teslenko and M. Bondarchuk, “Implementation of arbitrary bitness permutations in one of the classes of linear structures”, Herald of Advanced Information Technology, vol. 3, no. 1, pp. 406-417, 2020, doi: 10.15276/hait01.2020.7.
О. Тесленко та М. Бондарчук, «Використання реалізацій підстановок довільної розрядності для криптографічних перетворень», Наукові вісті КПІ, № 1-2, 2022, doi: 10.20535/kpisn.2022.1-2.263225.
В. Глушков, Синтез цифровых автоматов. Київ, 1967.
М. Карандашов, «Исследование биективных автоматных отображений на кольце вычетов по модулю 2k», Компьютерные науки и информационные технологии, с. 148-152, 2014.
A. Gill, Introduction to the theory of finite-state machines. McGraw-Hill electronic sciences series, 1962.
М. Бондарчук «Алгоритм генерування таблиці переходів як таблиці зв’язаного пронумерованого однонаправленого графа». [Електронний ресурс]. Доступно: https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/ConnectedGraphStateAlgorithm.cs. Дата звернення: 10.04.2023.
М. Бондарчук «Алгоритм генерування таблиці виходів з унікальними значеннями в кожному рядку». [Електронний ресурс]. Доступно: https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/RandomNonRepeatingRowsOutputAlgorithm.cs. Дата звернення: 10.04.2023.
G. Frobenius and L. Stickelberger, “Ueber Gruppen von vertauschbaren Elementen”, Journal für die reine und angewandte Mathematik, 1879, doi: 10.1515/crll.1879.86.217.
М. Бондарчук «Алгоритм генерування обернених автоматів». [Електронний ресурс]. Доступно: https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/ReversedMachine.cs. Дата звернення: 10.04.2023.
Summary of Virtex-6 FPGA Features. Virtex-6 Family Overview. XILINX DS150 (v2.5). [Online]. Available: https://www.xilinx.com/support/documentation/data_sheets/ds150.pdf. Accessed on: 13.04.2023.
Sequence A001349 – Number of connected graphs with n nodes. The On-Line Encyclopedia of Integer Sequences® (OEIS®). [Online]. Available: http://oeis.org/A001349. Accessed on: 13.04.2023.
J. van Lint and R. Wilson, A Course in Combinatorics. Cambridge University Press, 1992.
Sequence A001187 – Number of connected labeled graphs with n nodes. The On-Line Encyclopedia of Integer Sequences® (OEIS®). [Online]. Available: http://oeis.org/A001187. Accessed on: 13.04.2023.
SiSoftware Official Live Ranker "SiSoftware Zone". [Online]. Available: https://ranker.sisoftware.co.uk/top_device_all.php?q=d6ebdb. Accessed on: 03.01.2023.
Memory Performance in a Nutshell. [Online]. Available: https://www.intel.com/content/www/us/en/developer/articles/technical/memory-performance-in-a-nutshell.html. Accessed on: 10.04.2023.
RAM UserBenchmarks – 115 Memory Kits Compared. [Online]. Available: https://ram.userbenchmark.com. Accessed on: 10.04.2023.
SSD UserBenchmarks – 1071 Solid State Drives Compared. [Online]. Available: https://ssd.userbenchmark.com. Accessed on: 10.04.2023.
HDD UserBenchmarks – 1015 Hard Drives Compared. [Online]. Available: https://hdd.userbenchmark.com. Accessed on: 10.04.2023.
О. Яновська, В. Тарасенко та О. Тесленко, «Використання прямих та обернених підстановок до-вільної розрядності для підвищення ефективності існуючих засобів ущільнення даних», Тези до-повідей Четвертої Міжнародної науково-практичної конференції «Методи та засоби кодування, захисту й ущільнення інформації, с. 223-226, Вінниця, 2013.
В. Тарасенко, О. Тесленко та О. Яновська, «Аналіз впливу підстановок на декомпозицію булевих функцій», Вісник університету «Україна», № 8, с. 40-47, 2010.
Я. Клятченко, В. Тарасенко, О. Тесленко та О. Яновська, «Використання підстановок для неал-горитмічної реалізації кодерів та декодерів завадостійкого кодування», Сучасні комп’ютерні си-стеми та мережі: розробка та використання (ACSN’2011), с.191-193, Львів, 2011.
О. Мельникова та А. Маслєннікова, «Підстановки для підвищення ефективності програмної реа-лізації алгоритмів, які використовують знаково-цифрові представлення», Математичне та комп’ютерне моделювання, № 15, с. 126-132, Харків, 2017.
А. Аборнев, «Нелинейные подстановки на векторном пространстве, рекурсивно-порождённые над кольцом Галуа характеристики 4», Прикладная дискретная математика. Приложение, № 7, с. 40–41, 2014.
M. Hazewinkel, Encyclopedia of Mathematics. Springer Science+Business Media B. V. Kluwer Academic Publishers, 2000, doi: 10.1007/978-94-015-1279-4.
L. Peng, “The Generation of (n,n(n-1),n-1) Permutation Group Codes for Communication Systems”, IEEE Transactions on Communications, vol. 67, no. 7, pp. 4535-4549, 2019, doi: 10.1109/TCOMM.2019.2902149.
E. Boss, V. Grosso, T. Güneysu, G. Leander, A. Moradi and T. Schneider, “Strong 8-bit sboxes with ecient masking in hardware”, Journal of Cryptographic Engineering, no. 7, pp. 149-165, doi: 10.1007/s13389-017-0156-7.
D. Fomin and D. Trifonov, “Ob aparatnoy realisazii odnogo klassa baytovyh podstanovok”. [About hardware implementation of one class of byte permutations]. Prikladnaya diskretnaya matematika, Appendix 12, pp. 134-137, 2019, doi: 10.17223/2226308X/12/39 (in Russian).
R. Oliynykov, R. Gorbenko, I. Gorbenko, O. Kazymyrov, Y. Ruzhevcev and Y. Gorbenko, “Pryntsypy pobudovy i osnovni vlastyvosti novoho natsional’noho standartu blokovoho shyfruvannya ukrayiny” [Construction principles and basic properties of Ukraine’s new national block cypher encryption standard]. Zakhyst informatsiyi, vol. 2, pp. 142-157, 2015, doi: 10.18372/2410-7840.17.8789 (in Ukrainian).
National Institute of Standards and Technology. (2001, Nov. 26). Advanced Encryption Standard (AES). [Online]. Available: https://doi.org/10.6028/NIST.FIPS.197.
V. Tarasenko, O. Teslenko and O. Yanovska, “Problemy aparatnoi realisacii pidstanovok”. [Problems of hardware implementation of permutations]. Naykovi zapysky UNDIZ, no. 2, pp. 52-58, 2007 (in Ukrainian).
V. Tarasenko, O. Teslenko and O. Yanovska, “Vlastyvosti povnykh pidstanovok, yaki realizuyut’sya nayprostishym odnonapravlenym rehulyarnym OKKM”. [Properties of complete permutations implemented by the simplest unidirectional regular OCSU]. Radioelektronni i komp’yuterni systemy, no. 6, pp. 123-128, 2010 (in Ukrainian).
V. Tarasenko, O. Teslenko and O. Yanovska, “Mozhlyvosti naiprostishym dvonapravlenyh reguliarnyh odnovymirnyh kaskadiv konstruktyvnyh moduliv schodo realizacii riznyh povnyh pidstanovok”. [Features of the simplest bidirectional regular one-dimensional cascades of structural units for the implementation of various complete permutations]. Radioelektronni i kompyuterni systemy, no. 7 (59), pp. 147-153, 2012 (in Ukrainian).
O. Teslenko and M. Bondarchuk, “Implementation of arbitrary bitness permutations in one of the classes of linear structures”, Herald of Advanced Information Technology, vol. 3, no. 1, pp. 406-417, 2020, doi: 10.15276/hait01.2020.7.
O. Teslenko and M. Bondarchuk, “Use of implementations of arbitrary bitness permutations for cryptographic transformations”, KPI Science News, no. 1-2, 2022, doi: 10.20535/kpisn.2022.1-2.263225.
V. Glushkov, “Syntes cyfrovyh avtomatov”. [Synthesis of Digital Automata]. Kyiv, 1967 (in Russian).
M. Karandashov, “Issledovanie biektivnykh avtomatnykh otobrazhenii na kol’tse vychetov po moduliu 2k”, [Research bijective automaton mappings on the ring of residues modulo 2k]. Computer Science and Information Technologies, pp. 148-152, 2014 (in Russian).
A. Gill, Introduction to the theory of finite-state machines. McGraw-Hill electronic sciences series, 1962.
M. Bondarchuk “Connected graph state matrix algorithm”. [Online]. Available: https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/ConnectedGraphStateAlgorithm.cs. Accessed on: 10.04.2023.
M. Bondarchuk “Random non-repeating rows output matrix algorithm”[Online]. Available: https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/RandomNonRepeatingRowsOutputAlgorithm.cs. Accessed on: 10.04.2023.
G. Frobenius and L. Stickelberger, “Ueber Gruppen von vertauschbaren Elementen”. [“About groups of interchangeable elements”], Journal for Pure and Applied Mathematics, 1879, doi: 10.1515/crll.1879.86.217 (in German).
M. Bondarchuk “Reversed machine algorithm”. [Online]. Available: https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/ReversedMachine.cs. Accessed on: 10.04.2023.
Summary of Virtex-6 FPGA Features. Virtex-6 Family Overview. XILINX DS150 (v2.5). [Online]. Available: https://www.xilinx.com/support/documentation/data_sheets/ds150.pdf. Accessed on: 13.04.2023.
Sequence A001349 – Number of connected graphs with n nodes. The On-Line Encyclopedia of Integer Sequences® (OEIS®). [Online]. Available: http://oeis.org/A001349. Accessed on: 13.04.2023.
J. van Lint and R. Wilson, A Course in Combinatorics. Cambridge University Press, 1992.
Sequence A001187 – Number of connected labeled graphs with n nodes. The On-Line Encyclopedia of Integer Sequences® (OEIS®). [Online]. Available: http://oeis.org/A001187. Accessed on: 13.04.2023.
SiSoftware Official Live Ranker "SiSoftware Zone". [Online]. Available: https://ranker.sisoftware.co.uk/top_device_all.php?q=d6ebdb. Accessed on: 03.01.2023.
Memory Performance in a Nutshell. [Online]. Available: https://www.intel.com/content/www/us/en/developer/articles/technical/memory-performance-in-a-nutshell.html. Accessed on: 10.04.2023.
RAM UserBenchmarks – 115 Memory Kits Compared. [Online]. Available: https://ram.userbenchmark.com. Accessed on: 10.04.2023.
SSD UserBenchmarks – 1071 Solid State Drives Compared. [Online]. Available: https://ssd.userbenchmark.com. Accessed on: 10.04.2023.
HDD UserBenchmarks – 1015 Hard Drives Compared. [Online]. Available: https://hdd.userbenchmark.com. Accessed on: 10.04.2023.
V. Tarasenko, O. Teslenko and O. Yanovska, “Vykorystannya pryamykh ta obernenykh pidstanovok dovilʹnoyi rozryadnosti dlya pidvyshchennya efektyvnosti isnuyuchykh zasobiv ushchilʹnennya danykh”. [The use of direct and inverse arbitrary bit permutations to improve the performance of existing data comperssors]. Fourth International Scientific and Practical Conference “Metody ta zasoby koduvannya, zakhystu y ushchil’nennya informatsiyi”, Vinnytsia, Ukraine, pp. 223-226, 2013 (in Ukrainian).
V. Tarasenko, O. Teslenko and O. Yanovska, “Analiz vplyvu pidstanovok na dekompozytsiyu bulevykh funktsiy”. [Analysis of the effect of permutations on the decomposition of boolean functions]. Herald of University “Ukrayina” Informatyka, obchyslyuval’na tekhnika ta kibernetyka, no. 8, pp. 40-47, 2010 (in Ukrainian).
V. Tarasenko, O. Teslenko and O. Yanovska, “Vykorystannya pidstanovok dlya nealhorytmichnoyi realizatsiyi koderiv ta dekoderiv zavadostiykoho koduvannya” [Use of permutations for non-algorithmic implementation of encoders and decoders of fault-tolerant coding]. International Scientific Conference «Suchasni komp’yuterni systemy ta merezhi: rozrobka ta vykorystannya», L’viv, Ukraine, pp. 191-193, 2011 (in Ukrainian).
O. Mel’nykova and A. Maslyennikova, “Pidstanovky dlya pidvyshchennya efektyvnosti prohramnoyi realizatsiyi alhorytmiv, yaki vykorystovuyut’ znakovo-tsyfrovi predstavlennya”. [Permutations for increasing the efficiency of software implementation of algorithms that use character-to-digital representations]. “Tekhnichni nauky” Series, Kharkiv, Ukraine, vol. 15, pp. 126-132, 2017 (in Ukrainian).
A. Abornev, “Nelineynyye podstanovki na vektornom prostranstve, rekursivno-porozhdonnyye nad kol’tsom Galua kharakteristiki 4” [Nonlinear permutations on a recursively generated vector space over a Galois ring of characteristic 4], Prikladnaya diskretnaya matematika, vol. 7, pp. 40-41, 2014 (in Russian).
Downloads
-
PDF (Українська)
Downloads: 65
