Schneier posts at https://www.schneier.com/paper-pseudorandom-sequence.html:
int VERYRANDOM() {
static unsigned long regA, regB, regC;
/*regA, regB, and regC should be initialized with some random value.*/
regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
& 0x00000001)<<31) | (regA>>1);
regB = ((((regB>>30)^(regB>>2)) & 0x00000001)<<30) | (regB>>1);
regC = ((((regC>>28)^(regC>>1)) & 0x00000001)<<28) | (regC>>1);
/*regB is a 31-bit LFSR. regC is a 29-bit LFSR.*/
/*Both feedback sequences are chosen to be maximum length.*/
return ((regA & regB) | (!regA & regC)) & 0x00000001;
/*Above is equivalant to: if A then return B else return C.*/
/* Variants: return ((regA & regB) | (regA & regC) | (regB & regC)) &
0x00000001; Above variant returns the majority of A, B, and C.
return (regA ^ regB ^ regC) & 0x00000001;
Above variant returns the XOR of A, B, and C. */
}
And finished by warning against blindly choosing a different feedback sequence. To avoid venturing down such blind alleys I've read up on LFSR and the polynomials that define them.
One place, http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm is kind enough to list maximal length polynomials against however many taps (which is abridged for clarity as more taps become an option). For the 32 bit LFSR I don't understand where Schneier is getting his polynomial from:
regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
& 0x00000001)<<31) | (regA>>1);
According to the wikipedia on LFSR the equivalent polynomial would be:
//Fibonacci x^1 x^26 x^28 x^30 x^31 x^32
regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
& 0x00000001)<<31) | (regA>>1);
which isn't on the table:
[32, 31, 30, 29, 5, 1]
[32, 31, 30, 28, 27, 3]
[32, 31, 30, 28, 26, 13]
[32, 31, 30, 28, 23, 21]
[32, 31, 30, 28, 23, 18]
[32, 31, 30, 28, 20, 15]
[32, 31, 30, 28, 20, 3]
[32, 31, 30, 28, 19, 2]
[32, 31, 30, 28, 19, 1]
[32, 31, 30, 28, 17, 9]
[32, 31, 30, 28, 17, 4]
[32, 31, 30, 28, 17, 3]
[32, 31, 30, 28, 15, 5]
[32, 31, 30, 28, 14, 2]
[32, 31, 30, 28, 12, 9]
[32, 31, 30, 28, 10, 7]
[32, 31, 30, 27, 26, 9]
I don't want to misunderstand anything while learning the basics of crypto so why don't I get this? Before attempting to apply the terminology from Wikipedia's example I had diagnosed the polynomial as:
// 25 27 29 30 31
regA = ((((regA>>31)^(regA>>6)^(regA>>4)^(regA>>2)^(regA<<1)^regA)
& 0x00000001)<<31) | (regA>>1);
But it is XOR'ing the (leftmost) MSbit which goes unaccounted for then, also, odd number of taps is a sure sign I was wrong.
The wikipedia translating of polynomials is:
/* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
I guess wikipedia and newwaveinstruments use different terminology, but if I can't decipher what it is I can forget about understanding cryptography.
Wow. This code really sucks.
When seeded with a value of 1, the first LFSR repeats itself after just 107,359,437 iterations. This falls far short of the 4 billion iterations you would get with a maximal length 32-bit LFSR. With other seed values, the results could be even worse.
In fact, since the other two LFSRs don't include bit 0 in the feedback loop, seeding either of these with a value of 1 would result in them generating an infinite sequence of zeros straight away.
Frankly I'm astounded that someone with Schneier's credentials could possibly come up with something as rubbish as this.
In any case, LFSRs are utterly useless for crypto applications. ARCFOUR includes a simple pseudo-random generator that works much better than Shneier's effort, and probably a lot faster too. But don't go inventing your own cryptography methods. There's really no need :-)