Pseudorandom Number Generation using LFSR
A few essays back, we saw how pseudo-random numbers are generated using Cellular Automaton - Rule 30. This essay takes a detailed look into random number generation using LFSR - Linear Feedback Shift Registers. LFSR is widely adopted to generate random numbers on microcontrollers because they are very simple, efficient, and easy to adopt both hardware and software.
Pseudo-random Number Generators
A pseudo-random number generator produces numbers that seem aperiodic (random) but are deterministic. It uses a seed value and generates a sequence of random numbers as a function of the current state and some previous states.
These are pseudo-random (not truly random) because the following numbers can be determined algorithmically if the seed value is known. True random numbers are either generated using hardware or from natural phenomena like blood volume pulse, atmospheric pressure, thermal noise, quantum phenomenon, etc.
What is LFSR
A linear feedback shift register is a collection of bits that shifts when triggered, and the next state is a linear function of its previous state. We use right-shift (>>) as the shift operation and XOR (^) as the linear function to generate the next state of the register.
The LFSR is initiated with a random value called a seed. The next state of the register can be computed deterministically using its previous state and the mentioned operations.
LFSR in action
A series of latches (bits) connected to the next in line forming a chain is called a register. The diagram below shows an 8-bit shift register that shifts to the right upon an impulse. The rightmost bit that is thrown out during the shift is the output bit.
When the shift happens, the leftmost latch gets vacant, and it is either
filled with the output bit forming a circular shift register
filled with zero, like a pure right shift operation of a programming language
filled with a result of some boolean logic on the latches
LFSR that we used to generate pseudo-random numbers goes with the third approach and applies a boolean XOR on a set of chosen latches, called taps, and puts the resultant bit in the leftmost latch, creating a Linear Feedback.
A simple 4-bit LFSR
An LFSR has 3 configurable parameters
number of bits in the register -
ninitial n-bit seed value -
seedposition of taps for XOR -
taps
We build a simple 4-bit LFSR with a seed value of 0b1001 and tap position of 1. The output bit will be the rightmost bit of the register, and the next state of the LFSR will be computed as the
XOR the output bit with the bit in the
1st position (indexed at 0) from the rightshift the bits of the register by one to the right
set the vacant leftmost bit with the output of the XOR operation
After all the above operations are completed, the set of bits in the LFSR becomes the current state and is then used to output the next random bit, thus continuing the cycle.
The above example is taken from the Computerphile's video on this same topic.
Golang-based implementation of the above LFSR is as shown below. We define a struct holding LFSR with the mentioned three parameters - the number of bits in the register, the seed, and the position of the taps. We define the function named NextBit on it that returns a pseudo-random bit generated with the logic mentioned above.
When we execute the above code with seed 0b1001, tap position 1, on a 4-bit LFSR, we get the following random bits as the output, and with a little bit of pretty-printing, we see
The output bits seem random enough, but upon a close inspection, we see that the last 5 output bits are the same as the first 5, and it is because, for the given configuration of seed and tap, the value in the LFSR becomes the same as the seed value 0b1001 after 15 iterations; thus, from the 16th position, we can see the same set of output bits generated.
By carefully selecting the seed and the taps, we can ensure that the cycle is long enough to never repeat in our process’s lifetime. You can find the detailed source code for this LFSR at github.com/arpitbbhayani/lfsr.
LFSR Bits to Number
Although LFSR generates pseudo-random bits, generating random numbers is fairly simple using it. To generate a k-bit random number we need to generate k random bits using our routine LFSR and accumulate them in a k-bit integer, which becomes our random number.
Golang-based implementation of the above logic can be seen in the function named NextNumber defined below.
The first ten 8-bit random numbers generated with a seed 0b1001 and tap position 1 using the above logic are
We can see that the numbers are fairly random and are within the limits of an 8-bit integer. You can find the detailed source code for this LFSR at github.com/arpitbbhayani/lfsr.
Applications of LFSR
LFSRs find their application across a wide spectrum of use cases, given how efficient they generate randomness. Their applications include digital counters, generating pseudo-random numbers, pseudo-noise, scramble radio frequencies, and in general, a stream of bytes. We take a detailed look into LFSR for scrambling.
Scrambling using LFSR
LFSRs are computationally efficient and deterministic for a seed value, i.e., they generate the same set of numbers in the same order for a seed value, and here’s how they find their application in scrambling and unscrambling a stream of bytes.
The idea of scrambling using LFSR goes like this. We read the raw bytes from the file and pass them to the scrambler function. The function initializes the LFSR with the necessary register length, seed, and tap positions and is kept ready to generate the 8-bit random numbers.
The stream of bytes, from the input file, is then XORed with the random numbers generated from the LFSR such the ith byte of the file is XORed with the ith 8-bit number generated from the LFSR. Golang-based implementation of scramble function is as shown below.
The unscrambling process exploits the following property of XOR and the fact that the LFSR will generate the same set of random numbers in the same order for the given configuration.
So, if we XOR a byte twice with the same number, we get the same byte in return. We apply the same scramble function even to unscramble the scrambled data.
Concerns with LFSR
Although LFSRs are very efficient both on the software and hardware sides, there are some concerns about using them.
The number of bits in the LFSR is limited (as configured); the register will repeat the same set after generating a certain set of bits. The length of the cycle depends solely on the seed value and the tap configuration. So, while employing LFSR for random number generation, it is essential to pick a good set of tap positions and seeds to ensure a very long cycle.
Suppose we get hold of a few consecutive random numbers generated from the LFSR. In that case, we can put them in a few linear equations and reach the initial configuration, enabling us to predict the future set of random numbers. Given how vulnerable LFSRs can be, they are not used at places that need cryptographic strength.