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

Improve this question
$\endgroup$
3
  • $\begingroup$ Plug in the given data, and solve the system of equations. $\endgroup$
    – Aleph
    Commented Sep 24, 2017 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
    Commented Sep 24, 2017 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
    Commented Oct 25, 2017 at 11:54

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Aldrec, does this address your question? $\endgroup$
    – kodlu
    Commented Sep 25, 2017 at 20:24

Your Answer

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

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