LFSR

Linear Feedback Shift Register

Used to generate a stream for OTP.

Defined by:

• BitSize (Length of internal state)

• CharacteristicPolynomial (Function to be calculated for generating new values)

• InitialState (Initial state)

By knowing the CharacteristicPolynomial of an N-BitSize, it is possible to recover the internal state by observing a subsequence of N outputs. This makes it possible to predict subsequent sequences and recover old ones. Moreover, even if one does not know the CharacteristicPolynomial, it is possible to recover it with a sequence of observations. Berlekamp-Massey algorithm allows finding LFSR for a sequence of outputs.

Code

From HERE.

#!/usr/bin/env python

def Berlekamp_Massey_algorithm(sequence):
    N = len(sequence)
    s = sequence[:]

    for k in range(N):
        if s[k] == 1:
            break
    f = set([k + 1, 0])  # use a set to denote polynomial
    l = k + 1

    g = set([0])
    a = k
    b = 0

    for n in range(k + 1, N):
        d = 0
        for ele in f:
            d ^= s[ele + n - l]

        if d == 0:
            b += 1
        else:
            if 2 * l > n:
                f ^= set([a - b + ele for ele in g])
                b += 1
            else:
                temp = f.copy()
                f = set([b - a + ele for ele in f]) ^ g
                l = n + 1 - l
                g = temp
                a = b
                b = n - l + 1

    # output the polynomial
    def print_poly(polynomial):
        result = ''
        lis = sorted(polynomial, reverse=True)
        for i in lis:
            if i == 0:
                result += '1'
            else:
                result += 'x^%s' % str(i)

            if i != lis[-1]:
                result += ' + '

        return result

    return (print_poly(f), l)


if __name__ == '__main__':
    seq = (0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0)
    (poly, span) = Berlekamp_Massey_algorithm(seq)

    print 'The input sequence is %s.' % str(seq)
    print 'Its characteristic polynomial is (%s),' % poly,
    print 'and linear span is %d.' % span