# Find a LFSR given 2n (or more) non-consecutive keystream bits

How can I calculate the polynomial and state of a LFSR given 2n (or more) non-consecutive keystream bits? It is known to be n bit. If they were consecutive, I could use the Berlekamp–Massey algorithm.

Simple example: n is 7 and I know the keystream is 0...0...1...0...1...0...1...1...1...0...1...0...1...0 where the . is an unknown bit

Any explanation or reference to paper or text book with algorithm will be greatly appreciated.

We are given the sequence $b_i$ for $i$ multiple of $m>1$ with $0\le i<2n\,m$.

• If all the given $b_i$ are identical, we can't compute any missing $b_i$ (beyond a wild guess they are all $b_0$), stop.
• Build the sequence of $2n$ known bits $c_j=b_{(j\,m)}$ with $0\le j<2n$.
• Use Berlekamp–Massey to find a LFSR (polynomial $P$ of degree $k$ and $k$-bit initial state) matching $c_j$.
• Find some period $p$ of the $c_j$. For small degree $k$, we can simulate operation of the LFSR until the state repeats (OK to say $k\le40$ on a PC) or we can use baby-step/giant-step (OK to say $k\le75$ on a PC, see final section of this former revision). But more generally, if $P$ factors into a product of irreducible polynomials of degrees $k_r$ (thus with $k=\sum k_r$), then a period is $p=\prod(2^{k_r}-1)$.
Note: For large polynomial, we can still efficiently compute $c_j$ for large arbitrary $j$ (see this), once we have $P$ and starting state.
• If $\gcd(m,p)=1$, then $b_i$ also has period $p$, thus $\forall j\in\Bbb N,\ c_j=b_{(j\,m\bmod p)}$ ; it follows that $\forall i\in\Bbb N, b_i=c_{(i\,m^{-1}\bmod p)}$
Note: $m^{-1}\bmod p$ needs to be computed only once, e.g. with the half extended Euclidean algorithm.
Note: with $p=\prod(2^{k_r}-1)$ and $m$ a power of two as in the question, $\gcd(m,p)=1$ always holds. If $\gcd(m,p)\ne1$, it might be possible to find a smaller period, by factoring $p$ and iteratively removing those factors that leave what remains a period, until finding the smallest period $p_\text{min}$ (which depends on the irreducible factors of $P$ being primitive or not, and on the starting point). $\gcd(m,p_\text{min})=1$ allows to conclude without guesswork.

Once $2k$ consecutive $b_j$ are found, an easy option to find the LFSR yielding them is to use Berlekamp–Massey again. The initial state of the LFSR for the $b_j$ (in Fibonacci form) is of course the first $k$ bits $b_i$.

Not covered (yet?): polynomial arithmetic would allow to directly derive the LFSR for the $b_j$ from the one for the $c_j$; and conclude when $\gcd(m,p_\text{min})\ne1$ and partial information on the $b_j$ is available.

• Thank very much. I think I understand now. My initial example did not work as it failed in the gcd-step. I have changed it to one that is solvable. – PurpleTree Jun 7 '18 at 18:33
• how does one "efficiently compute c_j for large arbitrary j"? – Les Jul 9 '18 at 1:19
• @fgrieu - I'm confused. In #1 for example, let j=9, the binary expression for J is b1001 or 2^3 + 2^0, then "step the generator 2^i for each i"? Isn't that 9 steps? What if j=2305843009213693952 (mod (2^64-1)). To step the generator that many times would take years, wouldn't it? – Les Jul 9 '18 at 11:20
• @fgrieu - I have opened a new question on efficiently finding $c_j$ for large $j$ - crypto.stackexchange.com/questions/60634/… – Les Jul 9 '18 at 11:23
• @fgrieu - what are the parameters to the baby-step-giant-step if I've computed a non-primitive P, order K in field GF($2^K$)? Am i correct in assuming Alpha = P and Beta is $2^K$-1, with the goal of finding $x$ where $a^x = beta$ ? – Les Jul 12 '18 at 14:56