Scientific Journal

Herald of Advanced Information Technology

IMPLEMENTATION OF ARBITRARY BITNESS PERMUTATIONS IN ONE OF THE CLASSES OF LINEAR STRUCTURES
Abstract:
Speed of transformation and simplicity of implementation are one of the key contributors in permutation researches. The paper reviews the implementation of arbitrary bitness permutation in the field of computer engineering on one of the classes of combination structures of linear complexity from the number of variables – one-dimensional cascades of structural units. The fact that the reflection formed by the specified linear structure is completely the same as the reflection of the corresponding Mealy finite state machine as a prototype of the structural module of the cascade is used. This allowed us to explore the properties of structural units and the cascade as a whole in the context of the concepts of the theory of digital automata. The implementation of arbitrary bitness permutations is based on usage of the connected graphs for state table and on usage of unique combinations without repeats for each row of output table. The purpose of this permutation is to convert large volumes of data in fast and simple way using hardware or software with the ability to be used in multiple areas of researches. The study of providing the bijectivity of the reflection and the equivalence analysis of permutations was performed. The algorithm of construction of finite-state machines for implementation of direct and inverted permutations is shown, as well as examples of state and output tables construction. Examples of hardware implementation using field-programmable gate arrays are given. The size of state and output tables for the software implementation is estimated. The number of unique bijective reflections and amount of key information for the investigated permutation in cryptographic transformations has been estimated. The theoretical speed of transformations of the bijective reflection is estimated for both field-programmable gate arrays and software implementation according to the modern indicators of types of computing devices memory speed. The practical verification of processing speed is made with software implementation. Areas of application of the investigated arbitrary bitness permutation are proposed.
Authors:
Keywords
DOI
10.15276/hait01.2020.7
References
  1. Hazewinkel, Michiel. (2000). “Permutation”, Encyclopedia of Mathematics, Springer Science+Business Media B. V. Kluwer Academic Publishers. ISBN 9789048153787. DOI 10.1007/978-94-015-1279-4.
  2. Peng, Li. (2019). “The Generation of (n,n(n−1),n−1) Permutation Group Codes for Communication Systems”, Communications IEEE Transactions on, Vol. 67, No. 7, pp. 4535-4549. DOI 10.1109/TCOMM.2019.2902149.
  3. Boss, E., Grosso, V. & Guneysu, T. (2017). “Strong 8-bit sboxes with ecient masking in hardware”, J. Cryptographic Engineering. No. 7(2), pp.149-165. DOI 10.1007/s13389-017-0156-7.
  4. Fomin, D. B. & Trifonov, D. B. (2019). “Ob aparatnoy realisazii odnogo klassa baytovyh podstanovok”. [About hardware implementation of one class of byte permutations]. Prikladnaya diskretnaya matematika, Appendix 12, pp. 134-137 (in Russian).
  5. Oliynykov, R., Gorbenko, R., Gorbenko, I., Kazymyrov, O., Ruzhevcev, Y. & Gorbenko Y. (April-June 2015). “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 (in Ukrainian).
  6. (November 2001). “Advanced Encryp-tion Standard (AES)”. (PDF). Federal Information Processing Standards. DOI 10.6028/NIST.FIPS.197.
  7. Tarasenko, V. P., Teslenko, O. K. & Yanovska, O. Y. (2007). “Problemy aparatnoi realisacii pidstanovok”. [Problems of hardware implementation of permutations]. Naykovi zapysky UNDIZ, No. 2, pp. 52-58 (in Ukrainian).
  8. Tarasenko, V. P., Teslenko, O. K. & Yanovska, O. Y. (2010). “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 (in Ukrainian).
  9. Tarasenko, V. P., Teslenko, O. K. & Yanovska, O. Y. (2012). “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 (in Ukrainian).
  10. Glushkov, V. M. (1967). “Syntes cyfrovyh avtomatov”. [Synthesis of Digital Automata]. Moskov, Russian Federation (in Russian).
  11. Karandashov, M. V. (2014). “Issledovanie biektivnykh avtomatnykh otobrazhenii na kol’tse vychetov po moduliu [Research bijective automaton mappings on the ring of residues modulo ]. Computer Science and Information Technologies: Proc. Intern. Sci. Conf. Saratov, Russian Federation, Publ. Center “Nauka”, pp. 148-152 (in Russian).
  12. Gill, A. (1962). “Introduction to the theory of finite-state machines”. New York, Toronto, Ontario, London, McGraw-Hill Book Co., Inc., 207 p. (Russ. ed.: “Gill A. Vvedenie v teoriiu konechnykh avtomatov”. Moscow, Russian Federation, Publ. Nauka, 272 p.) (in Russian).
  13. “Summary of Virtex-6 FPGA Features. Virtex-6 Family Overview”. XILINX DS150 (v2.5). [Electronic resource]. – Available at: https://www.xilinx.com/support/documentation/data_sheets/ds150.pdf. – Active link: 20.08.2015.
  14. “Sequence A001349 – Number of connected graphs with n nodes”. The On-Line Encyclopedia of Integer Sequences® (OEIS®). [Electronic resource]. – Available at: http://oeis.org/A001349. – Active link: 10.01.2020.
  15. J. H. van Lint & Wilson R. M. (1992). “A Course in Combinatorics”, Cambridge University Press.
  16. SiSoftware Official Live Ranker “SiSoftware Zone”. [Electronic resource]. – Available at: https://ranker.sisoftware.co.uk/top_device_all.php?q=d6ebdb. – Active link: 31.07.2014.
  17. Tarasenko, V. P., Teslenko, O. K. & Yanovska, O. Y. (2007). “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 (in Ukrainian).
  18. Tarasenko, V. P., Teslenko, O. K. & Yanovska, O. Y. (2010). “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 (in Ukrainian).
  19. Klyatchenko, Y. M., Teslenko, O. K. & Yanovska, O. Y. (2011), “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 (in Ukrainian).
  20. Mel’nykova, O. A. & Maslyennikova, A. O. (2017). “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, Vol. 15 Kharkiv National University of Radioelectronics, Kharkiv, Ukraine, pp. 126-132 (in Ukrainian).
  21. Abornev, A. V. (2014). “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 (in Russian)



Received   31.01.2020
Received after revision   17.02.2020
Accepted    20.02.2020
Published:
Last download:
5 July 2020

[ © KarelWintersky ] [ All articles ] [ All authors ]
[ © Odessa National Polytechnic University, 2018.]