$4.[5$ points$]$ Implementation of Known$-$Plaintext Cryptanalysis of LFSR Cipher

Implement the following function:

RecoverKey$($m$,$ c$,$ t$),$ which recovers the key $($k$,$ d$)$ from a known plaintext$/$ciphertext pair $($m$,$ c$),$ where the underlying keystream is generated by a recurrence of degree t$.$

I have implemented the LFSR cipher and chosen a secret key. Using your implementation of RecoverKey, use the plaintext and ciphertext provided on Canvas to launch a known$-$plaintext attack to recover my secret key. The underlying keystream is generated by a recurrence of degree t $=250.$

Hint: The method that I showed in class involves solving a system of linear equations mod $2.$ If you are using Python, I have provided a short script that will construct the inverse of a matrix mod $2,$ which you can use as a subroutine in your solution. My code requires the Numpy package$\mathrm{.}3.[10$ points$]$ Implementation and Analysis of LFSR Keystream Generation.

Implement these functions:

$($a$)$ KeystreamGen$($k$,$ d$,$ n$),$ which generates the first

$$

n characters

$$

$1$

$$

$2$

$...$

$$

$$

z

$1$

$$

z

$2$

$$

$...$z

n

$$

of the LFSR keystream defined by the key

$($

$$

$,$

$$

$)$

$($k$,$d$).$

$($b$)$ FindPeriod$($k$,$ d$),$ which determines the period of the LFSR keystream defined by the key

$($

$$

$,$

$$

$)$

$($k$,$d$).$

$($c$)$ ComputeProb$($t$),$ which computes the probability that a randomly$-$chosen LFSR keystream defined by a recurrence of degree

$$

t has order as large as possible.

Hint:

i$.$ I don't care if your implementation is efficient. ii$.$ A recurrence of degree

$$

t is defined by two parameters: the initial conditions

$$

in

$$

$2$

$$

k in Z

$2$

t

$$

$,$ and the coefficient vector

$$

in

$$

$2$

$$

d in Z

$2$

t

$$

which satisfies

$$

$0$

$=$

$1$

d

$0$

$$

$=1.$

Using these tools:

$($a$)$ Determine the period of LFSR keystream arising from the following keys

$($

$$

$,$

$$

$)$

$($k$,$d$)$:

i$.$

$$

$=$

$11001111010011111111$

k$=11001111010011111111,$

$$

$=$

$11000010001000110100$

d$=11000010001000110100$

ii$.$

$$

$=$

$01010100001001000010$

k$=01010100001001000010,$

$$

$=$

$11100100110101100001$

d$=11100100110101100001$

iii.

$$

$=$

$10011011000111110101$

k$=10011011000111110101,$

$$

$=$

$11010101000000001110$

d$=11010101000000001110$

$($b$)$ Compute the probability that a randomly$-$chosen key

$($

$$

$,$

$$

$)$

$($k$,$d$),$ which defines a recurrence of degree

$$

t $($so

$$

$,$

$$

in

$$

$2$

$$

k$,$d in Z

$2$

t

$$

and

$$

$0$

$=$

$1$

d

$0$

$$

$=1),$ yields a keystream of maximal order, for

$$

$=$

$2$

$,$

$3$

$,$

$4$

$,$

$5$

$,$

$6$

$,$

$7$

t$=2,3,4,5,6,7.$