Linear-feedback shift register
(also linear feedback register, LFR, LFSR)
Linear-feedback shift register definition
A linear-feedback shift register (LFSR) represents a digital sequence-based mechanism employed in a range of applications such as cryptography, error identification and rectification, and the generation of pseudorandom numbers. This register comprises multiple flip-flops (data storage elements) linked together in a sequence, where feedback is supplied through a linear function based on the states of each individual flip-flop.
See also: ciphertext
Linear-feedback shift register examples
- Stream ciphers: LFSRs are commonly used in stream ciphers, where they generate a pseudorandom sequence of bits that is XORed with the plaintext to create ciphertext.
- Cyclic redundancy checks (CRCs): LFSRs are used in CRCs to detect errors in digital transmissions by calculating a check value based on the data being transmitted.
- Pseudorandom number generators: LFSRs can be used to generate pseudorandom number sequences with long periods and good statistical properties.
Comparisons and advantages
Compared to other digital circuits, LFSRs are relatively simple, compact, and fast. They can generate long pseudorandom sequences with low power consumption. However, the output is deterministic and can be predicted if the initial state is known, which may make LFSRs unsuitable for some cryptographic applications.
Tips for using LFSRs
- Choose an appropriate feedback polynomial to achieve a long sequence period and good statistical properties.
- Ensure that the initial state is non-zero to avoid generating an all-zero sequence.
- For cryptographic applications, consider combining LFSRs with other cryptographic primitives to enhance security.