What is your oppinion on the security of this system. Any obvious flaws? http://www.santafe.edu/~hag/ca11/ca11.html A Massively Parallel Cryptosystem Based on Cellular Automata Howard Gutowitz ESPCI; Laboratoire d'Electronique 10 rue Vauquelin; 75005 Paris, France [EMAIL PROTECTED] The DES is an example of an iterated cryptosystem, a cryptosystem in which a function is applied many times to a message in order to encrypt it. From the physicists point of view, an iterated cryptosystem is an example of a dynamical system, a system whose state evolves over time. Dynamical systems theory encompasses the study of a wide range of phenomena, chaos being the most well known. Some of these phenomena have correlates in cryptography, and can be used as the basis of cryptographic schemes. A certain type of dynamical system, called cellular automata, are particularly well suited for cryptographic application. A cellular automaton is a discrete dynamical system. Space, time, and the states of the system are discrete. Each point in a regular spatial lattice, called a cell, can have any one of a finite number of states. The states of the cells in the lattice are updated according to a local rule. That is, the state of a cell at a given time depends only on its own state one time step previously, and the states of its nearby neighbors at the previous time step. All cells on the lattice are updated synchronously. Thus the state of the entire lattice advances in discrete time steps. Since the update rule is simple, local, and discrete, it can be executed in easily-constructed massively-parallel hardware at extraordinary speeds, without round-off errors. I have developed a cryptosystem, called CA-1.1, which illustrates some of the principles of encryption with cellular automata. In CA-1.1, a message is encoed as a state of the system, and various cellular automaton rules applied to it to produce a new state which is the ciphertext. To decrypt, the same cellular automaton rules are applied in reverse order. The cellular automata employed are derived from a secret key. CA-1.1 uses both reversive and irreversible cellular automaton rules. Under a reversible rule, each state of the lattice comes from a unique predecessor state, while under an irreversible rule, each state can have many predecessor states. During encryption, irreversible rules are iterated backwards in time. To go backward from a given state, one of the possible predecessor states is selected at random. This process can be repeated many times. Backward iteration thus serves to mix random information with the message information. CA-1.1 uses a particular kind of partially linear irreversible rule which is such that a random predecessor state for any given state can be rapidly built. Reversible rules are also used for some stages of encryption. The reversible rules (simple parallel permutations on sub-blocks of the state) are fully non-linear, while the irreversible rules are partially linear. The irreversible rules are derived entirely from information in the key, while the reversible rules depend both on key information and on the random information inserted during the stages of encryption with irreversible rules. CA-1.1 features an authentication mechanism which renders chosen-ciphertext attack difficult. This authentication mechanism ensures that only ciphertext produced by the system loaded with a given key is decrypted using the same key. CA-1.1 is built around a block-link structure. That is, the processing of the message block is partially segregated from the processing of the stream of random information inserted during encryption. This random information serves to link stages of encryption together. It can also be used to chain together the encryption of a stream of blocks. The information in the link is generated within the encryption apparatus. It is not accesible even to legitimate users of the system, hence it is not available for chosen-plaintext attacks. A detailed explanation of how CA-1.1 works can be found in references [1,2]. Further details, as well as U.S. licensing information can be obtained from the author at the above address. References: [1] H. Gutowitz, "Method and Apparatus for Encryption, Decryption, and Authentication using Dynamical Systems", U.S. patent application (100 pg. 1992) [2] H. Gutowitz, "Cryptography with Dynamical Systems" to appear in: "Cellular Automata and Cooperative Phenomena", Eds: E. Goles and N. Boccara, K. Reidel Press (38 pg. 1993)
