Software Pseudorandom Number Generator

Aaron Logue 2001

An LFSR, or Linear Feedback Shift Register, is a type of pseudorandom
number generator.

To illustrate an LFSR in operation, consider a register that is 3
bits wide. Start by loading it with an initial seed value. Shift
it to the right, and if the bit that falls off the end is 1 then
XOR the register with a mask value, otherwise leave it alone. For
this example, we'll use a seed of 010 and a mask value of 101.
Here's what would happen each time we shifted the register:

010 shifted is 001 and a 0 fell off, so leave the register  001
001 shifted is 000 and a 1 fell off, so XOR with 101 to get 101
101 shifted is 010 and a 1 fell off, so XOR with 101 to get 111
111 shifted is 011 and a 1 fell off, so XOR with 101 to get 110
110 shifted is 011 and a 0 fell off, so leave the register  011
011 shifted is 001 and a 1 fell off, so XOR with 101 to get 100
100 shifted is 010 and a 0 fell off, so leave the register  010

The number of values that an LFSR cycles through before repeating
is its period. LFSRs that are maximal period cycle through 2^n-1
values before repeating, where n is the width of the register.  To
obtain a maximal period LFSR, the choice of the bits used for the
XOR mask is critical. The mask bits correspond to the terms of a
primitive polynomial modulo 2. For the above example, the polynomial
is x^3 + x, and the 1s in the mask of 101 correspond to the power
of x terms that are present in the polynomial. Thus, the mask for
the primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 would be 10001110.

It may be possible to combine LFSRs with secure hashes to achieve
strong, albeit slow, pseudorandom sequences. If the LFSR output is
hashed with SHA-1, for example, it may be difficult for an observer
of the SHA output to determine the state of the LFSR or to predict
subsequent output from the LFSR->SHA chain, making the sequence
suitable for use as an XOR encryption pad and requiring only that
the LFSR's starting point be shared. Indeed it is necessary to do
something to an LFSR's output if prediction difficulty is desired,
because it is possible for an observer to identify the mask value
being used with as little as 2n bits of observed output. This is
because 2n bits is equivalent to two consecutive numbers from the
pattern. If the polynomial and one number is known, then the next
number can be derived, and if a number and the next number is known,
then the polynomial can be derived.  For additional reading on
LFSRs, see Applied Cryptography 2nd Edition, Bruce Schneier p. 375.
For an excellent treatise on several different kinds of LFSRs, see
Shift-Register Stream Ciphers[1], and for information on finding
primitive polynomials for use in building your own maximal period
LFSRs, see Sean Erik O'Connor's code[2] and Scott Duplichan's code[3].
Additional information about primitive polynomials can be found at
mathworld.wolfram.com[4]. For truly random numbers, you need to use a
hardware random number generator[5].

[1] http://home.ecn.ab.ca/~jsavard/crypto/co040801.htm
[2] http://www.seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html
[3] http://users2.ev1.net/~sduplichan/primitivepolynomials/ppsearch11.c
[4] http://mathworld.wolfram.com/PrimitivePolynomial.html
[5] http://www.cryogenius.com/hardware/isarng/

Signed-off-by: David Michael Barr <b@rr-dav.id.au>