Computer Security and Cryptography

8.2 FEEDBACK SHIFT REGISTERS

A finite state machine (FSM) [Mealy, 1955] consists of finite sets of (internal) states {s}, input and output alphabets {a} and {b}, an output function T determining the output

and a state function Σ determining the successor state.

Given an initial internal state s₀, and sequence of input states a₀, a₁, …, the functions T and Σ determine the output sequence b₀, b₁, …, according to the recursion

Figure 8.1 Feedback shift register.

Figure 8.1 depicts a feedback shift register (FSR) with feedback function f, an FSM with null input consisting of N stages (each capable of storing one bit), a feedback register, and a single output port, where

• The content of Stage i at time t is s_i(t) = 0 or 1,
• The output s₀(t) is the content of Stage 0 at time t,
• The state of the FSR at time t is the N-vector s(t) = (s₀(t), s₁(t), …, s_N−1(t)) ∈ (where is the set of 2^N vectors ...