비선형 수축생성기의 분석

Abstract

Linear Feedback Shift Register(LFSR)s produce sequences having large periods and good statistical properties, and are readily analyzed using algebraic techniques. But the output sequences of LFSRs are also easily predictable, if we know a proper successive sequence of the sequences. Cellular Automata(CA) is a discrete dynamical system, which consists of a uniform array of memories called cells. The states of cells in the array are updated according to a rule : the state of a cell at a given time depends only on its own state and the state of its neighbors at the previous step. Since CA has a simple, regular, modular and cascadable structure, it is useful for hardware implementation for VLSI. In this paper, we propose a new shrinking generator which is called LCSG(Shrinking Generator based on LFSR and CA) using an LFSR with control register and CA with generator register. The proposed shrunken sequences generated by LCSG have longer periods and high complexities than the shrunken sequences generated by the known method. And we analyze the generated sequences using LCSG. Also, we propose a method for recovering the original sequence from intercepted bits by analyzing phase shifts of the output sequence using the properties of sequences generated from control register.