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.