Cryptography
 Computer Science Computer Catlog Cryptography Catlog

 Caesar Cipher Digital Signature Public key cryptography Symmetric vs. public-key Key Management Stream Ciphers Self-Synchronizing Ciphers Feedback Shift Registers Modes of Operation Multiple Encryption Transposition Ciphers Substitution Ciphers Poly-alpha Substitutions Poly-alpha Cipher Machine Cryptanalysis Ciphers Data Encryption Standard DES Algorithm IDEA Algorithm RC5 Algorithm RSA Encryption Rabin Encryption ElGamal Encryption MD4 & MD5 Secure Hash Algorithm Kerberos Authentication Diffie-Hellman protocols Key Management Life Cycle

## Feedback Shift Registers

Feedback shift registers, in particular linear feedback shift registers, are the basic components of many keystream generators.

### Linear feedback shift registers

Linear feedback shift registers (LFSRs) are used in many of the keystream generators that have been proposed in the literature. There are several reasons for this:

1. LFSRs are well-suited to hardware implementation.

2. They can produce sequences of large period.

3. They can produce sequences with good statistical properties.

4. Because of their structure, they can be readily analyzed using algebraic techniques.

A linear feedback shift register (LFSR) of length L consists of L stages (or delay elements) numbered 0; 1; … ; L - 1, each capable of storing one bit and having one input and one output; and a clock which controls the movement of data. During each unit of time the following operations are performed:

(i) The content of stage 0 is output and forms part of the output sequence.

(ii) The content of stage i is moved to stage i - 1 for each i, 1 <= i <= L - 1.

(iii) The new content of stage L - 1 is the feedback bit sj which is calculated by adding together modulo 2 the previous contents of a fixed subset of stages 0; 1;... ; L - 1. In figure, each ci is either 0 or 1; the closed semi-circles are AND gates; and the feedback bit sj is the modulo 2 sum of the contents of those stages i, 0 <= i <= L - 1, for which C L - i = 1.

The LFSR of is denoted hL;C(D)i, where C(D) = 1+c1D + c2D2 + ... + cLDL € Z2[D] is the connection polynomial. The LFSR is said to be nonsingular if the degree of C(D) is L (that is, cL = 1). If the initial content of stage i is si €{0,1} for each i, 0 < i < L - 1, then [sL - 1; .... ; s1; s0] is called the initial state of the LFSR.

If the initial state of the LFSR in Figure 6.4 is [sL - 1; .... ; s1; s0], then the output sequence s = s0; s1; s2; .... is uniquely determined by the following recursion:

sj = (c1sj - 1 + c2sj - 2 + ... + cLsj - L) mod 2 for j >= L: