Use the piling­up lemma to estimate the bias

Question

Q1)This question uses the following S­box from last week's homework. 
0 1 2 3 4 5 6 7 8 9 A B C D E F
8 4 2 1 C 6 3 D A 5 E 7 F B 9 0

1.Find a linear approximation using 3 active S­boxes, and use the piling­up lemma to estimate the bias of P 16 XOR U4,1 XOR U4,9 = 0. Explain your answer at the level of detail of slides 9­11 (but of course answer the analogues of the questions from slide 10) of the lecture slides.

2.Implement the linear cryptanalysis attack from the last question: 
Randomly generate the round keys (80 bits).

Randomly generate 8 * epsilon 16­bit plaintexts, and compute the corresponding ciphertexts 
(using the SPN from Homework 5), where epsilon is the bias of P16 XOR U4,1 XOR U4,9 = 0. 
2You may want to make sure that you generate 8 * epsilon different 16­bit plaintexts. Don't worry if you 
didn't do that; the attack should work anyway.
2Perform the attack that is described in the tutorial and the slides to compute 8 bits of the round 
key for round 5 (using the linear approximation of P16 XOR U4,1 XOR U4,9 = 0).