2
$\begingroup$

My friend gave me a question to solve. The question he asked me was: the following sequence has been generated by a 7-bit linear feedback shift register. He asked me to find the feedback polynomial. I went through some lectures on LFSR on youtube. But still I am unable to solve this. Can anyone point out how to approach or crack this kind of question?

1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1

$\endgroup$
  • $\begingroup$ Repetition length is 105 and there is no sequence of more than seven 1 or zeros. So 7 bits LFSR is possible. You can try all combinations with a small program (only 128 polynomials possible) and find the LFSRs with lenght 105. You will then have to find the initial value. Et voilà ! $\endgroup$ – TEMLIB Mar 13 '16 at 15:12
  • $\begingroup$ I am getting answer as x^7 + x^6 + x^5 + x^1 + 1. Is this right? $\endgroup$ – Born2Code Mar 13 '16 at 15:37
  • 3
    $\begingroup$ Do not post the same question on multiple sites. And do not delete a question once it's been answered, that's rude towards the answerer. $\endgroup$ – Gilles Mar 14 '16 at 0:07
  • 1
    $\begingroup$ Also posted on Crypto.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Mar 14 '16 at 2:39
8
$\begingroup$

The feedback polynomial is $x^7 + x^6 + x^5 + x^1 + 1$ and can be computed using the Berlekamp-Massey algorithm.

$\endgroup$
6
$\begingroup$

There is a comprehensive and excellent answer in this earlier “Cryptanalysis of Linear Feedback Shift Registers” question. Alternatively, if you know the order of the recurrence is $n$, you can solve a linear system of the form $$ \left( \begin{array}{lllll} z_i & z_{i+1} & \cdots & z_{i+n-1} \\ z_{i+1} & z_{i+2} & \cdots & z_{i+n} \\ & & \vdots & & \\ z_{i+n} & z_{i+n+1} & \cdots & z_{i+2n-1} \\ \end{array} \right) \left( \begin{array}{c} c_n \\ c_{n-1}\\ \vdots\\ c_2\\ c_1 \end{array} \right) = \left( \begin{array}{c} z_{i+n}\\ z_{i+n+1}\\ \vdots\\ z_{i+2n}\\ \end{array} \right) $$ where $(z_t)_{t \geq 1}$ are the sequence bits, and $i\geq 1$. Here $c_i$ are the recurrence coefficients, to be determined. This should be done over $GF(2)$ i.e., with mod 2 arithmetic.

If the recurrence is order $n$ then $c_n=1.$ If the recurrence is of lower order the system becomes singular and you need to work with a smaller square left upper submatrix.

The polynomial you want is $1+c_1 x+\ldots+c_n x^n.$

Note that the matrix method is of higher complexity than the recursive Berlekamp Massey algorithm in the linked question.

$\endgroup$
3
$\begingroup$

Denote the sequence by $X_0,X_1,\ldots$. If the minimal polynomial is $x^7 + a_6 x^6 + \cdots + a_0 x^0$, then (by definition) for every $N$ it will hold that $X_{N+7} = a_6 X_{N+6} + \cdots + a_0 X_N$ (modulo 2). (Your definition may vary slightly.) Since the first few values are $1,0,0,0,1,0,1,0$, this implies that $0 = a_6 + a_4 + a_0$. Collect enough such equations and solve them to recover the minimal polynomial.

$\endgroup$
  • $\begingroup$ Thats how I did it! and got this x^7 + x^6 + x^5 + x^1 + 1. Is this right??? $\endgroup$ – Born2Code Mar 13 '16 at 16:00
  • $\begingroup$ I don't know, but I count on you to have solved the equations correctly. $\endgroup$ – Yuval Filmus Mar 13 '16 at 16:01
  • $\begingroup$ CAn you please verify it?? is there any pre made tool to verify online??? $\endgroup$ – Born2Code Mar 13 '16 at 16:02
  • $\begingroup$ No, I can't verify it. This is your TA's task. $\endgroup$ – Yuval Filmus Mar 13 '16 at 16:02
  • $\begingroup$ Perhaps, but if so, I'm sure you can find them on your own. $\endgroup$ – Yuval Filmus Mar 13 '16 at 16:03

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.