# Linear feedback shift register sequences cipher breaking

The premise here is that somehow it is known that a cipher is linear feedback shift register sequence as well as a bit of plaintext and ciphertext, such that it can be found that the first several bits of key are 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1. So then it's possible to use this to try and determine the coefficients of the recursion sequence $x_{n+m} = \sum_{k=0}^{m-1}c_{k}x_{n+k}$ where $x_{k}$ and $c_{k}$ are integers (mod 2) and hence break the cipher completely. Is m the total number of digits (15)? If I'm only asked to find one $c_{k}$, does that imply that $c_{0}=c_{1}=...=c_{m-1}$ and hence, c_{k} can be factored out? Then is it just a matter of setting up multiple equations and solving? I'm I at all on the right track?

• You might have to provide a little more context. At least as I understand it, an LSFR is essentially a method for taking an initial $m$ bits $x_0, \ldots, x_{m-1}$ and extending them to an infinite (eventually repeating) sequence, given by the formula in your question. What is the "key" in this context? – Joppy Oct 8 '17 at 6:38
• The context is breaking a cipher, so the key is what modifies the plaintext through addition to get the ciphertext. – Matt Robbins Oct 8 '17 at 14:42
• I understand that, but how does encryption work in this scheme? I have a plaintext, a key, and an LFSR; how are they combined to produce a ciphertext? – Joppy Oct 8 '17 at 20:46

101001110100111 is really 1010011 being repeated, so then m=7.
$x_{1+7} = c_{0}x_{1+0}+c_{1}x_{1+1}+c_{2}x_{1+2}+c_{3}x_{1+3}+c_{4}x_{1+4}+c_{5}x_{1+5}+c_{6}x_{1+6}$

$x_{8}=c_{0}x_{1}+c_{1}x_{2}+c_{2}x_{3}+c_{3}x_{4}+c_{4}x_{5}+c_{5}x_{6}+c_{6}x_{1}$

$=c_{0}*1+c_{1}*0+c_{2}*1+c_{3}*0+c_{4}*0+c_{5}*1+c_{6}*1=c_{0}+c_{2}+c_{5}+c_{6} = 1$

$x_{9}=c_{1}+c_{4}+c_{5}+c_{6}=0$

$x_{10}=c_{0}+c_{3}+c_{4}+c_{5}=1$

$x_{11}=c_{2}+c_{3}+c_{4}+c_{6}=0$

$x_{12}=c_{1}+c_{2}+c_{3}+c_{5}=0$

$x_{13}=c_{0}+c_{1}+c_{2}+c_{4}=1$

$x_{14}=c_{0}+c_{1}+c_{3}+c_{6}=1$

Use linear algebra to solve the system of equations to get

$c_{0}-c_{5}-c_{6}=-1$

$c_{1}-c_{5}=0$

$c_{2}=0$

$c_{3}=0$

$c_{4}-c_{6}=0$

While there are multiple solutions, one possibility is $c_{2}=c_{3}=0$ and $c_{0}=c_{1}=c_{4}=c_{5}=c_{6}=1$