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?
- translate 'HELLO' to bits.
- translate 'KIHJF' to bits
- xor and get the first 25 key bits.
- the key is the 8 bits initial filling of the register (I'm assuming, but this is common).
- 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.
- Now compute the remainder of the key bits and xor them with the remaining ciphertext, to get plain bits and then plain characters.
- You can compute the characteristic polynomial from 25 bits again: recall the Berlekamp-Massey algorithm.
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.