## Software Pseudorandom Number GeneratorAn 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 010The 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.
[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
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; } } }