Research On Cellular Automata Theory And Its Application In Cryptography

With the rapid development of information technology, information security has become increasingly important, and brought huge challenges to scientific field. As the kernel of information security, cryptography is featured by its sensitivity and particularity. In view of this, each country has been looking for self-dependent techniques of the cryptography to guarantee their benefits and gains. Among various techniques, cellular automaton is considered as the most important one. This is because cellular automaton posses a lot of inherent characteristics, such as simple regular structure, local interaction, massive parallelism and complex behavior which make it a good candidate to design cryptosystem.Based on a review of the cryptography with cellular automata at home and abroad, this paper discusses how to design symmetric ciphers using reversible and irreversible cellular automata. The main contributes of this paper are as follows:(1) The concept of cross composition cellular automata and random composition cellular automata is proposed. After analyzing some basic properties of the composite system, two block ciphers are constructed based on composition cellular automata by means of inverse iteration. The new encryption systems effectively solve the problem of one-way error diffusion in a single cellular automaton system and acquire large key space with small rule radius.(2) By proposing a coupling parameter, we design a new model of coupling cellular automata and analyze the time-space evolution of coupling cellular automata. As there are some disadvantages of the cipher based on simple coupling cellular automata, we present a new encryption algorithm based on multi-coupling cellular automata. The method of coupling many cells can enhance the interaction between two cellular automata, and make the error diffuse quickly. Moreover, we provide a parallel encryption model based on coupled cellular automata, which not only improves the speed of encryption and decryption, but also has much higher real-time performance and more suitability.(3) Considering that there are few one-dimensional reversible cellular automata and there is no effective procedure for finding high-dimensional reversible cellular automata, a method of constructing reversible cellular automata is proposed. The reversible cellular automata are featured by their no information loss and parallel information processing, so it is suitable for us to design cipher. Instead of using the whole rule space as the key space, the new algorithm introduces a parameterλto partition the rule space and proves that rules withλ=0.5 are becoming to encrypt. Compared with the general irreversible toggle cellular automata cryptosystem, the proposed method greatly improves the speed of encryption and has large key space. Furthermore, there is no data inflation in our method, which makes it suitable for multimedia encryption such as image, video, speech.(4) According to some intrinsic features of image such as bulk data capacity, high data redundancy and strong correlation among pixels, a multiple-image encryption based on two-dimensional reversible cellular automata is presented. The algorithm permits images to be managed in a two-dimensional way, rather than treating them as a one-dimensional data stream, which greatly improves the efficiency and velocity of the algorithm. As a circular-chain iterating mode is adopted during the encryption, the statistical information for each plain image is dissipated not only into the long-rang of its own cipher image, but also into the other cipher images in the group. This makes the relationship between the plain images and cipher images as complex as possible. Simulation results show that the main advantages of the proposed algorithm compared with other algorithms are as follows:Firstly, there is no need to decorrelate the strongly correlated images. Secondly, the pixel values and order of the images don't change.