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 \({\bf a}=\{a_n\}_{n=1}^\infty\), \(a_n\in \{0,1\}\), should display to be considered “random”. Define the autocorrelation of \({\bf a}\) to be
In the case where \({\bf a}\) is periodic with period \(P\) then this reduces to
Assume \({\bf a}\) is periodic with period \(P\).
balance: \(|\sum_{n=1}^P(-1)^{a_n}|\leq 1\).
low autocorrelation:
(For sequences satisfying these first two properties, it is known that \(\epsilon=-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:{\bf F}_q^d\rightarrow {\bf F}_q^d\) of the form
where \(C:{\bf F}_q^d\rightarrow {\bf F}_q\) is a given function. When \(C\) is of the form
for some given constants \(a_i\in {\bf F}_q\), the map is called a linear feedback shift register (LFSR).
Example of a LFSR Let
be given polynomials in \({\bf F}_2[x]\) and let
We can compute a recursion formula which allows us to rapidly compute the coefficients of \(h(x)\) (take \(f(x)=1\)):
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
then
The coefficients of \(h\) are
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 [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:
Created 11-24-2005 by wdj. Last updated 12-02-2005.
INPUT:
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:
INPUT:
OUTPUT:
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:
This function creates an lfsr sequence.
INPUT:
OUTPUT: The lfsr sequence defined by \(x_{n+1} = c_kx_n+...+c_0x_{n-k}\), for \(n \leq 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: 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: