Symmetric cryptosystems based on finite automata

Abstract

The security of information is an important aspect of communication, which always requires constant improvement to its cryptosystems. Modern designs come with high security and improved performance in real-time applications in response to the increased danger from hacking effort. Since finite automata are formal models of computing devices, cryptosystems based on them can be efficiently implemented at software and hardware levels. Several cryptosystems based on the Mealy and Rabin-Scott models of finite automata and cellular automata have been developed. Mealy model based cryptosystems have serious security vulnerabilities; while cellular automata based cryptosystems have serious technical realization difficulties. Although Domosi’s cryptosystems based on the Rabin -Scott model combines the simplicity and the security of the above cryptosystems, the backtracking drawbacks in the encryption algorithms affect the performance of the whole cryptosystem. In addition, the resistance against crypt attacks depends on the construction of large size automata and relatively large minimal and maximal block lengths of ciphertext. This results in producing much longer ciphertext than the given plaintext. The purpose of this study is to propose a modified version of Domosi’s cryptosystems, introducing a novel stream cipher based on nondeterministic finite automata, and construct a new block cipher based on parallel finite automata systems. This study develops and designs formal models of finite automata as keys for encryption and decryption, where it considers modified Domosi’s cryptosystems, nondeterministic finite automata based cryptosystems, cryptosystems based on parallel and sequential finite automata systems. The performance and security analysis is tested for the introduced cryptosystems. It is found that the time complexity of the modified encryption algorithm in the modified Domosi’s cryptosystem drastically reduces the exponential time to the linear time with at least the same level of security. Regarding a novel stream cipher based on nondeterministic automata, the analysis illustrates that the nondeterministic automata are irreversible automata and they can be used to reduce the size of ciphertext blocks. Consequently, improving the security level as well as the performance. Moreover, the results show that a new block cipher has high security and throughput compared to the sequential counterpart. The research also shows that the cryptosystems can be implemented as an integrated component into large scale software and hardware.