Problem 5 - Cryptanalysis of a class of linear ciphers, 34 marks) Let F2 = {0,1} with the usual arithmetic modulo 2. The set = {0,1}" consisting of all n-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 F have coefficients 0 and 1. For any neN, let GI, (F2) denote the set of invertible nxn 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 = E, K = Gln (F2), and for all plaintexts (interpreted as n-bit column vectors with entries 0 and 1), encryption under a key matrix K is Ex() = K. Then for all ciphertexts c, decryption under K is obviously Dk(@=K-1. (a) (5 marks) Prove, by explicitly describing the key matrix K that encrypts an arbitrary plaintext vector to an arbitrary ciphertext vector c, 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 m1, 12,...,m be any collection of i linearly independent vectors in F for some i with 1sisn. Prove that there are 2 vectors +1 E F such that the vectors mi, m2, ..., mi, mi+1 are linearly dependent. Problem 5 - Cryptanalysis of a class of linear ciphers, 34 marks) Let F2 = {0,1} with the usual arithmetic modulo 2. The set = {0,1}" consisting of all n-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 F have coefficients 0 and 1. For any neN, let GI, (F2) denote the set of invertible nxn 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 = E, K = Gln (F2), and for all plaintexts (interpreted as n-bit column vectors with entries 0 and 1), encryption under a key matrix K is Ex() = K. Then for all ciphertexts c, decryption under K is obviously Dk(@=K-1. (a) (5 marks) Prove, by explicitly describing the key matrix K that encrypts an arbitrary plaintext vector to an arbitrary ciphertext vector c, 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 m1, 12,...,m be any collection of i linearly independent vectors in F for some i with 1sisn. Prove that there are 2 vectors +1 E F such that the vectors mi, m2, ..., mi, mi+1 are linearly dependent