Cryptographically Suitable Maximum Length Cellular Automata
Sourav Das and Dipanwita Roychowdhury
Efficient maximum length random sequence generators are very useful for cryptography. The linear Cellular Automata (CA), particularly maximum length CA, are well known for generating excellent random sequences. However, maximum length CA require a very large number of cycles to reach a state which is far from the initial states causing degradation of performance. Along with randomness, the non-linearity is also essential for cryptographic applications. However, till date, there is no known method of generating non-linear maximum length CA. This paper first devises an easy and efficient way to reach a state which is far from the initial state. It also discovers a series of linear time algorithms to explore the whole state space of maximum length CA. Then it devises a method to generate non-linear Maximal Length Cellular Automata. The efficient pseudo-random sequence generator can be combined with the non-linear generator to generate larger cryptographic primitives such as S-box.
Keywords: Pseudo-Random Number Generator, Non-linearity, Maximum Length Cellular Automata, Cryptography