next up previous contents
Next: Rule Application Up: Diffusion Phase Previous: Diffusion Phase

Rule Generation

CA-1.0 uses radius-5 toggle cellular automata for its diffusion phases. These toggle rules are specified by the 1024-bit block key. From these block key bits both a left- and a right-toggle rule are generated. The left-toggle rule is generated by reading the block key bits from the left, and the right-toggle rule is generated by reading the block key from the right. Each key bit is used to set two bits in a CA rule table, in such a way as to enforce the toggle property.

For left-toggle rules this means that the second half of the rule table is the bitwise complement of the first half. For right-toggle rules, the result of every odd-numbered neighborhood is the complement of the even-numbered neighborhood one less. For example, for radius-1 rules, the key 0111 generates the left-toggle rule 30 of column 2, table 1, and the right-toggle rule 149 of column 3, table 1.

The keys for CA-1.0 are completely arbitrary but for the imposition of a balance condition. A key is balanced if it has the same number of 0- and 1-bits. This condition is imposed to avoid weak encryption keys such as the rule which mearly shifts blocks. The balance condition is trivially imposed and reduces the number of independent bits in the key only slightly.



Howard A. Gutowitz
Fri May 12 06:16:18 MDT 1995