Random Numbers with LFSR (Linear Feedback Shift Register) - Computerphile

TL;DR

Linear feedback shift registers (LFSRs) are simple in structure but can produce complex output, making them useful in random number generation and cryptography.

Transcript

well i thought we'd talk about something um which you know i've been looking into anyway because um a part of my cryptography teaching but it's the linear feedback shift register now what i really like about them is it's unbelievably simple in structure and yet it can produce incredibly complicated seemingly output which i think is really really co... Read More

Key Insights

• 💄 Linear feedback shift registers (LFSRs) are simple structures that can generate complex and seemingly random output, making them valuable in various applications.
• 🐬 LFSRs are commonly used in random number generation due to their ability to produce statistical randomness similar to flipping a coin.
• 🚱 While LFSRs are not cryptographically secure on their own, they can be part of more advanced encryption schemes, such as combining multiple LFSRs in a non-linear fashion.
• 🪘 The length of an LFSR determines its maximum period, with longer registers able to produce longer periods and a larger number of unique output sequences.
• 🪈 Mathematical methods can be employed to choose optimal tap configurations in order to maximize the period of an LFSR.
• 🎴 In hardware implementations, LFSRs are highly efficient and low-power, making them suitable for applications like smart cards.
• 📱 LFSRs have found use in various encryption systems, including mobile phone encryption and the Trivium cipher.

Questions & Answers

Q: What is a linear feedback shift register (LFSR)?

An LFSR is a structure composed of bits that produces output by shifting the bits to the right and applying a linear feedback function to determine the new bit. This process repeats to generate a sequence of bits.

Q: What are the applications of LFSRs?

LFSRs are commonly used in random number generators due to their ability to produce sequences that appear random. They also find use in cryptography, particularly in stream ciphers, where they contribute to generating secure and unpredictable keys.

Q: How does the length of an LFSR affect its output?

The length of an LFSR determines the maximum period it can produce. For an n-bit LFSR, the maximum period is 2^n - 1, as it covers all possible combinations of 0s and 1s except for the all 0s state.

Q: Can LFSRs be used as a secure encryption method?

LFSRs alone are not secure for encryption purposes since their output can be reverse-engineered if a significant portion of the stream is known. However, combining multiple LFSRs in a non-linear way can enhance security and create robust encryption algorithms.

Summary & Key Takeaways

• Linear feedback shift registers (LFSRs) are simple structures composed of bits that can produce highly complex output.

• LFSRs are commonly used in random number generators and as elements in stream ciphers for cryptography.

• The length of an LFSR determines the maximum period it can produce, with longer registers capable of producing longer periods.