A special type of stream cipher is implemented in Sage, namely, a linear feedback shift register (LFSR) sequence defined over a finite field. Stream ciphers have been used for a long time as a source of pseudo-random number generators.
S. Golomb [G] gives a list of three
statistical properties a
sequence of numbers
,
, should display to be considered
``random''. Define the autocorrelation of
to be
In the case where
Assume
(For sequences satisfying these first two properties, it is known that
A general feedback shift register is a map
of the form
where
for some given constants
is sometimes called the connection polynomial.
Example:
Over
, if
then
,
The LFSR sequence is then
The sequence of
lfsr_connection_polynomial
(which produces the
reverse of berlekamp_massey
).
sage: F = GF(2) sage: o = F(0) sage: l = F(1) sage: key = [l,o,o,l]; fill = [l,l,o,l]; n = 20 sage: s = lfsr_sequence(key,fill,n); s [1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0] sage: lfsr_autocorrelation(s,15,7) 4/15 sage: lfsr_autocorrelation(s,15,0) 8/15 sage: lfsr_connection_polynomial(s) x^4 + x + 1 sage: berlekamp_massey(s) x^4 + x^3 + 1
See About this document... for information on suggesting changes.