Stream ciphers such as the one-time pad require a secret key stream of random bits which is bitwise x-or'ed with the plaintext to produce a ciphertext. In this problem, you will cryptanalyze one possible approach for generating such a key stream. Let m be a positive integer and Co,C1,...,m-1 {0,1} a sequence of m fixed bits. Let 20,21, ...,2m-1 be any sequence of m bits and define Zm, 2m+1,2m+1, ... via the linear recurrence Entm = Cm-12n+m-1 + Cm-22n+m-2+...+C12n+1 + Con (mod 2) (1) with the usual arithmetic modulo 2. The fixed bits Co,C1, ...Cm-1 are the coefficients of the linear recurrence (1) and the intial values 20,21,..., 2m-1 are its seed. If the seed and the coefficients are appropriately chosen, then (1) generates a sequence of 2 pseudorandom bits! (21)>0 from a seed of length m. This type of construction is popular since it can be implemented very efficiently in hardware using a linear feedback shift register; see pp. 36-37 of the Stinson-Paterson book. (a) (2 marks) Let m = 4 and consider the recurrence Zn+4 = {n+3 + Zn (mod 2) with seed (20, 21, 22, 23) = (1,0,1,0). Write down the first 19 bits 20, 21, ...,218 generated by this recurrence and seed. (b) (4 marks) A user with knowledge of the coefficients and of any m consecutive bits 2,21+1,..., Zi+m-1 (such as the seed, corresponding to the case i=0) can use (1) to generate the entire sequence of bits (2n)ni starting at 2. This user is then able to decrypt everything from that point in the plaintext onwards. Explain how an attacker who intercepts a sequence of any 2m consecutive bits 2, 2+1,..., 2+2m-1 can potentially obtain the (unknown) coeffi- cients co, 1,...,Cm-1 and thus completely break the stream cipher. Your description need not be long, but it should be clear and concise. (c) (4 marks) Suppose the sequence (1,1,1,1,0,0,1,1) of 8 consecutive bits was generated using an unknown linear recurrence of the form (1) with m = 1. Use your attack of part (b) to find the coefficients Co,C1, C2, C3 of this recurrence. Stream ciphers such as the one-time pad require a secret key stream of random bits which is bitwise x-or'ed with the plaintext to produce a ciphertext. In this problem, you will cryptanalyze one possible approach for generating such a key stream. Let m be a positive integer and Co,C1,...,m-1 {0,1} a sequence of m fixed bits. Let 20,21, ...,2m-1 be any sequence of m bits and define Zm, 2m+1,2m+1, ... via the linear recurrence Entm = Cm-12n+m-1 + Cm-22n+m-2+...+C12n+1 + Con (mod 2) (1) with the usual arithmetic modulo 2. The fixed bits Co,C1, ...Cm-1 are the coefficients of the linear recurrence (1) and the intial values 20,21,..., 2m-1 are its seed. If the seed and the coefficients are appropriately chosen, then (1) generates a sequence of 2 pseudorandom bits! (21)>0 from a seed of length m. This type of construction is popular since it can be implemented very efficiently in hardware using a linear feedback shift register; see pp. 36-37 of the Stinson-Paterson book. (a) (2 marks) Let m = 4 and consider the recurrence Zn+4 = {n+3 + Zn (mod 2) with seed (20, 21, 22, 23) = (1,0,1,0). Write down the first 19 bits 20, 21, ...,218 generated by this recurrence and seed. (b) (4 marks) A user with knowledge of the coefficients and of any m consecutive bits 2,21+1,..., Zi+m-1 (such as the seed, corresponding to the case i=0) can use (1) to generate the entire sequence of bits (2n)ni starting at 2. This user is then able to decrypt everything from that point in the plaintext onwards. Explain how an attacker who intercepts a sequence of any 2m consecutive bits 2, 2+1,..., 2+2m-1 can potentially obtain the (unknown) coeffi- cients co, 1,...,Cm-1 and thus completely break the stream cipher. Your description need not be long, but it should be clear and concise. (c) (4 marks) Suppose the sequence (1,1,1,1,0,0,1,1) of 8 consecutive bits was generated using an unknown linear recurrence of the form (1) with m = 1. Use your attack of part (b) to find the coefficients Co,C1, C2, C3 of this recurrence