Method and apparatus for encryption, decryption and authentication using dynamical systems5365589Abstract A method and apparatus provide encryption, decryption and authentication of messages using dynamical systems. The method and apparatus preferably operate on an information stream which may comprise message information, authentication information, and random or pseudo-random information. The initial secret keys of the system are a collection of dynamical systems, at least one of which is irreversible. These keys operate on states of the dynamical systems into which the message has been encoded. To initialize the encryption, a subset of the secret keys are selected to be current keys, and the desired message is encoded into the initial states. Encryption continues over a plurality of cycles. During each cycle the current keys are applied either backward or forward in time to their current states, over a plurality of sub-cycles. If during an encryption cycle an irreversible dynamical system is iterated in the backward direction, the choice of antecedent states may either be made randomly or according to information from the input information stream. After all encryption cycles have been performed, the current states of the dynamical system constitute the ciphertext. The ciphertext may then be decrypted by a method similar to the encryption method. In the preferred embodiment, random noise is diffused into the plaintext during encryption, and eliminated during decryption. The apparatus of encryption and decryption in the preferred embodiment operates with parallel hardware using only bit operations and table lookup; it may thus be made to operate in an exceedingly fast manner. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
______________________________________
Code for symbols used in application
to international bank communication.
Symbol Code Meaning
______________________________________
0 0000
1 1000
2 0100
3 1100
4 0010
5 1010
6 0110
7 1110
8 0001
9 1001
. 0101 decimal
" " 1101 space
, 0011 comma
X 1011 block end
$ 0111 dollar
Y 1111 yen
______________________________________
used in this application will now be described. The information to be encrypted is supplied from an input information stream shown at 100 generated by A. This input stream typically resides before encryption on some electronic storage medium, such as a computer storage disk. The input information stream contains banking symbols in accordance with those shown in the first column of Table 1. In accordance with the invention, A also possesses a noise generator 200 which supplies random bits of information. It will be understood that any high-quality noise source, such as, for example, the DOD standard noise source, could serve as noise generator 200. A has an encoder 300 which translates banking symbols into bit strings as specified in Table 1. The encoder 300 may be embodied as a read-only memory which contains the information in Table 1 or in other software well known to those skilled in the art. A has an encryption apparatus 400 which is able to backward 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 method in accordance with the invention in which B uses this apparatus to generate an output information stream 700 duplication A's input information stream 100 is described below. The details of the operation of the apparatus of the preferred embodiment depend on several constants which depend in turn on the radius r of the cellular automaton used. To simplify the description, these constants will be given labels as follows: the diameter, d=2r+1, the rule table size S=2.sup.2r+1, and the reduced rule table size R=2.sup.2r. Referring now to FIG. 2, the apparatus of the preferred embodiment has several parts which are used in both encryption and decryption. Part 10 comprises a memory implementing a lookup table which contains the cellular automaton rule, and will thus be called the rule table. This rule table comprises an array of memory element each of which, preferably, can store 1 bit of information. The number of memory elements which must be devoted to this purpose depends on the radius of the particular rule used. If the radius is r, then there must be S memory elements in the rule table. Data processor 20 sets the values in the rule table 10. There must be at least one such processor and it will be appreciated to those skilled in the art that, depending on hardware details, this processor could be physically identical with another processor in the system. This processor will be referred to as the rule-table setter. The rule-table setter 20 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 in the range 0<=i<R, the reduced rule table size. The rule table setter 20 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+R to 1. If the bit b is 1, then the rule-table setter 20 sets the rule-table element indexed i to 1 and sets the rule-table element indexed i+R to 0. In right mode, if the bit b is 0, then the rule-table setter 20 sets the rule-table element indexed 2*i to 0 and sets the rule-table element indexed 2*i+ 1 to 1. If the bit b is 1, then the rule-table setter 20 sets the rule-table element indexed 2*i to 1 and sets the rule-table element indexed 2*i+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.
TABLE 2
______________________________________
Lookup tables for iteration of cellular automaton rules 30,
86, and 60, used as example keys in the preferred embodiment.
Rule 30 86 60
index x.sub.i-1.sup.t x.sub.i.sup.t x.sub.i+1.sup.t
x.sub.i.sup.t+1
x.sub.i.sup.t+1
x.sub.i.sup.t+1
______________________________________
0 000 0 0 0
1 001 1 1 0
2 010 1 1 1
3 011 1 0 1
4 100 1 1 1
5 101 0 0 1
6 110 0 1 0
7 111 0 0 0
______________________________________
As previously discussed, the rule numbers are derived from the sum of the binary expansions of the location of the 1's in the respective index position of the rule table. Thus in the examples of Table 2, in the third column 2.sup.4 +2.sup.3 +2.sup.2 +2.sup.1 =16+8+4+2=30 (Rule 30) while in the fourth column, 2.sup.6 +2.sup.4 2.sup.2 +2.sup.1 =64+16+4+2=86. Array of memory elements 30 stores the current state and dynamical I/O, that is, the information being encrypted and decrypted. The memory elements in this array are indexed i=0, . . . , M-1, 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 N, n, and r respectively, then M is at least N+2nr. Advantageously, for iterative encryption and decryption, another processor in the system 40 has associated with it a memory element 50 which can store d bits of data. This memory will be considered to contain a d-bit size integer, but could also be embodied as a shift register. Depending on the desired hardware implementation, it will be apparent to those skilled in the art that this processor 40 could also be identical to some other processor in the system. Suitably, the processor 40 performs the following operations: Access the bits in the memory elements of the array 30 and set bits accordingly in its memory element 50. Access the rule table 10 using information in its memory element 50, and set bits accordingly in the array of memory elements 30. Shift, either to the left or right, the bits in its memory element 50. The method of iterative encryption and decryption will now be described using this processor 40 and its memory element 50, though as stated previously, it will be understood that the method may be suitably carried out using other processors in the system. Alternatively, each of the memory elements in the array 30 may 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 tasks are distributed over an array of processors, each acting only during part of the cycle. Use of such as array of processors will be described below in conjunction with the parallel decryption process. ITERATIVE ENCRYPTION The iterative method and apparatus of encryption will now be described with reference to FIGS. 1 through 3. Initialization of the system. 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 m symbols in the block of symbols retrieved, then the number of bits is N=4*m. These N bits are loaded in sequence into the memory array 30 by the encoder. This activates N memory elements in the array 30, these elements being indexed 0, . . . , N-1. Using the rule-table setter 20, the rule table 10 is loaded with the secret key. Encryption. Encryption then continues over n cycles. At each cycle, the following operations are performed in sequence: Bits from the noise generator 200 are placed in the dynamical I/O for this cycle of encryption. The dynamical I/O in this embodiment using left-toggle rules of radius r comprises the 2r memory elements of array 30 to the right of the currently active memory elements. At encryption cycle j, there are already N+2rj memory elements active, so these bits are placed in the memory elements of array 30 indexed N+2rj+i, i=0, . . . , 2r-1. The same 2r bits used to activate memory elements in the array 30 are placed in the memory element 50 of the processor 40. The (2r-1)th -order bit of the integer in the memory 50 is set accordingly to the bit placed in the memory element of 30 indexed N+2rj and so on down to the 0th-order bit which is set according to the bit placed in the memory element 30 indexed N+2r(j+1)-1. Beginning with the memory element 30 indexed k=N+2rj-1, and continuing down to the memory element labeled 0, the following operations are performed: An entry f in the rule table 10 is retrieved by the processor 40. Let b be the bit in the memory element 30 indexed k, and let g be the integer in the memory element 50. If b is 0, then f is the gth entry in the rule table 10, and if b is 1, then f is the (g+R)th entry in the rule table 10. The kth memory element of 30 is set to f. The integer in 50 is shifted to the right, i.e., the (2r-1)th-bit becomes the (2r-2)th bit and so on down. The 0th-order bit is dropped. The (2r-2)th-bit of the integer stored in memory 50 is set to f. After n cycles of encryption, the memory elements of 30 indexed 0 to (N+2rn-1) are activated, and contain the ciphertext. PARALLEL ENCRYPTION In each cycle of iterative encryption just described, one inverse iteration of a cellular automaton was performed. When an array of processors is used, each of which is of a type similar to the processor 40 described above, many steps of inverse iteration can be performed sat the same time in parallel. FIG. 4 shows such an array of processors 60 having associated d-bit memory elements 70. To perform n steps of parallel encryption, these arrays must contain at least n memory elements. It will be understood that 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. However, in accordance with a preferred embodiment illustrated here, only that processor in array 60 that is indexed 0 needs to be able to read from the memory array 30 which contains the information being encrypted, and only the processor in array 60 that is indexed n-1 needs to be able to write to the memory array 30. Each of the processors except the one indexed 0 can read respectively from the memory element of array 70 that is indexed 1 less than its own index number. 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 herein the bottom processor, the processor indexed n-1 will be called the top processor, and the other will be called middle processors. The operation of this processors will be explained with reference to FIG. 5. Initialization. Initialization of the state of the memory array 30 with an N-bit string encoding the information to be encrypted proceeds in the same way as in the process for iterative encryption described above. The rule table 10 is initialized with the rule table setter 20 also as described in connection with iterative encryption. Each of the memory elements in the array 70 is initialized with random information in similar manner as the memory 50 was described as being initialized in iterative encryption. As discussed in iterative encryption, similarly random bits are also used to initialize states of memory elements in the array 30. The bits used to initialize memory element i of the memory array 70 are used also to initialize the states of memory elements 30 indexed N+2ri. . . N+2r(i+1)-1. Encryption. Let Q be N+2rn, i.e. the total number of memory elements in array 30 initialized with either information to be encrypted or random information. Indices C and P are defined with initial values C=Q-d and P=N+u-2. A constant J is set to Q-d. Then, for an index j initialized to 0, the following process, in which each processor in the array 60 operates in parallel, stops when j reaches J: The bottom processor obtains a bit b from the element of array 30 that is indexed P, provided that P is greater than or equal to 0, otherwise this bit will not be used and can be set arbitrarily to 0. Each of the middle processors indexed i, and the top processor indexed n-1 obtain a bit b from the 0th-order position of the integer in the element of the memory array 70 indexed i-1. Using the bit b and the integer g in its associated memory element in the array 70, each of the processors in the array 60 obtains a bit f from the rule table 10. If b is 0, then f is the gth entry in the rule table 10, and if b is 1, then f is the (g+R)th entry in the rule table 10. The top processor sets its bit f in the memory element of array 30 that is indexed C. The other processors remain idle during this operation. Each of the processors in the array 60 shifts the integer in the associated memory element in array 70 to the right. Each of the processors in the array 60 sets its bit f in the (2r-1)th position (the high bit) in its associated memory element in the array 70. C and P are each decremented by 1, and j is incremented by 1. At the end of this process, the ciphertext is in the memory array 30, in elements indexed 0. . . Q-1. ITERATIVE DECRYPTION 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 similar apparatus as used in iterative encryption and as shown in FIG. 2. The operation of this apparatus in iterative decryption is explained with reference to FIG. 6. Assume that Q bits of ciphertext have been received by a user B who wishes to decrypt them. Initialization. The Q bits of ciphertext are used to activate the Q elements in the memory array 30 that are indexed 0. . . Q-1. The rule table 10 is initialized with the rule table setter 20 as discussed in the method of encryption. An index K is set to Q+2r and an index j is set to 0. Decryption. Decryption continues over n cycles. Cycle initialization. K is decremented by 2r. K marks the right boundary for the current encryption cycle. The d bits in the integer in memory element 50 are set according to the currently right-most d bits of the ciphertext. An index k is set to K-d. At each cycle the following steps are performed until k is 0: The integer, g in memory element 50 is used to index into the rule table 10, an entry f is retrieved. The kth element of 30 is set to f. The integer in the memory element 50 is shifted right. The dth bit of the integer in memory element 50 is set to the bit in the memory element of array 30 indexed k-1. The index number k is decremented by 1. It will be understood that the described 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 600 looks up from Table 1 the symbol corresponding to each group of 4 contiguous, non-overlapping bits. As a result of these steps, the resulting symbol stream 700 is the same as the symbols input by A. PARALLEL DECRYPTION Parallel decryption is described with reference to FIGS. 7 and 8. 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 these processors is associated with a memory element of an array 90, each of the elements of which can store d bits of information. As described above, the d bits may be considered to represent a d-bit integer. If the number of bits in the ciphertext block is Q, then the array 80 and 90 must each have at least Q elements. While the processor 40 used in iterative decryption can read and write to any element in the array 30, a processor indexed k in the array 80 needs only to be able to read from the elements indexed k-r. . . k+r in the array 30. Such a processor need only to be able to write to the memory element indexed k in the array 30. The arrangement of I/O connections of the processors in the array 80 is shown in FIG. 7. In order to avoid indexing problems near the end of the arrays, these array 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 Q bits of ciphertext just as described above. The rule table 10 is initialized with the rule table setter 20 as described in the steps for encryption. Decryption. Over n cycles each of the processors in array 80 performs the following operations: Each processor indexed k reads d bits from the memory array 30 at positions indexed k-r. . . k+r, and stores these bits as an integer g in its associated memory in the array 90. Each processor retrieves the bit b at index g in the rule table 10. Each processor indexed k sets the memory element that is indexed k in array 30 to b. After n cycles the contents of array 30 are sent to the decoder 600 as in iterative decryption. BANKING EXAMPLE Tables 3 and 4 show the encryption and decryption of an example message using the apparatus described above. In this example a simple message, for example "Y146,00", is sent from A to B. A and B share as a 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.
TABLE 3
______________________________________
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.
Rule Rule
En- De-
crypt
Step I/O crypt
Step I/O
______________________________________
30 0 Y146.00 30 0 8X.0X021.66$X
30 1 4$785YY1 30 1 62X,.8Y95XX12,
30 2 7840.94$ 30 2 XY.3X607.2293
30 3 97 Y36788 30 3 205$25,,5 Y7$
30 4 $4,428977 30 4 3,$1Y6 3.40,
30 5 370 306996 30 5 231X094.X703
30 6 .9Y22081$8 30 6 Y$X.,YY524,
30 7 012X300$373 30 7 012X300$373
30 8 Y$X.,YY524, 30 8 ,9Y22081$8
30 9 231X094.X703 30 9 370 306996
30 10 3,$1Y6 3.40, 30 10 $4,428977
30 11 205$25,,5 Y7$
30 11 97 Y36788
30 12 XY.3X607.2293
30 12 7840.94$
30 13 62X,.8Y95XX12,
30 13 4$785YY1
14 8X.0X021.66$X 14 Y146.00
______________________________________
A variant of the raw display format allows the resistance 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 4
__________________________________________________________________________
This table shows the same steps of encryption/decryption as
table 3. Here, however, the actual state of the processor array is
shown. The plaintext 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.
__________________________________________________________________________
Rule
Encrypt
Step
I/O
__________________________________________________________________________
30 0 111110000010011001010000000010
30 1 00100111111000011010111111111000
30 2 1110000100100000010110010010011101
30 3 100111101101111111000110111000010001
30 4 01110010001100100100000110011110111010
30 5 1100111000001101110000000110100110010110
30 6 001110011111010001000000000110000111000101
30 7 00001000010010111100000000000111110011101100
30 8 1111011110110101001111111111101001000010001101
30 9 010011001000101100001001001001011011111000001100
30 10 11000011011110001111011011011100010100100000001110
30 11 0100000010100111010010100011001110101101111111100111
30 12 101111110101110010110110000011100101010001001001110011
30 13 01100100101100110101000111111001101010111011100001000011
14 0001101101010000101100000100100001010110011001111011110100
__________________________________________________________________________
Rule
Decrypt
Step
I/O
__________________________________________________________________________
30 0 0001101101010000101100000100100001010110011001111011110100
30 1 01100100101100110101000111111001101010111011100001000011
30 2 101111110101110010110110000011100101010001001001110011
30 3 0100000010100111010010100011001110101101111111100111
30 4 11000011011110001111011011011100010100100000001110
30 5 010011001000101100001001001001011011111000001100
30 6 1111011110110101001111111111101001000010001101
30 7 00001000010010111100000000000111110011101100
30 8 001110011111010001000000000110000111000101
30 9 1100111000001101110000000110100110010110
30 10 01110010001100100100000110011110111010
30 11 100111101101111111000110111000010001
30 12 1110000100100000010110010010011101
30 13 00100111111000011010111111111000
14 111110000010011001010000000010
__________________________________________________________________________
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 Tables 3 and 4. This rule is known as rule 60 (table 2, column 5). Note that this minimal difference between keys produces differences throughout the ciphertext produced.
TABLE 6
______________________________________
Propagation of a single error introduced into the plantext.
"-" = site same as with no error "#" = site differs with error.
Rule
En-
crypt
Step I/O
______________________________________
30 0
#---------------
30 1
###-#-----------------
30 2
###-##-##--##-------------------
30 3 ##-##-##---####---------------------
30 4 ##--###--###--#-----------------------
30 5 #--###-##-##--#-------------------------
30 6 #--#-####-#--##---------------------------
30 7
#-#---####--##-----------------------------
30 8
#-#######-#-##-------------------------------
30 9
#-#--#--#-##---------------------------------
30 10
-#---#-#-----------------------------------
30 11
#-###-#-#-------------------------------------
30 12
##-#-#--####---------------------------------------
--###-----------------------------------------
30 14
-###-----#-------------------------------------------
______________________________________
Note that if r is the radius of the rules used, the size of the rule table is 2.sup.24+1, the number of bits required to indexed into the rule table is 2r+1, and the number of different number toggle rules (both left and right) is 2.sup.2.spsp.2r.sup.+1. For clarity, the example encryptions using the preferred embodiment are done using radius 1 rules. It will be understood that 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 provided an acceptable
TABLE 7
__________________________________________________________________________
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
Rule
Encrypt
Step
I/O
__________________________________________________________________________
0
30, 60
1
###----------###--############-
30, 60
2
#-##---######--#--#--#--#--#-#--
30, 60
3
#--#-####-#-#---##-##-###-----##--
30, 60
4
##-##--#----#---#---##--####--#-###
30, 60
5
#-##-######--####-----##-#--######-#-
30, 60
6 #---###--#-##-##-#-#-------##----#-#-#-#--
30, 60
7 #--##-#-##-#---#--##---------#####-#--# -###-
30, 60
8
####--###----##-##-#########-#--#--###-#--
30, 60
9 ##--#--#-##--#--###--#--#--#-##-###---#-#-###-
30, 60
10
-------##-##-###--##-##-###---#-#-----##---#---
30, 60
----##--###-#-#---#-###--##---#-#--####-####-####
30, 60
------#--#-#-#-##--##-#-##-##-------##-#-#--##-##--
30, 60
##---##-#####-#-#-##-#--##-#-#-##--###---##----##-#---
30, 60
#-#----#-#-#-----##-###### --#####-##-######----#-##-###-
__________________________________________________________________________
level of security. At radius 3, there are approximately 4*10.sup.19 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. Address Space will be considered first. A 16-bit processor such as used in personal computers has sufficient address space to use radius 7 rules, of which there are 2.sup.2.spsp.14.sup.+1, roughly 10.sup.5000. 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 2.sup.2.spsp.30.sup.+1. As to memory size, in most situations, 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 2.sup.25 bits of information, and could thus hold the rule table for a radius-12 rule. As there are 2.sup.2.spsp.24.sup.+1 radius-12 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. To obtain an idea of how large rule tables used in actual practice might be, consider that if the rule table for a radius-12 rule were to be written down on paper it would occupy over 4000 printed pages (assuming 8 bits/character, 256 characters/page). By contrast, a 56-bit key such as used in the DES, for instance, would occupy 7 characters under the same circumstances. ALTERNATE EMBODIMENTS In this subsection four alternate embodiments of this invention are described in detail. These alternate embodiments are constructed to illustrate some general features of the invention. They are in particular designed to show that the sequence of specializations used to arrive at the preferred embodiment are not necessary to build an encryption apparatus embodying this invention. ALTERNATE EMBODIMENT 1 The first alternate embodiment uses the logistic map as the underlying dynamical system. The cryptographic key in the embodiment comprises the parameter value of the logistic map, and the number of times n the map is applied during encryption and decryption. In this embodiment encryption involves only inverse iteration, and decryption involves both forward and inverse iteration of the dynamical system. This embodiment shows how the method of the invention can be used for encryption using dynamical systems with continuous variables. It also shows that a single such variable is sufficient to build a working encryption apparatus. A standard form for the logistic map defines the next state x.sup.t+1 of the system in terms of its previous state x.sup.t by x.sup.t+1 =4.lambda.x.sup.t (1-x.sup.t). Here x and .lambda. are real numbers between 0 and 1. There are in general two antecedent states x.sup.t-1 for each state x.sup.t, these are given by ##EQU3## An example of encryption and decryption using the logistic map is shown in Table 8. To encrypt a piece of the input information stream, the piece is encoded as a state of the system, x.sup.0. In the example of Table 8, the part of the information stream to be encoded in the state I/O of the dynamical system is a stream of numbers, representing, say, the amount of money in certain accounts which bank A would like to communicate to bank B. The representation of each piece of the input information stream as a state of the system used in this case is particularly simple. Each digit of the message is placed in the first position to the right of the decimal point of the state, and all other positions set to 0. Alternately, the other positions could be filled with random numbers or some other parts of the input information stream. In the example of Table 8, a single digit "8" is encrypted. During encryption of this state, a sequence of states are generated by iterating backward. At each inverse step, either x.sup.t-1.sub.+ or x.sup.t-1.sub.- is chosen according to information from some portion of the input information stream, this portion could, for instance, contain purely random information. The choice of one of the two antecedent states places information in the dynamical I/O of the dynamical system. In Table 8 choice of x.sup.t-1.sub.+ represents a 0 bit in the dynamical I/O, and choice of x.sup. t-1.sub.- represents a 1 bit in the dynamical I/O. Three runs of encryption are shown. In each run 12 encryption steps are carried out. In each of the three runs the state I/O is the same, but the dynamical I/O is different in each run since it is generated randomly, except for steps 6-8, at which identification information is inserted into the dynamical I/O. Thus each run produces a different ciphertext, as shown at step 12 of the encryption. The receiver of the ciphertext can decrypt the information in the state I/O by applying the logistic map forward in time 12 steps, using the secret key he shares with the sender. The portion of the information stream placed in the state I/O by the sender is recovered from the first digit after the decimal point. To recover the portion of the information stream place in the dynamical I/O by the sender, the receiver uses inverse iteration. At each forward iteration, the receiver computes a state x.sup.t+1 from a state x.sup.t. By inverse iteration, the receiver calculates the two possible antecedent states of x.sup.t+1 and compares each with x.sup.t. If the "-" antecedent state equals x.sup.t then the receiver knows that a 1 bit was placed in the dynamical I/O by the sender, and if the "+" antecedent state equals x.sup.t then the receiver knows that a 0 bit was placed in the dynamical I/O by the sender. In the example of Table 8, the identification information "101" is placed in the dynamical I/O at steps 6-8 of encryption. This identification information could, for instance, give the number of the block being encrypted, to be used during checks for transmission errors. The recovery of both state and dynamical I/O by the receiver of a message encrypted under alternate embodiment 1 is shown in the bottom half of Table 8.
TABLE 8
__________________________________________________________________________
Three runs of encryption/decryption with alternate embodiment 1.
.lambda.: 1.0.
Encryption. Initialized with plaintext for all runs: 8, encoded as 0.8;
The state
at iteration 12 is the ciphertext. Identification information: 101 is
placed in the
dynamical I/O at steps 6-8. Decryption. Initialized with ciphertext at
step 0. The
plaintext "8" is decoded from the state I/O at iteration 12, from the
first digit after
the decimal point. The identification information 101 is read from the
dynamical I/O at steps 7-5.
Encrypt
Run 1 Run 2 Run 3
Step Dynam
State Dynam
State Dynam
State
__________________________________________________________________________
0 0.8000000000
0.8000000000
0.8000000000
1 1 0.2763932023
1 0.2763932023
1 0.2763932023
2 0 0.9253254042
0 0.9253254042
1 0.0746745958
3 1 0.3633667355
1 0.3633667355
1 0.0190308211
4 0 0.8989465078
1 0.1010534922
1 0.0047805590
5 1 0.3410554404
1 0.0259360518
0 0.9988034285
6 1 0.0941229990
1 0.0065266096
1 0.4827042524
7 0 0.9758878547
0 0.9983656766
0 0.8596163746
8 1 0.4223595703
1 0.4797866170
1 0.3126609855
9 1 0.1199867010
0 0.8606290972
1 0.0854704430
10 0 0.9690451202
1 0.3133379372
0 0.9781551937
11 1 0.4120300054
0 0.9143253742
0 0.5738999430
12 1 0.1166039924
0 0.6463511409
1 0.1736182998
__________________________________________________________________________
Decrypt
Run 1 Run 2 Run 3
Step Dynam
State Dynam
State Dynam
State
__________________________________________________________________________
0 0 0.1166039924
0 0.6463511409
0 0.1736182998
1 1 0.4120300054
0 0.9143253742
1 0.5738999430
2 1 0.9690451202
0 0.3133379372
0 0.9781551937
3 0 0.1199867010
1 0.8606290972
0 0.0854704430
4 1 0.4223595703
0 0.4797866170
1 0.3126609855
5 1 0.9758878547
1 0.9983656766
1 0.8596163746
6 0 0.0941229990
0 0.0065266096
0 0.4827042524
7 1 0.3410554404
1 0.0259360518
1 0.9988034285
8 1 0.8989465078
1 0.1010534922
0 0.0047805590
9 0 0.3633667355
1 0.3633667355
1 0.0190308211
10 1 0.9253254042
1 0.9253254042
1 0.0746745958
11 0 0.2763932022
0 0.2763932022
1 0.2763932022
12 1 0.8000000000
1 0.8000000000
1 0.8000000000
__________________________________________________________________________
Alternate Embodiment 2 The preferred embodiment uses dynamical systems with a multiplicity of variables in which the dynamical rule governing the state of each variable is the same and is local in space. This is an embodiment with a dynamical system with a multiplicity of variables in which the connections between the variables are not local and many vary depending on not only on which variable is considered, but also on which step of encryption/decryption is being performed. This embodiment demonstrates that reversible dynamical systems can be used in addition to irreversible systems to encrypt and decrypt according to this invention. In this embodiment, one of the dynamical systems is chosen to be irreversible, the others are reversible. The irreversible system is simply the logistic map of alternate embodiment 1. At each step of encryption/decryption the state of this irreversible dynamical system is globally broadcast to the other dynamical systems. This embodiment thus demonstrates that the connections between variables in a mult-variate dynamical system need not be local in order to embody this invention. Note that the reversible systems do not have a dynamical I/O. Nonetheless, they can participate usefully in encryption since changing interconnections between them, driven by the dynamical I/O of the irreversible dynamical system, serves to diffuse the information in the states of each of them into the states of the others. This embodiment demonstrates further that asynchronous updating can be used to perform encryption/decryption with this invention. Here, at each step, the state of the irreversible dynamical system is updated first, and then the state of the reversible dynamical systems are updated. Table 9 shows the operation of an example of alternate embodiment 2. In this example three simple reversible dynamical systems are connected to the irreversible logistic map. Thus there are 4 variables, v.sub.0. . . v.sub.3. The secret key of the system is a set of four real numbers .lambda..sub.0. . . .lambda..sub.3. The value of v.sub.0 is updated using the logistic map v.sup.t+1.sub.0 =4.lambda..sub.0 v.sup.t.sub.0 (1-v.sup.t.sub.0). The states of the other variables v.sub.i are a function of the value of v.sub.0 and one of the other variables v.sup.j bu the funcaiton v.sup.t+1.sub.i =4.lambda..sub.i v.sup.t.sub.j (1-v.sup.t.sub.o). The pairs {i,j} are chosen such that the state of each variable at time t contributes to the calculation of one and only one variable in the set v.sub.1. . . v.sub.3. These other systems are reversible since given v.sup.t.sub.0, which is independently calculated, the antecedent state v.sup.t.sub.j is given uniquely in terms of the state at time t+1 of the system, ##EQU4## The value of each of the variables v.sub.i at time t+1 depends on the value of 1) the value the variable v.sub.0 at time t, and the value of one other variable at time t. Which other variable v.sub.i depends on may be allowed to vary according to the dynamical I/O to v.sub.0. In the example of Table 9, if a 0 is in the dynamical input of v.sub.0 at time t, then the following relations are used to update the values of v.sub.1. . . v.sub.3 : v.sup.t+1.sub.1 =4.lambda..sub.1 v.sup.t.sub.2 (1-v.sup.t.sub.0) (4) v.sup.t+1.sub.2 =4.lambda..sub.2 v.sup.t.sub.3 (1-v.sup.t.sub.0) (5) v.sup.t+1.sub.3 =4.lambda..sub.3 v.sup.t.sub.1 (1-v.sup.t.sub.0) (6) while if a 1 is in the dynamical I/O of v.sub.0 at time t, then the following alternate relations are used: v.sup.t+1.sub.1 =4.lambda..sub.1 v.sup.t.sub.3 (1-v.sup.t.sub.0) (7) v.sup.t+1.sub.2 =4.lambda..sub.2 v.sup.t.sub.1 (1-v.sup.t.sub.0) (8) v.sup.t+1.sub.3 =4.lambda..sub.3 v.sup.t.sub.2 (1-v.sup.t.sub.0) (9) Encryption and decryption with this embodiment is shown in table 9. There the key values are, .lambda..sub.0 : 1.0, .lambda..sub.1 : 0.9722222, .lambda..sub.2 : 0.73916483275, .lambda..sub.3 : 0.9462346. The plaintext is 6123, encoded as: 0.6, 0.1, 0.2, 0.3. The ciphertext is: 0.6646249811, 0.4047112390, 1.0084771899, 2.0443172127, and the number of encryption/decryption steps is 12. The dynamical I/O to v.sub.0 is recovered during decryption using inverse iteration as in alternate embodiment 1.
TABLE 9
__________________________________________________________________________
Encryption/Decryption with alternate embodiment 2. .lambda. values:
.lambda..sub.0 : 1.0, .lambda..sub.1 :
0.9722222. .lambda..sub.2 : 0.73916483275. .lambda..sub.3 : 0.9462346,
Encryption. Initialized with plaintext
6123, encoded in the state I/O as 0.6. 0.1, 0.2, 0.3. Dynamical I/O:
110101.
Decryption. Initialized with ciphertext state: 0.6646249811,
0.4047112390,
1.0084771899, 2.0443172127. Recovered plaintext decoded from states at
step
12: 6123. Recovered dynamical I/O: 000010010100.
Encrypt
Step Dynamical
.nu..sub.0
.nu..sub.1
.nu..sub.2
.nu..sub.3
__________________________________________________________________________
0 0.6 0.1 0.2 0.3
1 0 0.8162277660
0.3680855879
0.4313030648
0.1399247631
2 0 0.7143433192
0.5106659147
0.1294170151
0.3313438413
3 0 0.7672342983
0.1880490330
0.3760980660
0.5641470990
4 0 0.7412289896
0.4915686649
0.5759939501
0.1868548574
5 1 0.2456522998
0.1675664602
0.2582528147
0.0654484810
6 0 0.9342659612
1.3287811518
0.2630573489
0.6554978228
7 0 0.6281932514
0.2392940406
0.4657953723
0.9189897466
8 1 0.1951202087
0.0764496206
0.1957324618
0.3016621533
9 0 0.9485754650
1.2873338760
1.5498570315
0.3822781157
10 1 0.3866151080
0.5396753700
0.8545889549
0.1646597858
11 0 0.8915944624
2.6662724210
0.4013074876
1.2801345102
12 0 0.6646249811
0.4047112390
1.0084771899
2.0443172127
__________________________________________________________________________
Step
Decrypt
Dynamical
.nu..sub.0
.nu..sub.1
.nu..sub.2
.nu..sub.3
__________________________________________________________________________
0 0.6646249811
0.4047112390
1.0084771899
2.0443172127
1 0 0.8915944624
2.6662724210
0.4013074876
1.2801345102
2 0 0.3866151080
0.5396753700
0.8545889549
0.1646597858
3 1 0.9485754650
1.2873338760
1.5498570315
0.3822781157
4 0 0.1951202087
0.0764496206
0.1957324618
0.3016621533
5 1 0.6281932514
0.2392940406
0.4657953723
0.9189897466
6 0 0.9342659612
1.3287811518
0.2630573489
0.6554978228
7 0 0.2456522998
0.1675664602
0.2582528147
0.0654484810
8 1 0.7412289896
0.4915686649
0.5759939501
0.1868658574
9 0 0.7672342983
0.1880490330
0.3760980660
0.5641470990
10 0 0.7143433192
0.5106659147
0.1294170151
0.3313438413
11 0 0.8162277660
0.3680855897
0.4313030648
0.1399247631
12 0 0.6000000000
0.1000000000
0.2000000000
0.3000000000
__________________________________________________________________________
ALTERNATE EMBODIMENT 3 This alternate embodiment shows one way in which as arbitrary cellular automaton, not necessarily a toggle rule such as is used in the preferred embodiment, may be used to embody the method and apparatus of this invention. It also illustrates the following important points: Both forward and backward iteration can be used in encryption. (It will be appreciated that it has already been shown in alternate embodiments 1 and 2 that both forward and backward iteration can be used during decryption.) The number of either or both forward and backward iterations used in encryption need not correspond to the number of forward iterations used in decryption. Hence this information need not be part of the secret key, or part of a convention. The representation of bits of the input information stream as (part of) a state of the system need not be unique. As shown in this embodiment each bit may typically be represented in many different ways, and the choice may be made according to either random or information-bearing parts of the input information stream. The following facts concerning cellular automata operating on lattices with periodic boundary conditions must be explained before alternate embodiments 3 and 4 can be fully understood. Under forward iteration any configuration on a spatially periodic lattice will eventually enter a temporal cycle. Under most cellular automata there are certain configurations which have no antecedent states. These configurations are known as "Gardens of Eden" since once left they cannot be reentered under forward iteration. Configurations on a periodic lattice can be ordered. Hence, there is a configuration on every temporal cycle which is minimal in this ordering. This is one way in which a particular configuration on a temporal cycle can be distinguished from the others for coding purposes. Alternatively, the distinguished configuration could be the middle configuration of the ordering, or some other function of the ordering. Indeed, some function other than the ordering function could be applied to the configurations on the orbit in order to label them for coding purposes. What is essential for this application is that the orbits may be labeled in some unambiguous way. All distinct temporal cycles that are possible for a given cellular automaton operating on a spatially periodic lattice of a given size can be found; for instance, by finding the periodic orbit arising from the application of the cellular automaton to every possible initial configuration. All the configurations on a spatially periodic lattice can be organized into a collection of trees rooted on the temporally periodic cycles. The leaves of the trees are the Gardens of Eden, the branches of the trees consist of configurations which can be mapped both forward and backward in time. Configurations on the temporal cycles map to themselves after some number of forward iterations and/or some number of backward iterations. Configurations on the branches, by contrast, do not map to themselves under either forward or backward iteration.
TABLE 10
______________________________________
Lookup tables of cellular automaton rule 22, used as an
example key in alternate embodiments 3 and 4. Top: forward
iteration table, Bottom: inverse iteration table.
Forward
index x.sub.i-1.sup.t x.sub.i.sup.t x.sub.i+1.sup.t
x.sub.i.sup.t+1
______________________________________
0 000 0
1 001 1
2 010 1
3 011 0
4 100 1
5 101 0
6 110 0
7 111 0
______________________________________
Inverse
x.sub.i.sup.t x.sub.i+1.sup.t
x.sub.i.sup.t+1
x.sub.i-1.sup.t
______________________________________
00 0.1 0.1
01 0.1 1.0
10 0.1 1.0
11 0.1 branch, terminate
______________________________________
Initialization. To begin sending encrypted messages using this embodiment, two entities A and B share a secret which is comprised of 1) a cellular automaton rule, and 2) the size of the periodic lattice on which the cellular automaton operates. As in all of these embodiments, A and B must also agree on conventions for how the information stream is to be represented as states of the system, but these conventions need not be kept secret. In the example shown in Tables 11-13, the secret key is the system size 23, and the nearest-neighbor cellular automaton rule under which the neighborhoods 100,001, and 010 map to 1, and all other neighborhoods map to 0. In the standard nomenclature for cellular automata, this rule is known as rule 22. Note that rule 22 is not a left-toggle rule since both 011 and 111 map to 0, and it is not a right-toggle rule since both 110 and 111 map to 0. Table 10 (top) is a lookup table describing how to iterate rule 22 forward in time. A configuration of 0's and 1's is updated according to rule 22 by reference to this table as follows. For each site indexed i, the states of the cells in its neighborhood, in this case the sites indexed i-1, i, i+1 are found. The sequence of cell states in the neighborhood is treated as the binary expansion of an integer index into the table. The entry in the third column of that table at the row given by the index is the state of the site i at the next time step. To each forward-iteration table, there is an inverse-iteration table, which is a reorganization of the information in the forward iteration table. The inverse iteration table for rule 22 is given in Table 10 (bottom). This inverse iteration table can be used to inverse iterate configurations on either periodic or non-periodic lattices. In this embodiment the lattice is periodic (so that, for instance, the site indexed N+1 is identified with the site indexed 1). To construct an antecedent state (at time t) for a configuration (at time t+1) on such a lattice, a site is chosen to be the initial site and is indexed N. The two sites to the right of the site N (sites indexed 1 and 2) in the antecedent state (the state at time t) are chosen according to information from the input information stream. These sites could, for instance, be assigned values at random. Then, for each site indexed i=N down to i=1: By reference to column 1 of Table 10 (bottom), the two site values at time t and indexed i and i+1, are used to determine which row of the table to use to find the state at time t of the site indeed i-1. If the site indexed i in the configured at time t+1 is 0 or 1 then the value from the left respectively right subcolumn of column 3 is used to find the state for the site indexed i-1 at time t. Notice that the fourth row contains the entries branch, terminate. If a branch entry is encountered, both possibilities, 0 and 1, must be considered. The state at time t constructed up to that point is recopied twice into a store, one copy is augmented with a 0, the other with a 1, and the process of building an antecedent state is continued on both copies. If a terminate entry is encountered, then there is no possible way to continue building an antecedent state, given the part built thus far. The effort is therefore abandoned. If need be, an antecedent state is reinitialized with new information from the input information stream and the process restarted. After all sites have been assigned values in each of the copies produced, boundary conditions must be checked. Since the lattice is periodic, it must be checked if the values assigned to the sites N and N+1 are consistent under the cellular automaton rule with the given state at time t+1. If the site values are not consistent, then the presumptive antecedent state constructed above is not valid. If the configuration at time t is not a Garden or Eden, that is, if it does in
TABLE 11
______________________________________
Minimal representatives of the spatio-temporal orbits of nearest-
neighbor cellular automaton rule 22 operating on system size 23.
Codes for 0 Codes for 1
______________________________________
00000000000000000000000
00000001010000110010011
00000000000000010000001
00000000001000001000101
00000000001010001000001
00000000111100000001111
______________________________________
fact have at least one antecedent state, then the above process will find one or more of the antecedent states, given enough random initial starts. Initialization. Before messages are sent, both A and B find all of the temporal cycles of rule 22 operating on a lattice of size 23. They have agreed beforehand that configurations are to be ordered like binary numbers, e.g. 00000000000000000000000<00000000000000000000001 etc. so that on each temporal cycle, taking into account all possible spatial shifts, there is one configuration which is the minimum on the cycle. A and B find that the minimum representative configuration on each of the distinct orbits are as given in Table 11. A and B agree further that if the sum of the rightmost three digits in a minimal representation of an orbit is 0 or 1, then the configuration will be used to encode 0, and if the sum is 2 or 3, then the configuration will be used to encode 1. Hence, each of the 4 configurations in column 1 of Table 11 can encode 0, and each of the three configurations in column 2 of Table 11 can encode 1. A first picks a number at random from the set 1, 2, 3, 4, and uses that number to decide which of the four configurations representing 0 to use. In table 12, A has chosen 4, and hence represents the 0 bit as the configuration 00000000001010001000001. A then begins to inverse iterate the configuration. He decides that if a Garden of Eden is encountered, he will forward iterate 10 steps, and that if ever he is able to complete 5 inverse iterations in a row before a Garden of Eden is encountered, he will stop encrypting, and send the ciphertext. B does not need to know about these decisions, or any other detail of the operations performed by A during encryption, beyond the fact that the secret key was used. In Table 12, the configurations generated in the course of encryption by A are shown. Only the last of the 10 configurations generated at each forward iteration phase is shown. Between steps 25 and 29, 5 inverse iterations in a row are performed, so A stops encrypting and sends the ciphertext 01000101001011001011011. Decryption. B receives the ciphertext 01000101001011001011011 from A. Rule 22 is applied forward in time until a configuration is generated which is a shift in space (in a circular register of size 23) of one of the configurations in Table 11. The configurations generated by B are shown in Table 13. At the second step, a configuration is generated with is a shift of the configuration in the first column, 4th row of Table 11. Hence, a 0 bit has been decrypted. It will be appreciated that the intermediate states produced during encryption need not be related to the intermediate states produced during decryption. The use of cycles of a dynamical system as code words has been expressed here in terms of cellular automata. However, since continuous dynamical systems simulated in finite-precision hardware also have state spaces composed of trees rooted on cycles, this approach to embodiment of the invention can be taken with continuous dynamical systems as well.
TABLE 12
______________________________________
encryption with alternate embodiment 3. F: forward iteration,
I: inverse iteration. The last column gives the total number
of antecedent states for each configuration in column 3.
step direction configuratin antecedents
______________________________________
0 00000000001010001000001
31
1 I 11110111101010110000000
0
2 F 10111000011100000001101
6
3 I 00010000001000000000101
21
4 I 01100000000111101110101
0
5 F 00000011111101110001110
8
6 I 11011100100101001110010
0
7 F 00010100010000001000000
21
8 I 11010101100000000110111
0
9 F 00111000000011111101110
8
10 I 00010000000001001000100
17
11 I 11100000000000110000011
48
12 I 01000000000000010111010
0
13 F 01010001000001000000000
31
14 I 10001110000000110111101
1
15 I 00000100000000010100101
6
16 I 11110101101101100011000
0
17 F 00110110111000111000000
8
18 I 00010100010000010000000
31
19 I 11100011010111010111011
0
20 F 00111000000011011011100
6
21 I 11001011011010001010011
0
22 F 00000000010100010000010
31
23 I 11011011010101100000001
0
24 F 01110000111000000011011
6
25 I 00100000010000000001010
21
26 I 11000000001101101110001
8
27 I 10000000000101000100000
31
28 I 01101101111000111000000
2
29 I 01000101001011001011011
0
______________________________________
ALTERNATE EMBODIMENT 4 This alternate embodiment is similar to alternate embodiment 3. For illustrate purposes, it uses the same dynamical system as alternate embodiment 3. This embodiment differs from alternate embodiment 3 in that both encryption and decryption use only forward interation. Thus, this embodiment illustrates that even when irreversible dynamical systems are used, forward iteration alone can suffice to embody the invention. Notably, the advantage of the invention of associating many ciphertexts to a given plaintext which is due to the use of irreversible dynamical systems is retained in this embodiment. An advantage of this embodiment over alternate embodiment 3 is that in this embodiment the statistical properties of the ciphertext can be easily and explicitly specified, while this is difficult in alternate embodiment 3. Since only forward iteration is used during encryption in this embodiment, the dynamical I/O is not used to store and encrypt any portion of the information stream. As in alternate embodiment 3, assume that two users A and B share the secret information that the nearest-neighbor cellular automaton rule 22 operating on system size 23 is to be used for encryption and
TABLE 14
______________________________________
Catalog of configurations coding for 0 and 1,
for use in encryption in alternate embodiment 4.
Codes for 0 Codes for 1
______________________________________
00000010010010010110011
00001110001110000010000
00001001101100101111100
00010001100000110111011
00001011101011111100110
00010001100000110111011
00100000000111010000110
00011111111001111010010
00101011110101100001000
00101100110110000100100
01000110101110111100111
00111010101000100110100
01001100010100100111101
01000000010010010100001
01011011101001011110001
01110010100111101110101
10000001010110101000010
01111001000011010111111
10001100000101011110011
01111101101110001111101
10011011000000010101111
10010101110110011101110
10100101101001101111010
10010110110100100010101
10110110101111000011100
10101111110011101111101
11000100110001100111011
10110001100110111110111
11111010100010101101110
11000010011001000100100
11111111101010010001111
11111000010110111110000
______________________________________
decryption. The same convention concerning the interpretation of the periodic orbits of this system are in force. To begin, we assume that both A and B have found the minimal representatives of the periodic orbits of this rule operating on a system of this size, as in Table 11. Initialization. Before encrypting a message to B, A first makes a large catalog of random 23-bit strings. To each of the strings in the catalog, he assigns a label either 0 or 1. The label for each string is determined by 1) applying the rule 22 to the string until a periodic orbit is encountered, 2) finding the minimal representation of the orbit encountered, and then 3) determining from Table 11 if this minimal representation corresponds to a 0 or a 1. An example catalog constructed in this way is shown in Table 14. Encryption. A can send an encrypted 0 bit to B by selecting at random a 23-bit string that is labeled 0. In the example considered here, he selects the 13th entry in column 1, table 14: 10110110101111000011100. Decryption. B, upon receiving the random bit string, 10110110101111000011100, forward iterates the cellular automaton rule 22 to find a cycle, finds the minimal representative of the cycle, and finds the label of the minimal representative from Table 11. These operations decrypt the random bit string. The sequence of operations performed by B is shown in Table 15. After forward iterating the string received from A 28 times, B finds that a configuration has been generated twice (at steps 20 and 28) and hence knows that a cycle (of length 8) has been entered. The minimal representative of the cycle is then found. In this example the minimal representative is generated at step 23 of the decryption. In general, the minimal representative will be a shift of one of the cycle configurations generated during the forward iteration operation. By examination of Table 11, B finds that this minimal representative codes for 0.
TABLE 15
______________________________________
Decryption of the block 10110110101111000011100 in alternate
embodiment 4. A cycle of length 8 is entered at step 20. The
minimum representative of the orbit: 00000000000000010000001
is produced at step 23. By reference to table 11, it codes for "0";
Step Configuration
______________________________________
0 10110110101111000011100
1 10000000100000100100011
2 01000001110001111110100
3 11100010001010000000110
4 00010111011011000001000
5 00110000000000100011100
6 01001000000001110100010
7 11111100000010000110111
8 00000010000111001000000
9 00000111001000111100000
10 00001000111101000010000
11 00011101000001100111000
12 00100001100010011000100
13 01110010010111100101110
14 10001111110000011100001
15 01010000001000100010010
16 11011000011101110111111
17 00000100100000000000000
18 00001111110000000000000
19 00010000001000000000000
20 00111000011100000000000
21 01000100100010000000000
22 11101111110111000000000
23 00000000000000100000001
24 10000000000001110000011
25 01000000000010001000100
26 11100000000111011101110
27 00010000001000000000000
28 00111000011100000000000
______________________________________
THE DYNAMICAL I/O In the preferred embodiment using left-toggle rules, the dynamical I/O comprises the right-most 2r processors at each step of encryption/decryption. In the simplest mode or operation of this embodiment, the dynamical I/O is used merely as a place to load random information during the encryption process. In some applications, it may be desirable to reverse part of the dynamical I/O to hold non-random information, such as, for example, an auxiliary message. This auxiliary message can be loaded into the dynamical I/O during encryption and recovered from there during the decryption process. Indeed, in some embodiments, it is possible to encode all meaningful information to be encrypted into the dynamical I/O, and choose the initial states of the dynamical systems purely at random. In order to use the dynamical I/O to process non-random information, some modifications to the overview presented in FIG. 1 are necessary. Referring now to FIG. 9, these modifications are shown. These modifications involve the installation of two new parts 1) a distributor to the state and dynamical inputs 800, and 2) a collator from the state and dynamical outputs 900. Just as the pairs of parts (300, 600) and 400, 500) execute processes which are inverses of each other, the distributor 800 performs an operation during encryption which is undone during decryption by the collator 900. Several different application of these parts will be discussed below. The optimal hardware configuration for these these parts depends highly on the application. In some cases, they can be embodied simply as a look-up table in read-only memory; in others, some (low-level) computations must be performed as well. As an example of a very simple use of the dynamical I/O to process non-random information, consider again the application to international band communication. Imagine that blocks to be encrypted always contain a string of numbers. Either all of these number represent dollar amounts, or all of these number represent yen amounts. Rather than redundantly transmitting the dollar or yen symbol in front of each number, a dollar/yen bit can be set in the dynamical input by distributor 800, and read for the dynamical output by collator 900. The rest of the bitss in the dynamical input may be set with random bits from the noise generator 200, as previously described. In other applications, the dynamical input may contain an address to which the message in the state I/O should be sent upon decryption, a time-stamp, or other identifying information. For example, in an application to digital television encryption, the state I/O could contain the visual information, and the dynamical I/O the auditory information. The parameters of the encryption can always be adjusted such that non-random input to the dynamical I/O does not compromise in any way the security of the information in the state I/O. It will also be appreciated that with the system described here, encryption information may be included in the dynamical I/O, the original state information, or both. The information to be encrypted will therefore be defined as the information stream regardless of where the information is to be encrypted in accordance with the selected embodiment of the invention. SELF-SYNCHRONIZED KEY STREAMS An important use of the dynamical I/O is in self-synchronized stream encryption. In the self-synchronized stream mode, each block of plaintext is encrypted and decrypted with a different, generally random, key. The first block in the stream is encrypted and decrypted using the secret key. The key for encryption/decryption of a subsequent block is placed in the dynamical I/O during encryption of a previous block or blocks. During decryption, the key for the subsequent block is read from the dynamical I/O during decryption of the previous block or blocks. This method of stream encryption is called | ||||||