Interesting Aspects Of Cellular Automata Cellular Automata are a relatively new field of re
- 格式：pdf
- 大小：55.74 KB
- 文档页数：4
1Interesting Aspects Of Cellular Automata
Cellular Automata are a relatively new field of research in mathematics. They were
first investigated by the Hungarian mathematician John Von Neumann in his study of
self-reproducing machines. A fellow mathematician, Stanislaw M. Ulam, suggested
that he looked at these in a more abstract way.
Von Neumann made use of what is known as a ‘Uniform Cellular Space’. In this
space the state of one cell would depend on the state of neighbouring cells in the
previous step. This is the general principle of cellular automata.
In this section we will consider some interesting aspects of Cellular Automata.
Cryptographic Applications of Cellular Automata
One of the mathematicians most closely associated with cellular automata is Stephen
Wolfram. Stephen Wolfram was born in London in 1959, and went on to become the
youngest recipient of a MacArthur Prize Fellowship. Now he is known as the creator
of Mathematica in addition to his research on cellular automata.
In 1981 he began researching cellular automata. Wolfram has classified 256 different
rules for one-dimensional cellular automata, where the state of one cell is dependent
on the state of the cells to its right and left in the previous step. (See Appendix A)
Some of these rules, for example Rule 90, produce very simple, self-repeating
patterns. Certain rules may appear complicated but closer examination reveals regular
patterns.
However other rules produce incredibly irregular patterns.
Rule 30:-
Rule 30 is one of these rules. This rule is described by Stephen Wolfram as follows:
“Look at each cell and its right-hand neighbour. If both of these cells were white in
the last step, take the new colour of that cell to be whatever the previous colour of its
left-hand neighbour was. Otherwise, take the new colour to the opposite of the colour
of the left hand cell in the previous step.”
This rule can be represented diagrammatically as shown below.
Representation of Rule 30
To use this rule start with one cell and then apply the rule over and over again. Below
is a picture of the first one-hundred applications of the rule, to give the reader an idea
of the random pattern formed; here we have started with a single black cell.
The First 100 Applications of Rule 30
Cryptography In General and Cryptography Using Cellular Automata: -Since 1976
most research focussing on cryptography has centred on Public Key Cryptography.
Public Key Cryptography relies on the use of one-way trap door functions. These are 2functions that are easy to compute in one direction, but so hard as to make them
unfeasible to compute in the other direction unless you have the ‘key’ to the trapdoor.
Many cryptographic algorithms make use of the difficulty of the factorisation of
integers.
Getting back to the subject of cellular automata, Rule 30 is known to exhibit many
properties that are desirable for cryptography.
It does not repeat for any short period, and it also doesn’t show any obvious structure
for the majority of keys. Here the ‘key’ is the initial state to which the rule is first
applied. The central column of Rule 30 has also been subjected to many tests for
randomness and has so far passed every one. However there is no known way to
prove this randomness. This fact also leads to the possibility of using Rule 30 as a
random number generator.
In a New Kind of Science Stephen Wolfram has set out Boolean expressions for the
first five steps of Rule 30, these rapidly become highly complex. These Boolean
expressions determine the encryption sequence from the key, so it is obviously
desirable for them to be as simple as possible. It has also been shown that the system
is very efficient, an important factor in the ability of a cryptographic algorithm to be
actually used. An algorithm that is highly secure but very inefficient to implement
would be completely useless, because of the time factor it takes to implement it and
also the cost of the computing power required!
Rule 90 would be unsuitable for cryptography for many reasons. It repeats a common
pattern fairly quickly, and the Boolean expressions for the steps remain fairly simple
throughout the evolution of the cellular automata.
In a paper published in 1985, Wolfram suggested sampling the evolution of the
cellular automata to generate an encryption sequence. Since the publication of this
paper there have been many attempts, so far without success, to create a working
cryptographic system based on Rule 30.
The major deciding factor for the worth of a cryptographic algorithm is its resistance
to crypto-analytic attack. In principle any cryptographic system can be broken by a
