# Find the initial state of LFSR with n non-consecutive output bits

Let's say I have (e.g.) $32$ output bits of an $128$ bit LFSR whose period length is $2^{128} - 1$. Those output bits are chosen arbitrarily, so I do not have any consecutive bits.

Let us call the set of of outputs $Z = \{(i,z_i) | z_i \leftarrow s_0 \cdot A^i\}$, where $s_0$ is the initial state, $A$ describes the companion matrix of the LFSR and $z_i$ is the $i$-th output bit (i.e. the left-/rightmost element of the vector $z_i$).

It should be possible to create some sort of equation system to determine (possible) values for the initial state. But so far I am unable to think of a way, since we do not know the feedback polynomial.

If we had 32 consecutive output bits we could chose 96 other bits at random and clock the LFSR backwards - but in this special case that is not applicable.

Each output $z_i$ is the feedback from the previous state. But since we do not know the polynomial, how can we now create a set of equations?

• Hint: each output bit given is after a known number $n$ of steps from the initial state. For each such given, this gives an equation that the initial state must follow. Solve the system of such equations.
– fgrieu
Commented Dec 11, 2016 at 18:18