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.

Feedback Shift Register

    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: