Let F2 = {0,1} with the usual arithmetic modulo 2. The set Fy = {0,1}" consisting of all n-bit vectors (vectors of length n with entries 0 or 1) is an n-dimensional vector space over F2, with the standard basis for example. Linear algebra in F) as a vector space over F2 works just like linear algebra in R as a vector space over R, except that linear combinations of vectors in F have coefficients 0 and 1, and all arithmetic is done modulo 2. For any n e N, let G1, (F2) denote the set of invertible n x n matrices with zeros and ones as entries. Calculations involving such matrices again work exactly the same as the familiar matrix arithmetic over R that you learned in first year linear algebra, except that arithmetic using real numbers is again replaced by arithmetic modulo 2. Now fix n e N and consider the class of linear ciphers with M=C = F), K = GI(F2), and for all plaintexts in interpreted as n-bit column vectors with entries 0 and 1), encryption under a key matrix K is Ek (n) = Km. (2) Then for all ciphertexts c, decryption under K is obviously DK(C)= K-12 Problem 6 Cryptanalysis of linear ciphers (30 marks) In this problem, we explore attacks on linear ciphers as given in (2). a. (3 marks) If each key matrix K is chosen equally likely, does this class of linear ciphers provide perfect secrecy? Formally prove your claim. b. (3 marks) Explain how an attacker Eve can mount a chosen plaintext attack on a cipher of the form (2). The goal of this attack is to chose one or more plaintexts, obtain their encryptions under some unknown key matrix K, and derive K. How should Eve choose her plaintexts, and how many does she need to choose in order to be successful? c. (3 marks) Let a, ..., ; be any collection of i linearly independent vectors in Fy for some i with 1 Sisn. Prove that there are 2 vectors i+1 F" such that the vectors 11, 12,...,i,i+1 are linearly dependent. d. (2 marks) As in part (c), let ml, 12,..., m; be linearly independent vectors in F). How many vectors init1 EF", are there so that the vectors 11, 12,..., mi, mi+1 are linearly independent? h. (6 marks) Part (b) considered a chosen plaintext attack, whereas we will now consider the scenario of mounting a known plaintext attack on a linear cipher as given in (2). Given a set of known plaintext/ciphertext pairs where all the plaintexts were encrypted to their respective corresponding ciphertexts using the same unknown key matrix K, the goal of this attack is to find K. Assume that linear dependence of any collection of n plaintexts in F", represents inde- pendent events, i.e. if p is the probability that any n plaintexts are linearly dependent, then p is the probability that any two collections of n plaintexts are linearly dependent. Explain how Eve can use multiple attempts at a known plaintext attack to find the key matrix. For n = 4, how often does Eve have to try to achieve a 99 percent chance of success? In other words, what is the maximum number k of failed attempts such that Eve has a 99% chance of finding K on the (k+1)-st attempt? Let F2 = {0,1} with the usual arithmetic modulo 2. The set Fy = {0,1}" consisting of all n-bit vectors (vectors of length n with entries 0 or 1) is an n-dimensional vector space over F2, with the standard basis for example. Linear algebra in F) as a vector space over F2 works just like linear algebra in R as a vector space over R, except that linear combinations of vectors in F have coefficients 0 and 1, and all arithmetic is done modulo 2. For any n e N, let G1, (F2) denote the set of invertible n x n matrices with zeros and ones as entries. Calculations involving such matrices again work exactly the same as the familiar matrix arithmetic over R that you learned in first year linear algebra, except that arithmetic using real numbers is again replaced by arithmetic modulo 2. Now fix n e N and consider the class of linear ciphers with M=C = F), K = GI(F2), and for all plaintexts in interpreted as n-bit column vectors with entries 0 and 1), encryption under a key matrix K is Ek (n) = Km. (2) Then for all ciphertexts c, decryption under K is obviously DK(C)= K-12 Problem 6 Cryptanalysis of linear ciphers (30 marks) In this problem, we explore attacks on linear ciphers as given in (2). a. (3 marks) If each key matrix K is chosen equally likely, does this class of linear ciphers provide perfect secrecy? Formally prove your claim. b. (3 marks) Explain how an attacker Eve can mount a chosen plaintext attack on a cipher of the form (2). The goal of this attack is to chose one or more plaintexts, obtain their encryptions under some unknown key matrix K, and derive K. How should Eve choose her plaintexts, and how many does she need to choose in order to be successful? c. (3 marks) Let a, ..., ; be any collection of i linearly independent vectors in Fy for some i with 1 Sisn. Prove that there are 2 vectors i+1 F" such that the vectors 11, 12,...,i,i+1 are linearly dependent. d. (2 marks) As in part (c), let ml, 12,..., m; be linearly independent vectors in F). How many vectors init1 EF", are there so that the vectors 11, 12,..., mi, mi+1 are linearly independent? h. (6 marks) Part (b) considered a chosen plaintext attack, whereas we will now consider the scenario of mounting a known plaintext attack on a linear cipher as given in (2). Given a set of known plaintext/ciphertext pairs where all the plaintexts were encrypted to their respective corresponding ciphertexts using the same unknown key matrix K, the goal of this attack is to find K. Assume that linear dependence of any collection of n plaintexts in F", represents inde- pendent events, i.e. if p is the probability that any n plaintexts are linearly dependent, then p is the probability that any two collections of n plaintexts are linearly dependent. Explain how Eve can use multiple attempts at a known plaintext attack to find the key matrix. For n = 4, how often does Eve have to try to achieve a 99 percent chance of success? In other words, what is the maximum number k of failed attempts such that Eve has a 99% chance of finding K on the (k+1)-st attempt