Reconstruct an LFSR of the shortest length which generates the sequence {1, 0, 0, 0, 1, 1, 1, 1} by.

Reconstruct an LFSR of the shortest length which generates the sequence {1, 0, 0, 0, 1, 1, 1, 1} by using Berlekamp-Massey Algorithm. (c) The following is the description of the A5/1 key stream generator (refer Fig 2). It consists of three LFSRs denoted by R1, R2 and R3, with respective lengths of 19, 22, and 23 bits. The total content of all the three LFSRs is thus 19 + 22 + 23 = 64 bits. We refer the 64 bit initial contents of the three LFSRs as the key of the cipher. Ri [n] is used to refer to the n th bit of the register Ri , where i = 1, 2, 3, and n starts from 0. Each LFSR has one clocking tap: R1[8], R2[10], R3[10]. At each clock cycle, one key stream is generated as follows: • The three LFSRs make a clocking vote according to the majority of the current three clocking taps. • Each Ri compares the voting result with its own clocking tap. If they are equal, Ri is shifted: – a feedback bit is computed by XORing the contents of a fixed subset of cells of Ri , i.e the feedback for R1, R2 and R3 is: R1[18] ? R1[17] ? R1[16] ? R1[13], R2[21] ? R2[20], and R3[22] ? R3[21] ? R3[20] ? R3[7] respectively. – the content of all cells in Ri (except the leftmost) are shifted to the left by one position simultaneously – Ri [0] is updated by the precomputed feedback. • Output the bit R1[18] ? R2[21] ? R3[22]. Answer the following questions regarding the above key stream generator: i. Show that when R1 is loaded with a special initial state, then its state remains the same in the future. ii. Compute the number of 64 bit keys (number of initial states of the three LFSRs) so that the stream cipher generates 64 bit all zero key stream.