# Introduction ased on applications, such as data storing, transferring and processing, the information can be threatened in several way. In each threat, dependent to the threat agent, the information may be changed and lose their credibility, or be stolen and lose their confidentiality, only. The cryptography has been considered as an approach to protecting information, in both cases, and in different conditions, can help to preserving data credibility and confidentiality. Generally, this approach includes transforming a plain-text into a ciphered-text. In this way, a determined function and a specific key are used, and the common purpose is establishing a secure communication between a sender A and a receiver B over an insecure communication channel [1]. Regarding key type viewpoint, the encryption algorithms are divided into two broad classes: symmetric and asymmetric algorithms. In the first class, both a communication parties use a common secret key for both encryption and decryption process; whereas in second ones, each of communication parties has its private secret key and also a public key. Asymmetric-key algorithms provide stronger securities compared to symmetric ones; however, because of massive numeral computation for increasing the security of these algorithms, they have lower speeds compared to the first class algorithms [2]. The symmetric algorithms are divided into Block ciphering and Stream ciphering algorithms, themselves. In both ones, using an efficient tool for adding the randomness in the key or ciphered text is considered, as a basis. So, the Cellular Automata (CA) as a complex parallel processing model has been used in both these mentioned algorithms. The CA can be used for increasing encryption and decryption security and speed, via its parallel operation nature and its pseudorandom output [3,4]. However, the main problem in using CA for cryptography includes selecting a rule set for cells that provides security requirements, optimally. In this paper, using a Learning Cellular Automata (LCA), as an extended model of CA, has been considered for selecting an optimal rule set for a key generator based on CA that can be used in stream ciphering. For the purpose of this paper, it has been organized as follows: section 2 introduces stream ciphering. In section 3, key generating will be focused and after introducing CA as a common key generator, using it for this purpose will be reviewed. Also, the Learning Cellular Automata (LCA) as the basis of proposed model will be introduced. Then, section 4 presents the proposed model for identifying optimal rules that must be used in CA-based random number generator. Section 5 has been designated for reporting experiments results and finally, section 6 includes conclusion. # II. # Stream ciphering In a block ciphering system, the plain text is divided into several blocks with a specific size, and each block is transformed to a ciphered block, independently. However, the stream ciphering process transforms each plain text bit to a cipher bit, per a time instance [5]. A stream ciphering system includes a pseudo random bit sequence generator and a function box. The generator produces a bit stream that is considered as a key sequence and is combined with the plain text in a bitwise manner, and generates a cipher bit. This combination is done by a function box which often is an XOR-operator. The performance of an encryption system depends on randomness degree of key stream, used in encryption. So the key generator plays an important role in this way. Among different key generators, the random number generators based on Linear Feedback Shift Register (LFSR) and Cellular Automata (CA) have been known as prevalent ones. An LFSR includes a shift register together with a set of XOR operators which combine the feedbacks extracted from the register cells. This model is defined by an n-degree polynomial which specifies the operators and feedbacks arrangements [2]. A sample of these generators has been shown in fig. 1. Fig. 1: A typical sample of LFSR In some systems, a combination of LFSRs has been utilized for increasing the randomness of generated sequence. This requires applying nonlinear combination functions. The researches have indicated that utilizing linear CA provides an operation similar to LFSR [15,16,17,18]. In the other word, CA structures can be used in key producing, as a replacement for LFSR. Some experiments results have shown that CA is proper for producing random features in digital circuits and automatic control systems [17]. A desirable facet of CAs refers to independency between the sequence of generated bits and the states of neighbor cells. In this case, CA can be preferred compared to LFSR for stream ciphering. On the other hand, the main advantage of CA is that several generators designed as nonlinear combinations of LFSRs, when designing with CA, preserve linearity [20]. These mentioned advantages have been considered as the reasons to applying the CA as a Pseudo-Random sequence generator (PRSG). Really, the CA has an outstanding role in this area and is considered as an important tool for generating random sequences [3,6,7,8]. # III. # Key generation a) Cellular Automata (CA) The concept of CA was introduced by Von Neumann and Ulam at 1950s, for the first time, and was considered by Wolfram, more extensively. The simple structure of CA has attracted the researchers in several different areas, such as implementing the computing tools and modeling the natural systems [9]. Each CA includes a set of simple elements called cells that each has a finite set of states, and interacts with its adjacent cells (neighborhood), locally. The next state of each specific cell is determined with a rule that is a function of current states of that cell and its neighbors. Fig. 2 shows some samples of neighborhood patterns [10]. Regarding a k-cell neighborhood, P=2k neighborhood patterns and thus 2P possible rules can be defined. Fig. 3 shows schematic diagrams for some possible rules operations, assuming k=3. What is important in applying CA as a PRSG is selecting the rule set governing the cells such that the generated sequence provides a desirable level of randomness. Wolfram, for the first time, applied an uniform CA with k=3 neighborhood for encryption, at 1986. He used Rule 30 for all cells. His proposed model operated as a pseudo-random key stream generator for using in stream ciphering [18,21]. Afterward, other researchers showed that when using non-uniform CA, a higher level randomness is provided. For example, Habutsu et al. and Gutowitz and Nandi et al. used nonuniform CA with Rule 90 and Rule 150 for mentioned purpose and indicated that their generated key stream have a better quality than Wolfram's one [22,23]. Tomassini and Perrenoud proposed a linear CA with k=3 and the rule set {90,105,150,165} [24]. They used an evolutionary method called cell programming for searching optimal rules. This method is an evolutionary computational approach similar to diffusion model in parallel genetic algorithms. The entropy of generated sequence was used as a quality criterion for rules [24]. This paper has focused on using the learning capability of a Learning Cellular Automata for selecting a set of optimal rules for using in a CA-based PRSG. c) Learning Cellular Automata (LCA) The Learning Automata (LA) as another model of automata includes a finite automata which interacts with an environment. The automata have a finite set of actions that each can be selected with a specific selection probability. Such this model operates in two phases: Training phase and Testing phase. In the first one, some probabilities are assigned to automata actions, such that all of them sum to one. Then, in each step, the automata select an action randomly and based on probabilities. The environment receives the selected action and responses to it with a desirability or undesirability of selected action, by sending back a response to it. Then, by considering the received response, the automata reward the selected action or penalize it. Rewarding an action implies an increase in action selection probability for next steps and penalizing it includes decreasing this probability. The training phase continues until the probability of a special action approaches to one and thus is determined as optimal action [12,13]. A sample of LA interacting with an environment has been shown in fig. 5 [14]. Fig. 5: An LA interacting with an environment A set of LAs that in addition to interacting with the environment, have local interactions between themselves, form a Learning Cellular Automata (LCA). In such this structure, the desirability of selected action by each learning cell, is determined based on the states or selected actions by that cell and its neighbors. Updating all LAs is performed simultaneously; thus, the LCA has a parallel nature. A sample LCA has been shown in fig. 6, in which, each cell LAi selects an action denoted by Ai and the corresponding environment return a response denoted by Bi. # IV. The proposed model The proposed method in this paper focuses on finding a configuration of rules governing on the cells of a CA that operates as a PRSG. In this way, an LCA with two types of environment has been considered. Each cell of LCA interacts with a local environment and all cells have interactions with a global environment, simultaneously. The proposed method can be explained in two stages. In the first one, by considering a uniform CA with k-cell neighborhood, selecting M best rules among all possible rules is regarded. In order to do this, two empty vectors named best_rules and best_cnt are defined to hold the best rules indices and their correspond statistics. Then M different configurations are imposed to the CA, one by one. By imposing each configuration ci, as the initial state of the CA, during 2P stages (P=2K, in which, K is the size of neighborhood), all possible rules are assigned to the CA cells, one after another. By assigning each rule Rj to all cells of the CA, N sequences with the length l, are generated during the CA operation. Then, the entropy values are calculated for all sequences, using the method described in [11] and based on Eq. ( 4). ( )4 The max, min and average entropy values for each rule assigned to CA are stored in three vectors, separately. When the entropy values for all rules were calculated, the rules with maximum values in three mentioned vectors are selected. If these three rules are same, and not be found in best_rules vector, the rule is added to the mentioned vector and its correspond counter is set to one in best_cnt. If the rule exists in the best_rules, already, its counter is increased by one. This process is performed for M times and finally two mentioned vectors will contain best rules and the counters which indicate the number of times that each rule has been identified as the best rule. Among all best_rules members, m ones with top counter values are selected to be used for the next stage. This process has been shown in fig. 7 This stage includes an initial phase in which a probability value is assigned to each action, initially. Then, in the training phase, all cells of LCA select actions, simultaneously. The selected action by each cell is considered as its rule, and all cells will generate llength sequences with using that rules and through l operation step. The generated sequences by each cell and its neighbor cells (its r-1 left and right cells) are passed to the local environment and the entropy values will be calculated for these sequences. Then, by considering an r-cell neighborhood for evaluating the quality of generated sequences, each local environment compares the calculated entropy values and if this entropy is maximum value among all r entropy values, returns a response as zero or returns one, otherwise. Each learning cell rewards its selected action, if receive a zero as the local environment response; otherwise, it penalizes the selected action. After imposing rewards or penalties by all cells, all generated sequences are passed to the global environment. This environment calculates all entropy values and the max, min and mean values for them. These values are compared with their previous values and if an improvement is detected, a response as 0 will be passed back to each LA. In this case, each cell will impose a reward to its selected action. The training phase will be continue as described, until the actions probabilities in all cells reach a steady state. A flowchart describing each LA operation interacting with environments has been shown in fig. 9. # Experiments results For evaluating the proposed model, a CA with the size N=50 and a neighborhood size, k=3, was considered and by applying 100 different initial configurations, m=10 top rules among 256 possible rules were selected (based on l=100 bits length sequences). A bar diagram for best rules found during these 100 configuration imposing has been shown in fig. 10. The 10 selected rules were assigned as the actions of each cells in a LCA with N=32 cells and initial probability values as 0.1 were considered for them. The initial configuration of LCA states was determined by a N=32 bits vector. Also, the neighborhood size considered for next state calculation in each cell was selected as k=3. Afterward, multiple experiments were done. In the first one, the effect of learning neighborhood on the entropy values has been considered. For this purpose, after entering the training phase, each cell selects an action randomly and based on exist probabilities and then, all cells start generating pseudo-random sequences. The local environments, by considering r as the neighborhood size in evaluating each cell performance, calculates entropy values and produces a response as zero or one for each cell. Then the global environment, regarding all entropy values returns a response. This experiment was performed for r=3 and r=5 and its results have been reported in table (1). # Table 1: The effect of Learning Neighborhood on entropy values In the second experiment, the effect of learning neighborhood on the number of required train steps has been regarded. In order to this, the above experiment has been repeated for 10 different initial configurations and for r=3 and r=5. The results have been reported in Table (2). # Conclusion The proposed model in this paper, has considered a LCA for determining optimal rules used by a pseudo-random key stream generator based on CA. On this way, parallel operation by LCA cells has a significant effect on optimal rules determination speed. Also, the number of training steps, considerably, affects the convergence ratio in cells. For evaluating the key stream generated by proposed model, a set of standard tests (FIPS-140-2) have been applied that evaluate its randomness property. A 20000-bit stream produced by proposed model has passed all tests defined in mentioned standard. Also, the obtained results for proposed model, in compare with previous models have been summarized in table (5). 23![Fig. 2: Some common neighborhood patterns for linear and 2-dim CA](image-2.png "Fig. 2 :Fig. 3 :") 4![Fig. 4: Schematic diagram for Rule 105 and Rule 165 for k=3](image-3.png "Fig. 4 :") 6![Fig. 6: The block diagram of an LCA](image-4.png "Fig. 6 :") ![by a flowchart.](image-5.png "") 720128![Fig. 7: The flowchart for selecting m best rulesIn the second stage, the main part of proposed model is considered. This is an LCA that each of its cells can select an action among m different actions. Each action corresponds to a rule in best rules set which has been obtained in previous stage. Each cell interacts with a local environment which receives sequences from the current cell, and its neighbor cells, and returns a response to the cell. Also, a global environment interacts with all cells and returns a response based on the sequences generated by all LCA cells.](image-6.png "Fig. 7 : 2012 AprilFig. 8 :") 9![Fig. 9: The schematic diagram of each LCA cell interacting with local and global environments V.](image-7.png "Fig. 9 :") 10![Fig. 10: The bar diagram for best rules repetitions](image-8.png "Fig. 10 :") 2 3 4 52012April62 © 2012 Global Journals Inc. (US) © 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue VIII Version I * Applied cryptography, Second Edition BSchneier 1996 John Wiley and sons * High-Speed Cellular Automata based block cipher and fault tolerant public key cryptosystems, Thesis, computer science CLai RSaskatchewan Aug 2000 Regina ,Canada * Cellular automata computations and secret key cryptography FSeredynski PBouvry AZomaya 2004 Published by Elsevier B.V * SGolomb Shift-Register Sequences Aegean Press 1982 revised edition * On the Use of Cellular Automata in Symmetric Cryptography AF´uster-Sabater PCaballero-Gil Sept 2006 Springer 93 * Analysis of Cellular Automata used as Pseudo-Random Pattern Generators PHBardell International Test Conference 1990 * Theory of cellular automata: A survey JKari Theoretical Computer Science 334 3 2005 * Synthesis of Cryptographic Interleaved Sequences by Means of Linear Cellular Automata AFúster-Sabater PCaballero-Gil Applied Mathematics Letters 22 10 2009 * The Theory of Self Reproducing Automata JVNeumann A. W. Burks 1966 Univ. of Illinois Press Urbana and London * NGanguly BSikdar ADeutsch GCanright PChaudhuri A Survey on Cellular Automata Dresden, Germany 2003 Centre for High Performance Computing, Dresden University of Technology * Evolving Collective Behavior of Cellular Automata for Cryptography MSzaban FSeredynski P;Bouvry Ieee Melecon 2006. May 16-19 Benalmadena (Malaga), Spain * A Mathematical Framework for Cellular Learning Automata HBeigy MRMeybodi Advanced in Complex Systems,to Appear 2004 7 * Learning Automata: An Introduction KSNarendra MA LThathachar 1989 Prentice Hall * Learning Automata A Survey SKumpati KSNarendra MA LThathachar IEEE Transactions on Systems, Man, And Cybernetics 4 July 1974 * FBao Crytanalysis of a New Cellular Automata Cryptosystem, 8th Australasian Conference on Information Security and Privacy-ACISP Lecture Notes in Computer Science Springer Verlag 2003 * Theory and Applications of Cellular Automata in Cryptography SBlackburn SMerphy KPaterson IEEE Transactions on Computers 46 1997 * Theory and Applications of Cellular Automata in Cryptography SNandi BKKar PPChaudhuri IEEE Transactions on Computers 43 1994 * Cryptography with Cellular Automata, Advances in Cryptology-CRYPTO'85 SWolfram Lecture Notes in Computer Science 218 1994 Springer Verlag * SCho CUn-Sook HYoon-Hee Computing Phase Shifts of Maximum-Length 90 150 2004 * Cellular Automata Sequences Lecture Notes on Computer Science Springer Verlag 2004 3305 Proc. of ACRI * The Analysis of One dimensional Linear Cellular Automata and Their Aliasing Properties MSerra TSlater JMuzio DMMiller IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 9 7 1990 * A new kind of science SWolfram 2002 Wolfram Media 52 Champaign, IL * Wolfram Cellular Automata And Their Cryptographic Use As Pseudorandom Bits Generators, Memoria Samuel Solorzano Barruso Foundation (Spain) and Ministerio de Ciencia y Tecnologia (Spain) under grant RDiaz Len AHernandez Encinas LHernandez Encinas SHoya White AMartin Del Rey GRodriguez IVisus Ruiz 2001 * A Secret Key Cryptography By Iterating Chaotic Map THabutsu Proc. of Eurocrypt_91 of Eurocrypt_91 1991 * Stream Cipher With One And Two Dimensional Cellular Automata MTomassini MPerrenoud LNCS M. Schoenauer et al. 2000. 1917 Springer Eds.) Parallel Problem Solving from Nature -PPSN VI