Linear Feedback Shift Register

CS 463/480 Lecture, Dr. Lawlor

One very simple hardware cipher is a Linear Feedback Shift Register (LFSR). It's called "linear" because the only active gates are XOR operations, which are the equivalent of Galois field additions. XOR is also an information-preserving and hence quantum friendly operation.

Here's an implementation of a very simple three-bit LFSR:

unsigned long LFSR=1;

void foo(void) {
	for (int step=0;step<100;step++) {
		unsigned long lowbit=((LFSR)^(LFSR>>1))&1;
		LFSR=(lowbit<<2)|LFSR>>1;
		printf("%4d: %08lx\n",step,LFSR);
	}
}

(Try this in NetRun now!)

Note that the output cycles around through 7 states (it avoids zero, which will get any linear operator stuck):

   0: 00000004
   1: 00000002
   2: 00000005
   3: 00000006
   4: 00000007
   5: 00000003
   6: 00000001
   7: 00000004
   8: 00000002
   9: 00000005
  10: 00000006
  11: 00000007
  12: 00000003
  13: 00000001
  14: 00000004

Note that we're only working with one bit at a time, which means we could actually use *all* the bits in a 64-bit register (SIMD within a register or SWAR) to simulate 64 separate LFSRs at once:

typedef unsigned long SWAR;
SWAR LFSR0=0x11abcdef12345678; // bit 0
SWAR LFSR1=0x00123456abcdef12; // bit 1
SWAR LFSR2=0x00cceeaaffbbdd11; // bit 2

void foo(void) {
	for (int step=0;step<100;step++) {
		SWAR lowbit=(LFSR0)^(LFSR1);
		LFSR0=LFSR1; // shift right
		LFSR1=LFSR2;
		LFSR2=lowbit;
		printf("%4d: %016lx %016lx %016lx\n",step,LFSR2,LFSR1,LFSR0);
	}
}

(Try this in NetRun now!)

The output is as follows. Note that the cycle still repeats every 7 steps, and the high hex digits match the binary numbers above.

   0: 11b9f9b9b9f9b96a 00cceeaaffbbdd11 00123456abcdef12
   1: 00dedafc54763203 11b9f9b9b9f9b96a 00cceeaaffbbdd11
   2: 117517134642647b 00dedafc54763203 11b9f9b9b9f9b96a
   3: 11672345ed8f8b69 117517134642647b 00dedafc54763203
   4: 11abcdef12345678 11672345ed8f8b69 117517134642647b
   5: 00123456abcdef12 11abcdef12345678 11672345ed8f8b69
   6: 00cceeaaffbbdd11 00123456abcdef12 11abcdef12345678
   7: 11b9f9b9b9f9b96a 00cceeaaffbbdd11 00123456abcdef12
   8: 00dedafc54763203 11b9f9b9b9f9b96a 00cceeaaffbbdd11
   9: 117517134642647b 00dedafc54763203 11b9f9b9b9f9b96a
  10: 11672345ed8f8b69 117517134642647b 00dedafc54763203
  11: 11abcdef12345678 11672345ed8f8b69 117517134642647b
  12: 00123456abcdef12 11abcdef12345678 11672345ed8f8b69
  13: 00cceeaaffbbdd11 00123456abcdef12 11abcdef12345678
  14: 11b9f9b9b9f9b96a 00cceeaaffbbdd11 00123456abcdef12