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 [Go1967] gives a list of three statistical properties that a sequence of numbers $a = {a_{n}}_{n = 1}^{\infty}$ , $a_{n} \in {0, 1}$ should display to be considered “random”. Define the autocorrelation of $a$ to be

C (k) = C (k, a) = lim_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} (- 1)^{a_{n} + a_{n + k}} .

In the case where $a$ is periodic with period $P$ , then this reduces to

C (k) = \frac{1}{P} \sum_{n = 1}^{P} (- 1)^{a_{n} + a_{n + k}} .

Assume $a$ is periodic with period $P$ .

balance: $| \sum_{n = 1}^{P} (- 1)^{a_{n}} | \leq 1$ .
low autocorrelation:

$\begin{array}{r} C (k) = {\begin{array}{cc} 1, & k = 0, \\ ϵ, & k \neq 0. \end{array} \end{array}$

(For sequences satisfying these first two properties, it is known that $ϵ = - 1 / P$ must hold.)
proportional runs property: In each period, half the runs have length $1$ , one-fourth have length $2$ , etc. Moreover, there are as many runs of $1$ ’s as there are of $0$ ’s.

A general feedback shift register is a map $f : F_{q}^{d} \to F_{q}^{d}$ of the form

\begin{array}{r} \begin{array}{c} f (x_{0}, . . ., x_{n - 1}) = (x_{1}, x_{2}, . . ., x_{n}), \\ x_{n} = C (x_{0}, . . ., x_{n - 1}), \end{array} \end{array}

where $C : F_{q}^{d} \to F_{q}$ is a given function. When $C$ is of the form

C (x_{0}, . . ., x_{n - 1}) = a_{0} x_{0} + . . . + a_{n - 1} x_{n - 1},

for some given constants $a_{i} \in F_{q}$ , the map is called a linear feedback shift register (LFSR).

Example of an LFSR: Let

f (x) = a_{0} + a_{1} x + . . . + a_{n} x^{n} + . . .,

g (x) = b_{0} + b_{1} x + . . . + b_{n} x^{n} + . . .,

be given polynomials in $F_{2} [x]$ and let

h (x) = \frac{f (x)}{g (x)} = c_{0} + c_{1} x + . . . + c_{n} x^{n} + . . . .

We can compute a recursion formula which allows us to rapidly compute the coefficients of $h (x)$ (take $f (x) = 1$ ):

c_{n} = \sum_{i = 1}^{n} \frac{- b_{i}}{b_{0}} c_{n - i} .

The coefficients of $h (x)$ can, under certain conditions on $f (x)$ and $g (x)$ , be considered “random” from certain statistical points of view.

Example: For instance, if

f (x) = 1, g (x) = x^{4} + x + 1,

then

h (x) = 1 + x + x^{2} + x^{3} + x^{5} + x^{7} + x^{8} + . . . .

The coefficients of $h$ are

\begin{array}{r} \begin{array}{c} 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, \\ 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, . . . . \end{array} \end{array}

The sequence of $0, 1$ ’s is periodic with period $P = 2^{4} - 1 = 15$ and satisfies Golomb’s three randomness conditions. However, this sequence of period 15 can be “cracked” (i.e., a procedure to reproduce $g (x)$ ) by knowing only 8 terms! This is the function of the Berlekamp-Massey algorithm [Mas1969], implemented in berlekamp_massey.py.

AUTHORS:

David Joyner (2005-11-24): initial creation.
Timothy Brock (2005-11): added lfsr_sequence with code modified from Python Cookbook, http://aspn.activestate.com/ASPN/Python/Cookbook/
Timothy Brock (2006-04-17): added lfsr_autocorrelation and lfsr_connection_polynomial.

sage.crypto.lfsr.lfsr_autocorrelation(L, p, k)#

INPUT:

L – a periodic sequence of elements of ZZ or GF(2); must have length $p$
p – the period of $L$
k – an integer between $0$ and $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

sage.crypto.lfsr.lfsr_connection_polynomial(s)#

INPUT:

s – a sequence of elements of a finite field 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 [Mas1969].

EXAMPLES:

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: from sage.matrix.berlekamp_massey import berlekamp_massey
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).

sage.crypto.lfsr.lfsr_sequence(key, fill, n)#

Create an LFSR sequence.

INPUT:

key – a list of finite field elements, $[c_{0}, c_{1}, \dots, c_{k}]$
fill – the list of the initial terms of the LFSR sequence, $[x_{0}, x_{1}, \dots, x_{k}]$
n – number of terms of the sequence that the function returns

OUTPUT:

The LFSR sequence defined by $x_{n + 1} = c_{k} x_{n} + . . . + c_{0} x_{n - k}$ for $n \geq k$ .

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: from sage.matrix.berlekamp_massey import berlekamp_massey
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)