Research And Application Of Cellular Automata On Cryptography

Cellular automata are a kind of discrete nonlinear dynamic systems, they are hard to be predicted or analysed, and it's evolution process can not be described with algebrical structures at least currently. Moreover, cellular automata have three main notable characteristics: high parallel processing architecture, local interaction and very simple rules. Thus, cellular automata are suitable to be used for designing cryptosystems and to be designed with VLSI.Firstly in this thesis, we outline some basic theoretical foundations and the history about cryptography. Then, we introduce the applied fields and development history of cellular automata, and particcularly the research history in cryptography. The main contents of this thesis include as follows:Toggle rules are sensitive to the initial configurations and irreversible. The number of toggle rules increases rapidly with the CA's neighborhood radius became larger, but the proportion of the toggle rules to the size of rule space deceases sharply. We have given a formula which can use to build toggle rules efficiently; it can calculate the toggle rule's serial number immediacily as the rule is toggle in its either bit.The iteration process of cellular automata is irreversible and very sensitive to the initial global state, very similar to the characteristics of one-way hash function in cryptography. This paper tries to make use of the cellular automata's sensitivity to the initial state called avalanche effect, by swiftly diffusing and confusing the plaintext to be hashed, a cellular automata based one-way hash function is proposed. Statistical analysis on simulation data shows that, this cellular automata based one-way hash function can successfully resist varieties of cryptanalysis attacks, and also it is scalable, high computationally efficient and easy to be implemented with hardware.A genetic algorithm is specially designed to search the rules with avalanche effects in left and right toggle rule space, this kind of rules are sensitive to the initial configuration and reversible as well. A large quantity of simulation data indicates that, the toggle rules found by this genetical algorithm have good avalanche effects and diffusibility.