A New Design Method Of Feedback With Carry Shift Register And Its Application

Feedback with Carry Shift Register (FCSR) is a kind of pseudo-random se-quence generators introduced by Klapper and Goresky in1993. Since FCSRs are very similar to classical Linear Feedback Shift Registers (LFSRs) and FCSR sequences are of high linear complexity naturally, they have been proposed as a better alternative to LFSRs in stream cipher designs.FCSRs have two traditional representations. They are the Fibonacci and the Ga-lois representations. The Galois representation is more efficient than the Fibonacci representation, because the feedback computations of it are performed in parallel. By using a filter on the cells of a Galois FCSR automaton, hardware stream cipher F-FCSR family were proposed by F. Arnault and T. P. Berger et. al. However, these stream ciphers were exposed to a very powerful attack, i.e., LFSRization attack. Then, a new representation of FCSR called Ring representation has been introduced for re-sponding to the LFSRization attack. Moreover, the Ring FCSRs have been generalized through particular automata called2-adic automata.This dissertation studies some2-adic automata which can be implemented by hardware. The first part focuses on the Ternary FCSR, a special kind of2-adic au-tomata which is suitable for building hardware oriented FCSRs. The main results are as follows:1. Given an negative odd integer q, an algorithm to construct a Ternary FCSR with a critical path of length1and fan-out2is shown.2. The safety of Ternary FCSRs is analysed. A kind of Ternary FCSRs called "defective Ternary FCSR" is presented. They may be of LFSRization in successive clock cycles. Furthermore, a method for improving the safety of "defective Ternary FCSRs" is proposed.3. A preliminary method of constructing Ternary FCSRs for the hardware F-FCSR design is proposed.In the second part of this dissertation,2-adic Finite State Machines (2-adic FSMs) are considered.2-adic FSM is a type of2-adic automata which can be im-plemented by circuits. The coefficients of a2-adic FSMs are restricted to be in Z(2) rather than in Z2for dealing with finite memory. A new implementation method of2-adic FSMs is presented. Less registers are used in this method than in the previous method.