РЕАЛІЗАЦІЯ ПІДСТАНОВОК ДОВІЛЬНОЇ РОЗРЯДНОСТІ НА БАЗІ КОМБІНОВАНИХ КАСКАДІВ КОНСТРУКТИВНИХ МОДУЛІВ
DOI:
https://doi.org/10.31649/1999-9941-2023-57-2-63-77Ключові слова:
функції підстановок, автомат Мілі, бієктивне відображення, програмовані логічні інтегральні схеми, каскади конструктивних модулівАнотація
Анотація. Швидкість перетворення і простота реалізації є одними з ключових факторів підстановок. У статті розглянуто реалізацію підстановки довільної розрядності в області комп’ютерної інженерії на одному із класів комбінаційних структур лінійної складності від кількості змінних – комбінованих каскадів конструктивних модулів. Використано той факт, що відображення, яке формує вказана лінійна структура, повністю збігається з відображенням відповідного скінченного автомата Мілі як прототипу конструктивного модуля каскаду. Це дозволило досліджувати властивості конструктивних модулів та каскаду в цілому у розрізі понять теорії цифрових автоматів. Реалізація підстановок довільної розрядності полягає у використанні зв’язаних пронумерованих однонаправлених автоматів для таблиці станів і використанні унікальних комбінацій без повторів для кожного рядку таблиці виходів. Метою реалізації даної підстановки є швидке перетворення даних великих об’ємів з можливістю застосування в кількох напрямках досліджень при простій реалізації на апаратному або програмному рівні. Виконано дослідження забезпечення бієктивності відображення та проведено аналіз еквівалентності відображень. Показано алгоритми формування автоматів для реалізації прямих та обернених підстановок, а також приклади формування таблиць переходів та виходів таких автоматів. Наведено приклади апаратної реалізації на програмованих логічних інтегральних схемах. Виконано оцінку об’єму таблиць переходів та виходів для апаратної та програмної реалізації. Виконано оцінку кількості унікальних бієктивних відображень. Проведено теоретичну оцінку швидкості бієктивних відображень при реалізації на програмованих логічних інтегральних схемах, а також при програмній реалізації згідно з сучасними показниками швидкості видів пам’яті обчислювальних пристроїв для кожного виду. Проведено порівняння швидкодії програмних реалізацій на базі комбінованого та одновимірного каскадів конструктивних модулів. Наведено експериментальну оцінку, а також проведено практичну перевірку швидкості перетворення за допомогою програмної реалізації. Запропоновано області застосування досліджених реалізацій підстановок довільної розрядності.
Посилання
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).
##submission.downloads##
-
PDF
Завантажень: 37
