This code implements a simple, fast nonlinear feedback shift register
(NLFSR), a form of pseudorandom number generator. I believe it is good
enough to use in crypographical applications, but I make no promises.
Linear feedback shift registers are not appropriate for use in crypto
applications because they are susceptible to the "correllation attack",
which allows an adversary to determine the value of an N-bit LFSR key after
observing only 2*N+1 bits of system output. Please see Schneier's _Applied
Cryptography_ for more details.
A nonlinear combination of feedback shift registers, on the other hand,
is not necessarily susceptible to the correllation attack. This NLFSR uses
integer multiplication as its fundamental nonlinear operation, and throws
out the high and low bits from each multiplication because the values of
those bits are necessarily predictable. It uses two LFSR's as sources for
the multiplication.
Recoded this 2001-01-13 with stdtypes for greater portability.
The interface functions for the nlfsr are:
int32 nlfsr_init ( nlfsrt *mx, word32 nbytes, word32 *seed );
nlfsr_init() will initialize a new nlfsrt struct with the given seed
values. Note that the cryptographical strength of the nlfsr is no greater
than the seed you use! Use a cryptographically strong source of seed
values (like /dev/urandom on FreeBSD and Linux systems). Returns the
bitwise strength of the nlfsr on success (ie, the average length of the
two component lfsr's), or 0 on failure. The period of the nlfsr's output
is approxamitely 2**strength.
int32 nlfsr_nuke ( nlfsrt *mx );
nlfsr_nuke() will free an nlfsr's dynamic memory fields after writing
over them with 0's.
word32 nlfsr_get_n ( nlfsrt *mx, word32 n );
nlfsr_get_n() will put n bits (up to 32) into the least significant
digits of its return value.
byte nlfsr_get_byte ( nlfsrt *mx );
nlfsr_get_byte() will return a randomly-valued octet.
word32 nlfsr_get_word ( nlfsrt *mx );
nlfsr_get_word() will return a randomly-valued 32-bit word.