0

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

cyborg_681
  • 11
  • 2

1 Answers1

1

Berlekamp Massey algorithm does this for you.

See Dilip Sarwate's nice answer

kodlu
  • 22,423
  • 2
  • 27
  • 57