The method and apparatus of the preferred embodiment will now be described with reference to figures 1 to 5. The preferred embodiment uses toggle cellular automata as dynamical systems for encryption and decryption. These toggle cellular automata are the secret keys used in encryption and decryption. Before secure communication can begin between two parties A and B, these parties must share a secret collection of toggle cellular automata, and some convention for selecting which of these are to be used at each step of encryption/decryption.
The key elements of the method of the preferred
embodiment will be presented
in terms of a concrete application in which the encryption/decryption
capabilities of this invention are advantageous. Further applications,
the hardware modifications they entail, and several alternate
embodiments of the invention will be specified below. In
this application only one toggle automaton, of radius 
,
is used as a secret key. It is assumed that this is a left-toggle
cellular automaton. It is further assumed that the communicating
parties share an integer 
which specifies the number of
encryption/decryption steps.
The application involves communication between two banks, A and B. Bank A,located in the United States, wishes to securely communicate with bank B, located in Japan. Due to their great physical separation, these banks must communicate over an insecure trans-pacific phone line via modem. As in any application, the type of information to be communicated influences the convention to be established between the communicating parties which governs how information is to encoded and decoded into the encryption/decryption apparatus. In this case, A and B communicate numbers representing the values of various transactions. They must identify these numbers as representing either dollars or yen, and need certain special symbols to aid in further processing of this information. They find that a 4-bit code, as given in table 1 suffices for their needs. In this table a symbol, the 4-bit code for the symbol, and its meaning if non-numeric is indicated.
Table: Code for symbols used application to
international bank communication.
Referring to fig. 1, an overview of the preferred embodiment used in this application will now be described. The information to be encrypted is supplied from an input information stream 100 generated by A, this input stream resides before encryption on some electronic storage medium, such as a computer storage disk. The input information stream contains banking symbols from the first column of table 1. A also possess a noise generator 200 which supplies random bits of information, any high-quality noise source, such as the DOD standard noise source, could serve as 200. A has an encoder 300 which translates banking symbols into bit strings as specified in table 1. The encoder 300 could be embodied as a read-only memory which contains the information in table 1. A has an encryption apparatus 400 which is able to inverse iterate toggle cellular automata in iterative and/or parallel mode as described below. B has a decryption apparatus 500 which is able to forward iterate toggle cellular automata in iterative and/or parallel mode as described below. B possesses further a decoding apparatus 600 which translates bit streams into streams of banking symbols by reference to table 1. The way B uses this apparatus to generate an output information stream 700 duplicating the A's input information stream 100 is specified below.
The details of the operation of the apparatus of the preferred embodiment
depend on several constants which depend in turn on the
radius of the cellular automaton used. To simplify the
specification, these constants will be given labels
as follows: 
, 
, and 
.
Refer now to figure 2.
The apparatus of the preferred embodiment has several
basic parts which are used in both encryption and
decryption. The first part 10 is a lookup
table which contains the cellular automaton rule,
and will thus be called the rule table.
This rule table is an array of memory elements
each of which can store 1 bit of information. The
number of memory elements which must be devoted to
this purpose depends on the radius of the rule
used. If the radius is , then there must be 
memory
elements in the rule table.
There must be at least one data processor in the system 20
which is able to set the values in the rule table. Depending
on hardware details, this processor could be physically identical
with some other processor. It will be referred to as the
rule-table setter. The rule-table setter takes as input
a bit b and an integer i and sets the value of two
elements of the rule table accordingly. The integer i must
be the the range 
. The rule
table setter has two modes of operation, left and right.
In left mode,
if the bit b is 0,
then the rule-table setter sets the rule-table
element indexed i to 0 and sets the rule-table element indexed
i+
to 1.
If the bit b is 1,
then the rule-table setter sets the rule-table
element indexed i to 1 and sets the rule-table element indexed
i+ to 0.
In right mode,
if the bit b is 0,
then the rule-table setter sets the rule-table
element indexed 2
i to 0 and sets the rule-table element indexed
2i+1 to 1.
If the bit b is 1,
then the rule-table setter sets the rule-table
element indexed 2i to 1 and sets the rule-table element indexed
2i+1 to 0.
As an example of the operation of the rule-table setter, consider construction of the rule table for the nearest-neighbor (r=1) left-toggle cellular automaton rule 30 shown in table 2. Since r is 1, R is 4. Invoking the rule-table setter in left mode with the bit sequence 0,1,1,1 for i = 0 to 3 respectively produces the rule 30. Invoking the rule-table setter in right mode with the same bit sequence produces the right-toggle rule 86. The left-toggle rule 60 which is used in some examples below is produced by the rule-table setter in left mode with the input sequence 0,0,1,1. The rule tables for these three rules are shown in table 2.
Advantageously, the rule-table setter has a third mode, a direct mode, in which information may be passed directly into the array 10 to set-up the rule-table. The direct mode can only be used if the information is already structured to represent either a left- or right- toggle rule.
There must be an array of memory elements 30 which
stores the current state and dynamical I/O,
the information being encrypted and decrypted.
The memory elements in this array are indexed 
, and
may be considered to be physically 1-dimensional. Each can
store 1 bit. If the block size, number of encryption/decryption steps,
and rule radius
are 
,, and respectively, then 
is at least 
.
Advantageously, for iterative encryption and decryption,
there is another processor in the system 40
which has associated to it a memory element 50
which can store 
bits of data.
This memory will be considered to contain a
-bit integer, but could also be embodied as a shift register.
Depending on hardware details, this processor 40 could
be identical to some other processor in the system.
The processor 40 can perform the following operations:
Iterative encryption and decryption will be described using this processor 40 and its memory element 50. Alternatively, each of the memory elements in the array 30 could be associated with its own processor, each able to access only part of the memory array 30, and each updating only one element of the array 30. Use of a distinguished processor 40 permits the total number of bit operations performed during each cycle of iterative encryption and decryption to be reduced compared to the iterative process in which the tasked are distributed over an array of processors, each acting only during part of the cycle.
Use of such an array of processors will be described below in conjunction with the parallel decryption process.
Table: Lookup tables for iteration of cellular automaton rules 30,
86, and 60, used as example keys in the preferred embodiment.
The iterative method and apparatus of encryption will now be described with reference to figures 1 and 2.
A block of banking symbols is retrieved from the input information stream
100 by the encoder 300, which then codes these
symbols by reference to table 1 into a block of bits. If
there are 
symbols in the block of symbols retrieved, then the number of
bits is 
. These bits are
loaded in sequence into the
memory array 30 by the encoder.
This activates memory elements in the array 30,
indexed 
.
Using the rule-table setter 20, the rule table 10 is loaded with the secret key.
Encryption then continues over cycles. At each cycle,
the following operations are performed in sequence:
, there are already 
active, so these
bits are placed in the memory elements of array 30
indexed 
.
and so on down to the 0th-order bit which
is set according to the bit placed in the memory element 30
indexed 
.
, and
continuing down to the memory element labeled 0, the
following operations are performed:
After n cycles of encryption, the memory elements of 30 indexed 0-(N+2rn-1) are activated, and contain the ciphertext.
In each cycle of iterative encryption just described, one inverse iteration of a cellular automaton was performed. By using an array of processors, each of which similar to the processor 40 used above, many steps of inverse iteration can be performed at the same time in parallel. The array of processors 60, their associated d-bit memory elements 70, are shown in figure 3. To perform n steps of parallel encryption, these arrays must contain at least n elements.
All of the processors in the array 60 can read from the rule table 10, each can also read and write to its associated memory element in the array 70.
Only the processor in array 60 indexed 0 can read from the memory array 30 which contains the information being encrypted, and only the processor in array 60 indexed n-1 can write to the memory array 30. All of the processors except the one indexed 0 can read from the memory element of array 70 indexed 1 less than its own index. Since the processors have slightly different I/O connections, it will be useful to give them different names. The processor indexed 0 will be called the bottom processor, the processor indexed n-1 will be called the top processor, and the others will be called middle processors.
-bit string encoding the information
to be encrypted is the same
as in iterative encryption described above.
The
rule table 10 is initialzed with the rule table setter 20
also as in iterative encryption.
Each of the memory
elements in the array 70 is initialized with random
information in the same way that the memory 50 was
initialized in iterative encryption. As in iterative encryption,
the same random bits are also used to initialize states of
memory elements in the array 30. The bits used to initialize
memory element 
of the memory array 70 are used also
to initialize the states of memory elements 30 indexed
.
Let K be 
, i.e. the total number of memory elements
in array 30 initialized with either information to be
encrypted or random information. Define two indices C and P
with initial values 
and 
. Then for an
index i intialized to 0.
The following process, in which each processor
in the array 60 operates in parallel,
stops when i reaches C-(2 r+1):
Each of the middle processors indexed , and the top
processor indexed 
obtain a bit b from
0th-order position of the integer in the element of the memory
array 70 indexed 
.
At the end of this process, the ciphertext is in the memory array
30, in elements indexed 
.
While both encryption and decryption in the preferred embodiment are best performed in parallel hardware, it is possible to perform decryption as well as encryption using a single main data processor, using the same apparatus as used in iterative encryption and as shown in figure 2.
Assume that 
bits of ciphertext have been received by a user
B who wishes to decrypt them.
The bits of ciphertext are used to activate elements
in the memory array 30, indexed 
.
The d-bits in the integer in memory element 50
are set according to the last d bits of the ciphertext.
The
rule table 10 is initialized with the rule table setter 20
as in encryption.
An index 
is set to Q, an index J is set to 0, and
an index k is set to K-d.
This process forward iterates the dynamical system one step at each cycle.
At the end of all n cycles, the bits from the memory array 30 are passed to the decoder 600 (fig. 1). The decoder looks up from table 1 the symbol corresponding to each group of 4 contiguous, non-overlapping bits. The resulting symbol stream 700 is the same as the symbols input by A.
Parallel decryption is described with reference to fig. 3.
The updating of each of the memory elements in the
array 30 can be done in parallel using an
array of processors. This array 80 contains
processors each similar to the processor 40 used
in iterative decryption. Each of this processors is
associated with a memory element of an array 90,
each of elements of which can store d bits of information.
As above, the d-bits are considered to represent a d-bit
integer. If the number of bits in the ciphertext block
is , then the arrays 80 and 90 must each have
at least elements.
While the processor 40 used in iterative decryption
can read and write to any
element in the array 30, a processor indexed in the
array 80 needs only to be able to read from the elements indexed
in the array 30. Such a processor
need only to be able to write to the memory element indexed
in the array 30. The arrangement of I/O connections of the
processors in the array 80 is shown in fig. 3.
In order to avoid indexing problems near the end of the arrays,
these arrays can be considered to have periodic boundary conditions, i.e.,
the element indexed Q is identified with the element indexed 0.
Initialization. The memory array 30 is activated with
bits of ciphertext just as above.
The rule table 10 is initialzed with the rule table setter 20
as in encryption.
Decryption. Over n cycles each of the processors in array 80 performs the following operations:
reads d bits from the memory array
30 at positions indexed , and stores
these bits as an integer g in its associated memory in
the array 90.
sets the memory element indexed in
array 30 to b.
After n cycles the contents of 30 are sent to the decoder 600 as in iterative decryption.
Tables 3 and 4 show the encryption and decryption of an example message using the apparatus described above. In this example a simple message: ``Y146.00" is sent from A to B. A and B share as secret key, the radius-1 left-toggle rule known as rule 30, whose rule table is given in the third column of table 2. It is considered public knowledge that banks use 14 steps of encryption/decryption for their communication. Tables 3 and 4 show the steps of encryption/decryption in two different formats. In table 3 the state of the memory array 30 at the end of each cycle of encryption/decryption is shown coded according to table 1. This representation allows for easy global visualization of the steps of the process. In table 4 the same steps of encryption/decryption are shown in a raw format, i.e. the actual states of the elements in the array 30 are shown. This representation allows detailed verification of the steps performed.
A variant of the raw display format allows the resistence of the invention to cryptanalytic attack to be easily verified. In this variant, two very similar runs of encryption are performed, and an XOR of the state of the memory array in the two cases is displayed. The XOR is 1 if and only if values in the corresponding positions in the two runs differ. For clarity 1 is represented by the symbol ``#'' and 0 is represented by the symbol ``_''. In table 5, the decryption phase of tables 3 and 4 is XOR'ed with a decryption process using the same sequence of random bits in the dynamical input, but on a ciphertext which differs by 1 bit from the ciphertext of tables 3 and 4. Note that the single error propagates as decryption proceeds. If a sufficient number of encryption/decryption steps are used, then the single error will diffuse across the entire plaintext.
Table 6 is similar to table 5, though here encryption is shown in which a single error has been introduced into the plaintext. Note that, this error propagates across the ciphertext, albeit only to the left. Means to assure that errors propagate in both directions are discussed below.
Table 7 shows the difference produced when the encryption of tables 3 and 4 is performed on the same text with the same sequence of random numbers, but with a left-toggle cellular automaton rule which differs by one bit from that used in 3 and 4. This is this rule is known as rule 60 (table 2, column 5). Note that this minimal difference between keys produces differences throughout the ciphertext produced.
Note that if is the radius of the rules used, the
size of the rule table is 
, the number of
bits required to index into the rule table is 
, and the number of
different number toggle rules (both left and right) is
.
For clarity, the example encryptions using the preferred
embodiment are done using radius 1 rules. In practical
situations radius 1 rules would not be used. There are
only 32 radius 1 toggle rules.
A code-breaker could easily try them all and hence decrypt
the message by brute force. The situation at radius 2 is
somewhat better; there are 131,072 radius 2
toggle rules. Still, especially since decryption with this
invention is extremely fast, this number of rules could be
searched rapidly in a brute-force attack. If self-synchronized
key streams are used, so that keys are changed after each block
encrypted, radius-2 rules may provide an acceptable level of
security. At radius 3, there are approximately 
toggle rules, which should be enough for most applications. At radius 3,
the number of keys is already 512 times greater than the number of
keys in used the Data Encryption Standard.
In general, one would like a radius as large as possible given hardware limitations. There are two main hardware factors which could limit the radius of the rules used 1) address space size limitations connected with the number of bits each integer memory holds, and 2) memory size limitations connected with the memory required to hold the rule table.
An 16-bit processor such as used in personal computers
has sufficient address space to use radius 7 rules,
of which there are 
, roughly 
.
A 32-bit processor, such as used workstations and some personal computers
has sufficient address space to use radius 15 rules,
of which there are 
.
In most situations then, memory size, rather than
address space is the most serious potential limitation. A
standard 4-megabyte memory chip (such as those made by the Intel
Corporation, for instance)
holds 
bits of information, and could thus hold the
rule table for a radius-12 rule. As there are
radius-11 rules, this should be much more than
sufficient for most applications. Still larger radius rules
could be handled with an array of memory chips to hold the
rule table.
Table: Encryption and Decryption of an example message
between banks A and B. In this table the state of
the processor array at each step of encryption/decryption
is treated by the decoder 600 to allow for easy
visualization. The plaintext, Y146, appears at line
0 of the encryption table and line 14 of the decryption
table. The ciphertext, 8X.0X021.66$X,
appears at line 14 of the
encryption table , and line 0 of the decryption table.
Table: This table shows the same steps of encryption/decryption
as table 3. Here, however, the actual state of the
processor array is shown. The plain text is to be read left to
right in groups of 4 bits, i.e. 1111='Y', 1000='1', 
0000='0'.
The right-most two entries in each line are the dynamical I/O.
Table: Propagation of a single error introduced into the ciphertext.
``_" = site same as with no error ``#"= site differs with error.
Table: Propagation of a single error introduced into the plain text.
``_" = site same as with no error ``#"= site differs with error.
Table: Difference pattern: encryption under rules 30 and 60,
which are only 1-bit different from each other. The 1-bit error in the rule
produces random changes throughout the ciphertext