1

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$?

Temirzhan
  • 217
  • 2
  • 5
  • Plug in the given data, and solve the system of equations. – Aleph Sep 24 '17 at 19:10
  • @Aleph so I can create the following 3 equations $0=C_0∗2+C_1∗1$ & $2=C_0∗1+C_1∗0$ & $2=C_0∗0+C_1∗2$ and from that I can see $C_0 = C_1$ right? – Temirzhan Sep 24 '17 at 19:54
  • @Temirzhan The first equation would be $0 = C_0 \cdot 1 + C_1 \cdot 1$, you have a $2$ there. Given 2 equations in 2 variables gives you the solution already, you don't even need the third equation, but you can check it to verify your result. Btw, $C_0 \neq C_1$, there is no equation which would indicate $C_0 = C_1$ – tylo Oct 25 '17 at 11:54

1 Answers1

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.

kodlu
  • 22,423
  • 2
  • 27
  • 57