> 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 %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://ivalexev.gitbook.io/rednote/pentesting-process/crypto-attacks/prng/lfsr.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.