# Cryptography with cellular automata.

1. IntroductionConfidentiality is mandatory for a majority of network applications including, for example, commercial uses of the Internet. Two classes of algorithms exist on the market for data encryption: secret key systems and public key systems. One of such promising cryptography techniques is CA.

The main concern of this paper is secret key cryptosystems. In such systems the same key is used for encryption and decryption. The encryption process is based on the generation of random ASCII characters, and CA can be effectively used for this purpose. In the context of symmetric key systems, CA were studied by Albert Y. Zomaya et al. [1], Marco Tomassini et al. [3], and Sheng-Uei Guan et al. [7].

This paper is organized as follows: the following section introduces CA, the third section introduces the proposed CA model that we used to generate random ASCII characters and the forth section introduces the conclusion of this paper.

2. Cellular Automata

2.1 What are CA?

Cellular automata [2, 4, 6] are dynamical systems in which space, time, and the states of the system are discrete. A cellular automaton consists of an array of cells, each of which can be in one of finite number of possible states, updated in discrete time steps, according to a local interaction set of rules. The state of a cell at the next time step is determined by the current states of a surrounding neighborhood of cells.

The reason behind the popularity of CA can be traced to their simplicity and to the huge potential that they hold in modeling complex systems, in spite of their simplicity. A cellular automaton can be viewed as a simple model of a spatially extended decentralized system made up of a number of individual components (cells), the communication between constituent cells is limited to local interaction and each individual cell is in a specific state, which changes over time depending on the states of its local neighbors. The overall structure can be viewed as a parallel processing device, however, this simple structure when iterated several times produces complex patterns displaying the potential to simulate different sophisticated natural phenomena.

2.2 CA Notations

In CA, the following elements must be considered:

* States space: cell collection (assuming identical) or a discrete grid of cells on which the automaton works. That is a substrate of one, two, three dimensions or multidimensional.

* Boundary conditions: when considering finite-sized grid, spatially periodic boundary conditions are frequently applied as explained below:

** In one-dimensional CA, the right most cell is considered to be the neighbor of the left most one and vice versa.

** In two-dimensional CA, the north most cells are considered to be the neighbors of their corresponding south most cells, and the east most cells are considered to be the neighbors of their corresponding west most cells; this results in a toroidal grid (see Figure 1).

* The number of states per cell: binary automata (with two states per cell) are the easier to work with, these two states often represent full empty, life dead, on off, and are numerically represented with one and zero.

* Evolutionary rule(s): which defines how the state of each cell must change, depending of its previous state and of its neighborhood properties. Each rule is essentially a finite state machine, usually specified in the form of a rule table (also known as the transaction function), with an entry for every possible neighborhood of states.

[FIGURE 1 OMITTED]

* Initial configuration: at the beginning of the simulations, an initial configuration is given to states space.

* Neighborhood: a neighborhood defined for every cell, consisting in a set of adjacent cells, indicating their respective positions respect at the same cell. The cellular neighborhood of a cell consists of the surrounding (adjacent) cells as explained below:

** For one-dimensional CA, a cell is connected to r local neighborhoods on either side, as well as to itself, where r is a parameter referred to as the radius (each cell has 2r+ 1 neighbors: r neighbors on each side plus itself).

** For two-dimensional CA, two types of cellular neighborhoods [8] are usually considered:

*** Von Neumann neighborhood (see Figure 2): five cells, consisting of the cell along with its four immediate non-diagonal neighbors

*** Moore neighborhood (see Figure 3): nine cells, consisting of the cell along with its eight surrounding neighbors

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

* A virtual computational clock connected to each cell: which generates pulses to cells indicating that such rule must be applied and in such a way cells will change their states.

CA may be classified into uniform CA and non-uniform CA. Non-uniform CA function in the same way as uniform ones, the only difference is that in the case of uniform CA, evolutionary rules must be identical for all cells while in non-uniform CA, evolutionary rules need not be identical for all cells.

3. The Proposed Ca Model

As we mentioned before that we used two-dimensional, 128-state, non-uniform CA to generate random ASCII characters sequence. The state of each cell is a number in the range 0 and 127 inclusive to represent the ASCII code of a character. We considered Moore-neighborhood and boundary conditions. We used the standard GENETIC ALGORITHM (GA) to obtain the best CA rules that can be used to generate random characters and we used binary encoding to represent CA rules as GA chromosomes. The generated random characters are used to construct a text key; an important note is that the constructed key will not contain non-printable characters (characters whose ASCII codes are in the range 0 and 32 inclusive) and so such characters will be excluded when constructing the key.

In the following sub sections we will introduce our CA model in details and we will show how we applied the operators of the standard genetic algorithm on it.

3.1 Defining Rules

Consider the four logic operators AND, OR, XOR and NXOR (not XOR). If [S.sub.i,j](t) is the state of the cell at row i and column j at time t, then its state at the next time step, [S.sub.i,j](t+1) is calculated using the following equation:

[S.sub.i,j](t+1) = [S.sub.i,j](t)op1 [ S.sub.i-1,j](t)op2 [S.sub.i-1,j+1](t)op3 [S.sub.i,j+1](t)op4 [S.sub.i+1,j+1](t)op5 [S.sub.i+1,j](t)op6 [S.sub.i+1,j-1](t)op7 [S.sub.i,j-1](t)op8 [S.sub.i+1,j-1](t) (1)

Where [S.sub.i-1,j](t), [S.sub.i-1,j+1](t), [S.sub.i,j+1](t), [S.sub.i+1,j+1](t), [S.sub.i+1,j](t), [S.sub.i+1,j-1](t), [S.sub.i,j-1](t) and [S.sub.i+1,j-1](t) are the states of the neighboring cells of the cell at row i and column j according to Moore-Neighborhood and each of opl, op2, op3, op4, op5, op6, op7 and op8 are one of the four logic operators AND, OR, XOR and NXOR.

The previous equation represents the general form of each rule in our CA model. According to the previous general form of rules, the number of rules will be [4.sup.8] = 65536 which is too large; therefore we used the standard genetic algorithm to search for the best set of rules that can be used to generate random characters.

As we mentioned before that the state of each cell will be a number in the range 0 and 127 inclusive. To apply one of the logical operators AND, OR, XOR and NXOR on two numbers in that range, we perform the following steps:

1. Each of the two numbers is converted to its 7-bit binary representation.

2. The operator is applied on each two corresponding bits in the two binary representations obtained from the previous step.

Following is an example:

Example

Consider the operation 52 AND 123; to calculate the result of this operation we will first convert each of the two numbers 52 and 123 to its 7-bit binary representation. 52 will be converted to 0110100 and 123 will be converted to 1111011. Then, we will apply the AND operator on each two corresponding bits in the binary representation as shown below:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.2 Applying GA Operators

3.2.1 The Mutation Operator

The mutation operator is applied, on a CA rule, by mutating a randomly chosen bit in the binary representation of the rule with a mutation probability. The next example shows how we apply the mutation operator on rules in our CA model:

Example: consider the following rule:

[S.sub.i,j](t+1) = [S.sub.i,j](t)XOR [S.sub.i-1,j](t) AND [S.sub.i-1,j+1](t) NXOR [S.sub.i,j+1](t) OR [S.sub.i+1,j+1](t) AND [S.sub.i+1,j](t) XOR [S.sub.i+1,j-1](t) OR [S.sub.i,j-1](t) NXOR [S.sub.i+1j-1](t)

Assume that we want to apply the mutation operator on the previous rule. First, we must construct the binary representation of the rule using Table1. According to table1, the binary representation of the given rule is 1000110100100111 (this string is obtained by mapping each of the 8 logical operators, used in the rule, to its binary representation according to Table1.)

After obtaining the binary representation of the rule, we apply the mutation operator; assume that we will mutate the bit at position 3 in the binary representation of the given rule (assuming that the bit at position 0 is the left-most bit), we will obtain the string: 1001110100100111. The obtained string represents the following rule:

[S.sub.i,j](t+1) = [S.sub.i,j](t) XOR [S.sub.i-1,j](t) OR [S.sub.i-1,j+1](t) NXOR [S.sub.i,j+1](t) OR [S.sub.i+1,j+1](t) AND [S.sub.i+1,j](t) XOR [S.sub.i+1,j-1](t) OR [S.sub.i,j-1](t) NXOR [S.sub.i+1,j-1](t)

3.2.2 The Crossover Operator

Crossover is performed with probability between two selected individuals; the two selected individuals are exchanged after a randomly selected crossover point. The next example shows how we apply the crossover operator on rules in our CA model.

Example: consider the following two rules:

The first rule:

[S.sub.i,j](t+1) = [S.sub.i,j](t) AND [S.sub.i-1,j](t) OR [S.sub.i-1,j+1](t) NXOR [S.sub.i,j+1](t) XOR [S.sub.i+1,j+1](t) AND [S.sub.i+1,j](t) OR [S.sub.i+1,j-1](t) NXOR [S.sub.i,j-1](t) OR [S.sub.i+1,j-1](t)

The second rule:

[S.sub.i,j](t+1) = [S.sub.i,j](t) OR [S.sub.i-1,j](t) OR [S.sub.i-1,j+1](t) NXOR [S.sub.i,j+1](t) AND [S.sub.i+1,j+1](t) AND [S.sub.i+1,j] (t) XOR [S.sub.i+1,j-1](t) OR [S.sub.i,j-1](t) AND [S.sub.i+1,j-1](t)

To apply the crossover operator, first we must construct the binary representation of each of the two given rules. The binary representation of the first rule is: 0001111000011101 and the binary representation of the second rule is: 0101110000100100.

Now, assume that we will apply the crossover operator between the two binary representations at location 5; the first child will inherit bits 0 through 5 from the first parent and bits 6 through 15 from the second parent, vice versa for the second child.

Therefore, the first child will be 0001110000100100 which represent the following rule:

[S.sub.i,j](t+1) = [S.sub.i,j](t) AND [S.sub.i-1,j](t) OR [S.sub.i-1,j+1](t) NXOR [S.sub.i,j+1](t) AND [S.sub.i+1,j+1](t) AND [S.sub.i+1,j](t) XOR [S.sub.i+1,j-1](t) OR [S.sub.i,j-1](t) AND [S.sub.i+1,j-1](t)

And the second child will be 0101111000011101 which represents the following rule:

[S.sub.i,j](t+1) = [S.sub.i,j](t) OR [S.sub.i-1,j](t) OR [S.sub.i-1,j+1](t) NXOR [S.sub.i,j+1](t) XOR [S.sub.i+1,j+1](t) AND [S.sub.i+1,j](t) OR [S.sub.i+1,j-1](t) NXOR [S.sub.i,j-1](t) OR [S.sub.i+1,j-1](t)

3.2.3 The Fitness Value

The fitness value for each rule is calculated using the DIEHARD [5] test of randomness. To calculate the fitness value for a given rule, we use the following procedure:

First, we select a random initial CA population.

Second, for a specific number of times, we apply the concerned rule on the CA population. Each time we apply the rule, we append the CA output to a binary file.

Third, we test the binary file, obtained from the previous step, using one of the DIEHARD tests of randomness. We consider the result of the DIEHARD test as the fitness value of the rule.

4. Conclusion

In this paper we used two-dimensional, 128-state, non-uniform CA to generate random ASCII characters. We used the standard genetic algorithm to obtain the best CA rules that can be used to generate random characters. We used the generated random characters to construct a text key (a key that contains letters and/or digits and/or symbols) that can be used in the data encryption/decryption process. We conclude that CA are able to generate random characters and have good quality as measured by the DIEHARD test.

5. References

[1] Albert Y. Zomaya, Franciszek Seredynski and Pascal Bouvry, Cellular automata computations and secret key cryptography, Parallel Computing 30 (2004) 753-766

[2] Jarkko Kari, 2005, Theory of cellular automata: A survey, Theoretical Computer Science 334: 3-33.

[3] Marco Tomassini and Mathieu Perrenoud, Cryptography with cellular automata, Applied Soft Computing 1 (2001) 151-160

[4] Marcus Pivato, 2005, Cellular Automata vs. Quasistrumian Shifts, Ergodic Theory and Dynamical Systems forthcoming = math.DS/0503502.

[5] Marsaglia, Diehard, http://stat.fsu.edu/~geo/diehard.html, 1998 [6] P.-Y. Louis, 2005, Increasing coupling of probabilistic cellular automata, Statistics and Probability Letters 74: 1-13.

[7] Sheng-Uei Guan and Syn Kiat Tan, Evolving cellular automata to generate nonlinear sequences with desirable properties, Applied Soft Computing 7 (2007)1131-1134.

[8] Veronique Terrier, 2004, Two-dimensional cellular automata and their neighborhoods, Theoretical Computer Science 312: 203-222.

(1) Mahmoud M. H. Gabr, (2) Yasser F. Hassan and (3) Khaled Mohamed Mohamed

(1,2,3) Mathematic Department (Computer Science), Faculty of Science, Alexandria University Alexandria, Egypt 010060040, +002

(1) E-mail: MMAHGabr@sci.alex.edu.eg

(2) E-mail: Y.Fouad@sci.alex.edu.eg

(3) E-mail: K.Mohamed@sci.alex.edu.eg

Table 1: Binary Representations of the Logical Operators: AND, OR, XOR and NXOR. Operator Binary Representation AND 00 OR 01 XOR 10 NXOR 11

Printer friendly Cite/link Email Feedback | |

Author: | Gabr, Mahmoud M.H.; Hassan, Yasser F.; Mohamed, Khaled Mohamed |
---|---|

Publication: | International Journal of Computational and Applied Mathematics |

Article Type: | Report |

Geographic Code: | 7EGYP |

Date: | Jan 1, 2009 |

Words: | 2531 |

Previous Article: | A comparative performance of swarm intelligence optimization method and evolutionary optimization method on some noisy numerical benchmark test... |

Next Article: | An order level inventory model for perishable items with stock dependent demand and partial backlogging. |

Topics: |