a) We consider the possibility of obtaining the periodic sequence {111000}8, that is 111000111000 ·.

a) We consider the possibility of obtaining the periodic sequence {111000}8, that is 111000111000 · · · using the LFSR of length 3. Specify the connection polynomial of LFSR of length 3 in case it is possible to generate such a sequence with this length. Motivate your answer. Solution We cannot get such a sequence since when the state of LFSR is 000 which is a part of the sequence it will output only zeros. b) Alice wants to encrypt a string of bits. She decides to encrypt using an LFSR as a generator in a stream cipher. However, she knows that just using an LFSR is a bad choice, so she makes a modification. She only uses every second bit of the LFSR sequence. The encryption process would then be as follows. A sequence of bits m = m1, m2, . . . , mn is encrypted to a sequence of ciphertext symbols c = c1, c2, . . . , cn by ci = mi ? s 0 i , ?i, 1 = i = n where s 0 i = s 0 1 , s0 2 , . . . is obtained from the binary LFSR sequence s = s1, s2, . . . using s 0 i = s2i , i = 1, 2, . . .. Finally, s is generated by a length 4 LFSR with connection polynomial C(x) = 1+x+x 4 , with initial (secret) state (s1, s2, s3, s4) (the LFSR outputs first s1 then s2 etc.) 27 Eve observed the ciphertext c = 0, 1, 1, 1, 1, 1, 0. Also, she knows that the plaintext starts as 1, 1, 1, 1, . . . , i.e., m = 1, 1, 1, 1, m5, m6, m7. Find the remaining plaintext bits.