Problem $1-$ Linear feedback shift register key streams $(11$ marks$)$

Stream ciphers such as the one$-$time pad require a secret key stream of pseudorandom bits. In this

problem, you will cryptanalyze one possible approach for generating such a key stream.

Let $m$ be a positive integer and $c_0,c_1,$dots,$c_{m-1}in\{0,1\}$ a sequence of $m$ fixed bits. Let $z_0,z_1,$dots,$z_{m-1}$

be any sequence of $m$ bits and define $z_m,z_{m+1},z_{m+2},$dots via the linear recurrence

$z_{n+m}-=c_{m-1}{z}_{n+m-1}+c_{m-2}{z}_{n+m-2}+$cdots$+c_1{z}_{n+1}+c_0{z}_n(mod2),(n0),$

with the usual arithmetic modulo $2.$ The fixed bits $c_0,c_1,dots{c}_{m-1}$ are the coefficients of the linear

recurrence $(1)$ and the initial values $z_0,z_1,$dots,$z_{m-1}$ are its seed. If the seed and the coefficients are

appropriately chosen, then $(1)$ generates a sequence of $2^m$ pseudorandom $bit{s}^1(z_i{)}_{i}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 $($LFSR$).$ If you are interested in how to do this; see

pp$.36-37$ of the Stinson$-$Paterson book, but you don't need to consult this source or know what an

LSFR is in order to solve this problem.

a$.(2$ marks$)$ Consider the recurrence

$z_{n+4}-=z_{n+3}+z_n(mod2),$

This represents the special case of $(1)$ with $m=4$ and $(c_3,c_2,c_1,c_0)=(1,0,0,1).$ Write down

the first $19$ bits $z_0,z_1,$dots,$z_{18}$ generated by this recurrence with seed $(z_0,z_1,z_2,z_3)=(1,0,1,0).$