- lfsr
- Updated Fri, 15 Jul 2022 02:16:56 GMT

I have an exercise for a crypto class that I'm working on and trying to understand. In the problem I have a Linear-Feedback shift register working in mod 3 with digits {0, 1, 2}.

The LFSR is using a recurrence relation of degree 2 which looks like this $Z_{i+2}=C_0Z_i+C_1Z_{i+1}$

I also have part of the keystream $S=...11022...$

I am looking to find $C_0$ & $C_1$ along with

the three keystream numbers that follow and precede $S$

Unfortunately I have no examples to work off so I'm confused on how i'd start even with finding $C_0$ & $C_1$?

Given any LFSR equation $$Z_{i+L}=C_0 Z_i+C_1 Z_{i+1}+\cdots+C_{L-1} Z_{i+L-1},$$ over any field, you can rewrite it as a linear system $$ \left( \begin{array}{cccc} Z_{i} & Z_{i+1} & \cdots & Z_{i+L-1} \\ Z_{i+1} & Z_{i+2} & \cdots & Z_{i+L} \\ \vdots & & & \vdots \\ Z_{i+L-1} & Z_{i+L} & \cdots & Z_{i+2L-2}\\ \end{array} \right) ~ \left(\begin{array}{c} C_0 \\ C_1 \\ \vdots\\ C_{L-1} \end{array}\right) = \left( \begin{array}{c} Z_{i+L} \\ Z_{i+L+1}\\ \vdots\\ Z_{i+2L-1} \end{array} \right) $$

and solve it by using linear algebra, since the right hand vector and the matrix entries are obtained from the observed keystream sequence $(Z_t)$. You will need $2L$ keystream symbols to obtain the coefficients uniquely.

In this case there are faster ways of solving such a system, such as the Berlekamp Massey algorithm, which recursively finds the solution with the smallest $L$, given the keystream $Z_t.$ See the answer to the question berlekamp massey to construct minimal lfsr? for more details.

Local articles referenced by this article: