> For the complete documentation index, see [llms.txt](https://ivalexev.gitbook.io/rednote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ivalexev.gitbook.io/rednote/pentesting-process/crypto-attacks/prng/lfsr.md).

# LFSR

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)

<figure><img src="/files/mWKKbREYEvMjHHa8z2qp" alt=""><figcaption></figcaption></figure>

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](https://github.com/bozhu/BMA/blob/master/bma.py).

{% code overflow="wrap" %}

```python
#!/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
```

{% endcode %}