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.


Here are some programs to find and verify maximal period LFSR masks from 2 to 16 bits using brute force. They are easily modified to search for longer-period masks.
[gorf@box lfsrs]# cat lfsr_brute.c
/* Find primitive polynomial mod 2 masks by brute force */
/* Aaron Logue 2013      gcc -o lfsr_brute lfsr_brute.c */
#include <stdio.h>
int main(int argc, int argv[]) {
 unsigned int i, row, lfsr, lsb, width, power, mask;
   width = 2;
   while (width <= 16) {
      power = 1 << width;
      row = 0;
      printf("Masks with period %d :\n", power-1);
      for (mask=power>>1; mask < power; mask++) {
         lfsr = 1;
         i = 0;
         do {
            lsb = lfsr & 1;
            lfsr >>= 1;
            if (lsb) {
               lfsr ^= mask;
            }
            i++;
         } while (lfsr != 1);
         if (i == (power-1)) {
            printf(" %x", mask);
            row++;
            if (row == 12) {
               printf("\n");
               row = 0;
            }
         }
      }
      if (row) {
         printf("\n");
      }
      width++;
   }
   return 1;
}

[gorf@box lfsrs]# ./lfsr_brute
...
Masks with period 63 :
 21 2d 30 33 36 39
Masks with period 127 :
 41 44 47 48 4e 53 55 5c 5f 60 65 69
 6a 72 77 78 7b 7e
Masks with period 255 :
 8e 95 96 a6 af b1 b2 b4 b8 c3 c6 d4
 e1 e7 f3 fa
Masks with period 511 :
 108 10d 110 116 119 12c 12f 134 137 13b 13e 143
 14a 151 152 157 15b 15e 167 168 16d 17a 17c 189
 18a 18f 191 198 19d 1a7 1ad 1b0 1b5 1b6 1b9 1bf
 1c2 1c7 1da 1dc 1e3 1e5 1e6 1ea 1ec 1f1 1f4 1fd
Masks with period 1023 :
 204 20d 213 216 232 237 240 245 262 26b 273 279
 27f 286 28c 291 298 29e 2a1 2ab 2b5 2c2 2c7 2cb
...

[gorf@box lfsrs]# cat lfsr_tester.c
/* GF(2) Primitive Polynomial Tester for short LFSR masks. */
/* Aaron Logue 2013      gcc -o lfsr_tester lfsr_tester.c  */
#define MASK 0x9AEB
#include <stdio.h>
void lfsr_shift(unsigned int *lfsr) {
 int lsb;
   lsb = *lfsr & 1;
   *lfsr >>= 1;
   if (lsb) {
      *lfsr ^= MASK;
   }
}
int main(int argc, int argv[]) {
 unsigned int i = 0;
 unsigned int lfsr = 1;
   do {
      lfsr_shift(&lfsr);
      i++;
   } while (lfsr != 1);
   printf("Period of mask %x is %d\n", MASK, i);
   return 1;
}

[gorf@box lfsrs]# ./lfsr_tester
Period of mask 9aeb is 65535
...
Period of mask ab6ba is 1048575

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;
      }
   }
}