Problem 1 - Linear Feedback Shift Register Key Streams (10 marks) 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, ..., Cm-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 2n+m = Cm-12n+m-1 + Cm-22n+m-2 + ... + Cl2n+1 + Coin (mod 2), (1) with the usual arithmetic modulo 2. The fixed bits co., ...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 (zi)>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. (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 = 4. Use your attack of part (b) to find the coefficients Co,C1,C2, C3 of this recurrence. (Suggestion: check your answer, i.e. ensure that the coefficients you obtain define a recur- rence that produces the second four bits from the first four.) Problem 1 - Linear Feedback Shift Register Key Streams (10 marks) 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, ..., Cm-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 2n+m = Cm-12n+m-1 + Cm-22n+m-2 + ... + Cl2n+1 + Coin (mod 2), (1) with the usual arithmetic modulo 2. The fixed bits co., ...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 (zi)>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. (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 = 4. Use your attack of part (b) to find the coefficients Co,C1,C2, C3 of this recurrence. (Suggestion: check your answer, i.e. ensure that the coefficients you obtain define a recur- rence that produces the second four bits from the first four.)
