Problem 5 - Cryptanalysis of a class of linear ciphers, 34 marks) Let F2 = {0,1} with the usual arithmetic modulo 2. The set F3 = {0,1}" consisting of all no-bit vectors with entries 0 or 1 is an n-dimensional vector space over F2 (with the usual canonical basis, for example). Linear algebra works exactly like linear algebra over R as a vector space over R, except that linear combinations of vectors in E have coefficients 0 and 1. For any ne Nlet Gl.(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 linear algebra over R you learned in first year, except that arithmetic using real numbers is replaced by arithmetic modulo 2. Now fix n E N and consider the class of linear cryptosystems with M =C=F3, K = Gl. (F2). and for all plaintexts m interpreted as n-bit column vectors with entries 0 and 1), encryption under a key matrix K is Ex(*) = Km. Then for all ciphertexts, decryption under K is obviously (2) Dx(@=K-. (a) (5 marks) Prove, by explicitly describing the key matrix K that encrypts an arbitrary plaintext vector vil to an arbitrary ciphertext vector that a transposition cipher operating on bit strings of length n is a special case of a linear cipher as given in (2), whose key matrices are permutation matrices, i.e. matrices in Gl. (F2) with exactly one one and n - 1 zeros in each row and in each column. (b) (4 marks) Explain how a cryptanalyst 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) (4 marks) Let m. ...,n be any collection of i linearly independent vectors in E for some i with 1sisn. Prove that there are 2 vectors mit E F such that the vectors 1,112,...,1 +1 are linearly dependent. (d) (3 marks) With the notation of part (c), how many vectors mit E F are there so that the vectors 1,2,...,1,miti are linearly independent? Problem 5 - Cryptanalysis of a class of linear ciphers, 34 marks) Let F2 = {0,1} with the usual arithmetic modulo 2. The set F3 = {0,1}" consisting of all no-bit vectors with entries 0 or 1 is an n-dimensional vector space over F2 (with the usual canonical basis, for example). Linear algebra works exactly like linear algebra over R as a vector space over R, except that linear combinations of vectors in E have coefficients 0 and 1. For any ne Nlet Gl.(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 linear algebra over R you learned in first year, except that arithmetic using real numbers is replaced by arithmetic modulo 2. Now fix n E N and consider the class of linear cryptosystems with M =C=F3, K = Gl. (F2). and for all plaintexts m interpreted as n-bit column vectors with entries 0 and 1), encryption under a key matrix K is Ex(*) = Km. Then for all ciphertexts, decryption under K is obviously (2) Dx(@=K-. (a) (5 marks) Prove, by explicitly describing the key matrix K that encrypts an arbitrary plaintext vector vil to an arbitrary ciphertext vector that a transposition cipher operating on bit strings of length n is a special case of a linear cipher as given in (2), whose key matrices are permutation matrices, i.e. matrices in Gl. (F2) with exactly one one and n - 1 zeros in each row and in each column. (b) (4 marks) Explain how a cryptanalyst 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) (4 marks) Let m. ...,n be any collection of i linearly independent vectors in E for some i with 1sisn. Prove that there are 2 vectors mit E F such that the vectors 1,112,...,1 +1 are linearly dependent. (d) (3 marks) With the notation of part (c), how many vectors mit E F are there so that the vectors 1,2,...,1,miti are linearly independent