Прилог кон примена на квазигрупите во теоријата на кодирање и криптографијата

Abstract

In this thesis we research some applications of quasigroups in the coding theory and the cryptography. We consider Random Codes Based on Quasigroups (RCBQ) proposed by Danilo Gligoroski, Smile Markovski i Ljupco Kocarev. These codes are a combination of cryptographic algorithms and error-correcting codes and they have several parameters. We investigate the influence of the code parameters and the length of the messages on the code performance. From the experiments we conclude that the speed of the decoding process is one of the biggest problem for these codes. In order to improve the decoding speed, we define a new coding/decoding algorithm called Cut-Decoding algorithm. The modified decoding process is 4.5 times faster than the original one for code (72, 288), for quasigroups of order 16. Also, we propose several methods for reducing the unsuccessful decodings. In such a way we obtain better values for packet-error and bit-error probabilities. In this thesis we investigate the performances of the random codes based on quasigroups when quasigroups of order 4 and order 256 are used in the coding/decoding processes. We consider an application of these codes for decoding images transmitted through a binary symmetric channel and compare the results obtained using the standard algorithm, Cut-Decoding algorithm and Reed-Solomon codes. For obtaining a faster decoding process we define another coding/decoding algorithm, called 4-Sets-Cut-Decoding algorithm. Also, for improving the packeterror and bit-error probabilities we define several methods for generating reduced decoding candidate sets. We analyze the performances of different decoding algorithms of RCBQ (the standard, Cut-Decoding and 4-Sets-Cut-Decoding algorithms) for a code with rate R = 1/8 and we consider the application of the methods for reducing the number of unsuccessful decodings in the new proposed algorithms. We investigate performances of RCBQ with 4-Sets-Cut-Decoding algorithm#3 for coding/decoding images transmitted through a binary symmetric channel and we compare these results with suitable results obtained with Reed- Solomon codes. We derive a theoretical upper bound for the packet-error probability obtained by the new algorithms and approximate formulas for cardinality of the reduced decoding candidate sets. With the derived formulas we prove that with the new algorithms we have improved the performances of these codes. The first idea for quasigroup string transformation based on parastrophes is given by Aleksandar Krapez. In this thesis, we propose a modification of this transformation, called parastrophic quasigroup (PE) transformation and consider its cryptographic properties. Using this transformation we classify the quasigroups of order 4 into three classes: 1) parastrophic-fractal; 2) fractal parastrophic-nonfractal; and 3) non-fractal quasigroups. We investigate the algebraic properties of parastrophic fractal quasigroups of order 4 and give a mathematical model of parastrophic fractality using some identities. Also, we find a number of different parastrophes of each quasigroup of order 4 and divide the set of all quasigroups of order 4 in four classes. Using this transformation we increase the number of quasigroups of order 4 which are suitable to design cryptographic primitives. We prove an important cryptographic property of PE-transformation. Namely, if PE- transformation is used as encryption function then after n applications of it on arbitrary message the distribution of l-tuples (l = 1; 2; :::; n) is uniform. This property implies the resistance to statistical kind of attack.