I have a following crypto problem and I have been struggling with for some time

An 8-bit linear feedback shift register with connection polynomial C(X) = 1+aX +bX^2 +cX^3 +dX^4 +eX^5 + fX^6 +gX^7 +hX^8 is used to generate a pseudo-random binary sequence. This pseudo-random sequence is used as the enciphering key of a stream cipher. It is known that when the cipher is applied to the plaintext string [0,0,0,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,1,0,1,0,1,1,0,1,1,0,1] the corresponding ciphertext string is [1,0,1,0,1,1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,0,1,0,1,0,0,0,1,0,0]

What would be the approach to determine all non-zero coefficients in this polynomial? I have no clue how to start...

Thanks in advance


Berlekamp Massey algorithm does this for you.

See Dilip Sarwate's nice 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.