1
$\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$
4
  • $\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$
    – Grabul
    Mar 13, 2016 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, 2016 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$ Mar 14, 2016 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, 2016 at 2:39

3 Answers 3

7
$\begingroup$

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

$\endgroup$
0
5
$\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$
2
$\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$
5
  • $\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, 2016 at 16:00
  • $\begingroup$ I don't know, but I count on you to have solved the equations correctly. $\endgroup$ Mar 13, 2016 at 16:01
  • $\begingroup$ CAn you please verify it?? is there any pre made tool to verify online??? $\endgroup$
    – Born2Code
    Mar 13, 2016 at 16:02
  • $\begingroup$ No, I can't verify it. This is your TA's task. $\endgroup$ Mar 13, 2016 at 16:02
  • $\begingroup$ Perhaps, but if so, I'm sure you can find them on your own. $\endgroup$ Mar 13, 2016 at 16:03

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.