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 $\mathbf{a}=\{a_n{\}}_{n=1}^{\mathrm{\infty }}$, $a_n\in \{0,1\}$ should display to be considered “random”. Define the autocorrelation of $\mathbf{a}$ to be

$$C(k)=C(k,\mathbf{a})=\underset{N\to \mathrm{\infty }}{lim}\frac{1}{N}\sum _{n=1}^N(-1{)}^{a_n+a_{n+k}}.$$

In the case where $\mathbf{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 $\mathbf{a}$ is periodic with period $P$.

• balance: $|\sum _{n=1}^P(-1{)}^{a_n}|\le 1$.

• low autocorrelation:

  $$\begin{array}{r}C(k)=\{\begin{array}{cc}1,& k=0,\\ ϵ,& k\ne 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:{\mathbf{F}}_q^d\to {\mathbf{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:{\mathbf{F}}_q^d\to {\mathbf{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 {\mathbf{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 ${\mathbf{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 – integer between $0$ and $p$

OUTPUT: autocorrelation sequence of $L$

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> F = GF(Integer(2))
>>> o = F(Integer(0))
>>> l = F(Integer(1))
>>> key = [l,o,o,l]; fill = [l,l,o,l]; n = Integer(20)
>>> s = lfsr_sequence(key,fill,n)
>>> lfsr_autocorrelation(s,Integer(15),Integer(7))
4/15
>>> lfsr_autocorrelation(s,int(Integer(15)),Integer(7))
4/15

Sage Live

F = GF(2)
o = F(0)
l = F(1)
key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
s = lfsr_sequence(key,fill,n)
lfsr_autocorrelation(s,15,7)
lfsr_autocorrelation(s,int(15),7)

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

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

Python

>>> from sage.all import *
>>> F = GF(Integer(2))
>>> F
Finite Field of size 2
>>> o = F(Integer(0)); l = F(Integer(1))
>>> key = [l,o,o,l]; fill = [l,l,o,l]; n = Integer(20)
>>> 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]
>>> lfsr_connection_polynomial(s)
x^4 + x + 1
>>> from sage.matrix.berlekamp_massey import berlekamp_massey
>>> berlekamp_massey(s)
x^4 + x^3 + 1

Sage Live

F = GF(2)
F
o = F(0); l = F(1)
key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
s = lfsr_sequence(key,fill,n); s
lfsr_connection_polynomial(s)
from sage.matrix.berlekamp_massey import berlekamp_massey
berlekamp_massey(s)

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 – 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\ge k$.

EXAMPLES:

Sage

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)

Python

>>> from sage.all import *
>>> F = GF(Integer(2)); l = F(Integer(1)); o = F(Integer(0))
>>> F = GF(Integer(2)); S = LaurentSeriesRing(F,'x'); x = S.gen()
>>> fill = [l,l,o,l]; key = [Integer(1),o,o,l]; n = Integer(20)
>>> L = lfsr_sequence(key,fill,Integer(20)); L
[1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0]
>>> from sage.matrix.berlekamp_massey import berlekamp_massey
>>> g = berlekamp_massey(L); g
x^4 + x^3 + 1
>>> (Integer(1))/(g.reverse()+O(x**Integer(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)
>>> (Integer(1)+x**Integer(2))/(g.reverse()+O(x**Integer(20)))
1 + x + x^4 + x^8 + x^9 + x^10 + x^11 + x^13 + x^15 + x^16 + x^19 + O(x^20)
>>> (Integer(1)+x**Integer(2)+x**Integer(3))/(g.reverse()+O(x**Integer(20)))
1 + x + x^3 + x^5 + x^6 + x^9 + x^13 + x^14 + x^15 + x^16 + x^18 + O(x^20)
>>> fill = [l,l,o,l]; key = [l,o,o,o]; n = Integer(20)
>>> L = lfsr_sequence(key,fill,Integer(20)); L
[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
>>> g = berlekamp_massey(L); g
x^4 + 1
>>> (Integer(1)+x)/(g.reverse()+O(x**Integer(20)))
1 + x + x^4 + x^5 + x^8 + x^9 + x^12 + x^13 + x^16 + x^17 + O(x^20)
>>> (Integer(1)+x+x**Integer(3))/(g.reverse()+O(x**Integer(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)

Sage Live

F = GF(2); l = F(1); o = F(0)
F = GF(2); S = LaurentSeriesRing(F,'x'); x = S.gen()
fill = [l,l,o,l]; key = [1,o,o,l]; n = 20
L = lfsr_sequence(key,fill,20); L
from sage.matrix.berlekamp_massey import berlekamp_massey
g = berlekamp_massey(L); g
(1)/(g.reverse()+O(x^20))
(1+x^2)/(g.reverse()+O(x^20))
(1+x^2+x^3)/(g.reverse()+O(x^20))
fill = [l,l,o,l]; key = [l,o,o,o]; n = 20
L = lfsr_sequence(key,fill,20); L
g = berlekamp_massey(L); g
(1+x)/(g.reverse()+O(x^20))
(1+x+x^3)/(g.reverse()+O(x^20))

Make live