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, and for information on finding primitive polynomials for use in building your own maximal period LFSRs, see Sean Erik O'Connor's code and Scott Duplichan's code. Additional information about primitive polynomials can be found at mathworld.wolfram.com. For truly random numbers, you need to use a hardware random number generator. 

/****************************************************************************
 * Galois linear feedback shift register pseudorandom number generator.
 * This LFSR cycles through 2^160-1 values before repeating.
 * Aaron Logue 2001 - To the public domain.
 *
 * Declare an external unsigned long lfsr[5] array and seed with nonzero value.
 * lfsr[0] contains most significant bits.
 *
 * The mask value below implements the following primitive polynomial:
 * X^160+X^159+X^158+X^157+X^155+X^153+X^151+X^150+X^149+X^148+X^147+X^146+
 *  X^142+X^141+X^137+X^134+X^133+X^132+X^130+
 * X^128+X^126+X^125+X^121+X^120+X^118+X^117+X^116+X^114+
 *  X^112+X^111+X^109+X^108+X^106+X^104+X^102+
 * X^95+ X^94+ X^90+ X^89+ X^88+ X^86+ X^85+ X^84+ X^83+ X^82+ X^81+
 *  X^80+ X^78+ X^76+ X^68+ X^66+
 * X^64+ X^61+ X^60+ X^59+ X^57+ X^52+ X^50+
 *  X^46+ X^45+ X^41+ X^40+ X^39+ X^38+ X^37+ X^36+ X^35+
 * X^31+ X^29+ X^27+ X^26+ X^25+ X^23+ X^20+ X^18+
 *  X^16+ X^11+ X^10+ X^8+  X^7+  X^6+  X^5+  X^3+  X+ 1
 ***************************************************************************/
static unsigned long lfsr[5];
#define MASK0 0xF57E313A
#define MASK1 0xB1BADAA0
#define MASK2 0x63BFA80A
#define MASK3 0x9D0A31FC
#define MASK4 0x574A86F5
void lfsr_shift(unsigned long * lfsr, int n) {
   int lsb;
   int i;
   for (i=0;i<n;i++) {
      lsb = lfsr[4] & 1;
      lfsr[4] = ((lfsr[3] & 0x00000001) << 31) | (lfsr[4] >> 1);
      lfsr[3] = ((lfsr[2] & 0x00000001) << 31) | (lfsr[3] >> 1);
      lfsr[2] = ((lfsr[1] & 0x00000001) << 31) | (lfsr[2] >> 1);
      lfsr[1] = ((lfsr[0] & 0x00000001) << 31) | (lfsr[1] >> 1);
      lfsr[0] = lfsr[0] >> 1;
      if (lsb) {
         lfsr[4] ^= MASK4;
         lfsr[3] ^= MASK3;
         lfsr[2] ^= MASK2;
         lfsr[1] ^= MASK1;
         lfsr[0] ^= MASK0;
      }
   }
}