Linear feedback shift register
|
|
A linear register is a shift register whose input is the exclusive-or (xor) of some of its outputs. The outputs that influence the input are called taps. A maximal LFSR produces an n-sequence, unless it contains all zeros. The tap sequence of an LFSR can be represented as a polynomial mod 2 - called the feedback polynomial. For example, if the taps are at the 1st, 3rd, 4th and 6th bits (as below), the polynomial is <math>x^{16} + x^{5} + x^3 + x^2 + 1<math>. If this polynomial is primitive, then the LFSR is maximal.
Lfsr.gif
Image:lfsr.gif
LFSR's can be implemented in hardware, and this makes them useful in applications that require very fast generation of a pseudo-random sequence, such as direct-sequence spread spectrum radio.
Given an output sequence you can construct a LFSR of minimal size by using the Berlekamp-Massey algorithm.
A Galois LFSR, or a LFSR in Galois configuration is a variation on typical LFSR design. In Galois configuration, the output is individually xor'ed with each tap, before becoming the new input. Galois LFSRs do not concatenate every tap to produce the new input, thus it is possible for each tap to be computed in parallel, increasing the speed of execution.
Use in cryptography
LFSRs have long been used as a pseudo-random number generator for use in stream ciphers (especially in military cryptography), due to the ease of construction from simple electromechanical or electronic circuits, long periods, and very uniformly distributed outputs. However the outputs of LFSRs are completely linear, leading to fairly easy cryptanalysis. Three general methods are employed to reduce this problem in LFSR based stream ciphers:
- Non-linear combination of several bits from the LFSR state;
- Non-linear combination of the outputs of two or more LFSRs; or
- Irregular clocking of the LFSR.
Important LFSR-based stream ciphers include A5/1, A5/2, and the shrinking generator.