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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Dec 11, 2016 at 18:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.