2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Joppy Oct 8 '17 at 6:38
  • $\begingroup$ The context is breaking a cipher, so the key is what modifies the plaintext through addition to get the ciphertext. $\endgroup$ – Matt Robbins Oct 8 '17 at 14:42
  • $\begingroup$ 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? $\endgroup$ – Joppy Oct 8 '17 at 20:46
1
$\begingroup$

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$

$\endgroup$

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.