Recently, we looked at a simple LFSR and how it works.

1. Shift the bits
2. XOR some of the bits together; we call these the taps
3. Replace a bit with the XORed value.
4. Repeat

Easy peasy.

I’ve long been fascinated by the Sound Interface Device (SID) in the Commodore 64, mostly because you can use it to get random numbers.

But how does it work?

The Commodore 64 SID LFSR is 23-bits. It’s a maximal length LFSR, which means it will cycle through all 8,388,608 numbers before repeating. It’s often used to generate random numbers in games. Or if you’re nuts, you can use it to do cryptography on a Commodore 64. Who would ever do that?

What is an LFSR?

An LFSR is a Linear Feedback Shift Register. It’s a simple way of generating a sequence of numbers that look random.

Used in cryptography and in generating pseudo-random numbers, they are interesting because they are so simple. Shift bits and feed a few of them back into the sequence. That’s it.

Important note: LFSRs are not cryptographically secure on their own. ESPECIALLY 8-bit LFSRs. More on that in the next post on this topic.