I'm having a hard time understanding the concept of LFSR, polynomials and finite field and how to solve exercises like picture below. Could anyone give me some pointer on where to start?

enter image description here

  1. translate 'HELLO' to bits.
  2. translate 'KIHJF' to bits
  3. xor and get the first 25 key bits.
  4. the key is the 8 bits initial filling of the register (I'm assuming, but this is common).
  5. we have 25 key bits so 25 linear equations in the initial filling. Or if the system has no initial stepping, the first 8 bits are just the initial filling in reversed order. In any case, you can compute the key. [ADDED:] no initial stepping (So straight initial filling computation) is indeed the case, as I verified.
  6. Now compute the remainder of the key bits and xor them with the remaining ciphertext, to get plain bits and then plain characters.
  7. You can compute the characteristic polynomial from 25 bits again: recall the Berlekamp-Massey algorithm.
| improve this answer | |
  • $\begingroup$ 1. translate 'HELLO ' to bits. = 00111 00100 01011 01011 011101. 2. translate 'KIHJFR' to bits = 01010 01000 0011 01001 00101 3. xor and get the first 30 key bits = 11010 11000 11000 00100 1011 the bits corrosponds to following characters "space" "y" "y" and the last one has only 4 bits so i was not sure what character it belongs to. $\endgroup$ – user3768971 Oct 22 '17 at 14:01
  • $\begingroup$ What is you suggestion for continuing? $\endgroup$ – user3768971 Oct 22 '17 at 14:05
  • $\begingroup$ @user3768971 correct your xor? 00111 xor 01010 = 01101 $\endgroup$ – Henno Brandsma Oct 22 '17 at 14:08
  • $\begingroup$ all characters have 5 bits. $\endgroup$ – Henno Brandsma Oct 22 '17 at 14:16
  • $\begingroup$ yeah i saw it, should be correct now: 01101 01100 01100 00010 01011 the corrosponding letters are now "N" "M" "M" "C" and "L" $\endgroup$ – user3768971 Oct 22 '17 at 14:17

Added as an answer due to its importance: A secret polynomial affords no extra security for LFSRs (which are weak to begin with) due to the Berlekamp Massey attack which works as soon as $2d$ known plaintext (equivalently ciphertext) bits are available. Here $d$ is the degree of the characteristic polynomial.

Of course, knowing HELLO is more than enough to even break a length 12 primitive LFSR, and keeping the taps secret won't help.

| improve this answer | |

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.