Module: sage.crypto.lfsr
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
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
Example of a LFSR Let
be given polynomials in
We can compute a recursion formula which allows us to rapidly compute the coefficients of
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
The sequence of
berlekamp_massey.py
.
[G] Solomon Golomb, Shift register sequences, Aegean Park Press, Laguna Hills, Ca, 1967
[M] James L. Massey, ``Shift-Register Synthesis and BCH Decoding.'' IEEE Trans. on Information Theory, vol. 15(1), pp. 122-127, Jan 1969.
Author: Timothy Brock
Created 11-24-2005 by wdj. Last updated 12-02-2005.
Module-level Functions
L, p, k) |
Input:
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
Author: 2006-04-17: Timothy Brock (m060774@usna.edu)
s) |
Input:
This implements the algorithm in section 3 of J. L. Massey's article [M].
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).
Author: 2006-04-17: Timothy Brock (m060774@usna.edu)
REFERENCES: [M] J. L. Massey, "Shift-register synthesis and BCH decoding," IEEE Trans. Inform. Theory, vol. IT-15, pp. 122-127, Jan. 19 69.
key, fill, n) |
This function creates an lfsr sequence.
Input:
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)
Author: Timothy Brock (11-2005, with code modified from Python Cookbook, http://aspn.activestate.com/ASPN/Python/Cookbook/
See About this document... for information on suggesting changes.