Linear feedback shift register (LFSR) sequence commands¶
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 is periodic with period
then this reduces to
Assume is periodic with period
.
balance:
.
low autocorrelation:
(For sequences satisfying these first two properties, it is known that
must hold.)
proportional runs property: In each period, half the runs have length
, one-fourth have length
, etc. Moreover, there are as many runs of
‘s as there are of
‘s.
A general feedback shift register is a map
of the form
where is a given
function. When
is of the form
for some given constants , the map is
called a linear feedback shift register (LFSR).
Example of a LFSR Let
be given polynomials in and let
We can compute a recursion formula which allows us to rapidly
compute the coefficients of (take
):
The coefficients of can, under certain conditions on
and
, be considered “random” from
certain statistical points of view.
Example: For instance, if
then
The coefficients of are
The sequence of ‘s is periodic with period
and satisfies Golomb’s three randomness
conditions. However, this sequence of period 15 can be “cracked”
(i.e., a procedure to reproduce
) by knowing only 8
terms! This is the function of the Berlekamp-Massey algorithm [M],
implemented as
berlekamp_massey.py
.
[G] | Solomon Golomb, Shift register sequences, Aegean Park Press, Laguna Hills, Ca, 1967 |
[M] | (1, 2) James L. Massey, “Shift-Register Synthesis and BCH Decoding.” IEEE Trans. on Information Theory, vol. 15(1), pp. 122-127, Jan 1969. |
AUTHORS:
- Timothy Brock
Created 11-24-2005 by wdj. Last updated 12-02-2005.
-
sage.crypto.lfsr.
lfsr_autocorrelation
(L, p, k)¶ INPUT:
L
- is a periodic sequence of elements of ZZ or GF(2). L must have length = pp
- the period of Lk
- k is an integer (0 k p)
OUTPUT: autocorrelation sequence of L
EXAMPLES:
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) sage: lfsr_autocorrelation(s,15,7) 4/15 sage: lfsr_autocorrelation(s,int(15),7) 4/15
AUTHORS:
- Timothy Brock (2006-04-17)
-
sage.crypto.lfsr.
lfsr_connection_polynomial
(s)¶ INPUT:
s
- a sequence of elements of a finite field (F) of even length
OUTPUT:
C(x)
- the connection polynomial of the minimal LFSR.
This implements the algorithm in section 3 of J. L. Massey’s article [M].
EXAMPLE:
sage: F = GF(2) sage: F Finite Field of size 2 sage: o = F(0); 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_connection_polynomial(s) x^4 + x + 1 sage: berlekamp_massey(s) x^4 + x^3 + 1
Notice that
berlekamp_massey
returns the reverse of the connection polynomial (and is potentially must faster than this implementation).AUTHORS:
- Timothy Brock (2006-04-17)
-
sage.crypto.lfsr.
lfsr_sequence
(key, fill, n)¶ This function creates an lfsr sequence.
INPUT:
key
- a list of finite field elements, [c_0,c_1,...,c_k].fill
- the list of the initial terms of the lfsr sequence, [x_0,x_1,...,x_k].n
- number of terms of the sequence that the function returns.
OUTPUT: The lfsr sequence defined by
, for
.
EXAMPLES:
sage: F = GF(2); l = F(1); o = F(0) sage: F = GF(2); S = LaurentSeriesRing(F,'x'); x = S.gen() sage: fill = [l,l,o,l]; key = [1,o,o,l]; n = 20 sage: L = lfsr_sequence(key,fill,20); L [1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0] sage: g = berlekamp_massey(L); g x^4 + x^3 + 1 sage: (1)/(g.reverse()+O(x^20)) 1 + x + x^2 + x^3 + x^5 + x^7 + x^8 + x^11 + x^15 + x^16 + x^17 + x^18 + O(x^20) sage: (1+x^2)/(g.reverse()+O(x^20)) 1 + x + x^4 + x^8 + x^9 + x^10 + x^11 + x^13 + x^15 + x^16 + x^19 + O(x^20) sage: (1+x^2+x^3)/(g.reverse()+O(x^20)) 1 + x + x^3 + x^5 + x^6 + x^9 + x^13 + x^14 + x^15 + x^16 + x^18 + O(x^20) sage: fill = [l,l,o,l]; key = [l,o,o,o]; n = 20 sage: L = lfsr_sequence(key,fill,20); L [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1] sage: g = berlekamp_massey(L); g x^4 + 1 sage: (1+x)/(g.reverse()+O(x^20)) 1 + x + x^4 + x^5 + x^8 + x^9 + x^12 + x^13 + x^16 + x^17 + O(x^20) sage: (1+x+x^3)/(g.reverse()+O(x^20)) 1 + x + x^3 + x^4 + x^5 + x^7 + x^8 + x^9 + x^11 + x^12 + x^13 + x^15 + x^16 + x^17 + x^19 + O(x^20)
AUTHORS:
- Timothy Brock (2005-11): with code modified from Python Cookbook, http://aspn.activestate.com/ASPN/Python/Cookbook/