1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Plug in the given data, and solve the system of equations. $\endgroup$ – Aleph Sep 24 '17 at 19:10
  • $\begingroup$ @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? $\endgroup$ – Temirzhan Sep 24 '17 at 19:54
  • $\begingroup$ @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$ $\endgroup$ – tylo Oct 25 '17 at 11:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Aldrec, does this address your question? $\endgroup$ – kodlu Sep 25 '17 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.