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


1 Answer 1


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 and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.