THE UNIVERSITY OF CALGARY FACULTY OF SCIENCE DEPARTMENT OF COMPUTER SCIENCE DEPARTMENT OF MATHEMATICS & STATISTICS MIDTERM EXAMINATION 1 FALL 2018 CPSC 418/MATH 318 L01 October 17, 2018 Time: 50 minutes NAME: COURSE (circle one): CPSC 418 MATH 318 Please DO NOT write your ID number on this page. Instructions: Answer all questions in the space provided. Show all your work. Use the last two pages to continue answers if you need more space, or as rough paper. No aids are allowed. Total marks: 50 CPSC 418/MATH 318 (cont’d.) Name: Page II of X ID: Question Score Out Of 1. Multiple Choice Questions 5 2. True/False Questions 6 3. Definitions and Short Answer Questions 11 4. Perfect Secrecy 8 5. Entropy 10 6. Polynomial Arithmetic 4 7. Affine Linear Cipher 6 Total: 50 CPSC 418/MATH 318 (cont’d.) Name: Page III of X ID: 1. [5 points] Multiple Choice Questions For each question, check exactly one answer. (a) [1 point] Which of the following is not a substitution cipher? ◦ Shift cipher ◦ Vigene`re cipher ◦ One-time pad ◦ All the above ciphers are substitution ciphers (b) [1 point] Which of the following is an active attack? ◦ Ciphertext-only attack ◦ Known plaintext attack ◦ Chosen plaintext attack ◦ None of the above attacks is active. (c) [1 point] Assuming that keys are chosen with equal likelihood, what is the entropy of the key space for triple DES? ◦ 56 ◦ 112 ◦ 168 ◦ none of the above (d) [1 point] Which of the following is not a product cipher? ◦ DES ◦ AES ◦ One-time pad ◦ All the above ciphers are product ciphers (e) [1 point] Which component of AES is non-linear? ◦ SubBytes ◦ ShiftRows ◦ MixColumns ◦ AddRoundKey CPSC 418/MATH 318 (cont’d.) Name: Page IV of X ID: 2. [6 points] True/False Questions Answer every questions with TRUE or FALSE. No explanations are required. (a) [1 point]. The Vigene`re cipher is a monoalphabetic substitution cipher. (b) [1 point] The one-time pad provides perfect security if each key is used with equal like- lihood. (c) [1 point] Diffusion in a cipher is achieved through S-boxes. (d) [1 point] AES is based on a Feistel network structure, just like DES. (e) [1 point] Linear cryptanalysis is used exclusively to break linear ciphers. (f) [1 point] The number of rounds in the Rijndael algorithm depends on the key length. CPSC 418/MATH 318 (cont’d.) Name: Page V of X ID: 3. [11 points] Definitions and Short Answer Questions (a) [2 points] State Kerckhoff’s principle. (b) [2 points] Describe what information an adversary is assumed to have when mounting a known plaintext attack? (c) [2 points] Define what it means for an attack on a cryptosystem to be active. (d) [3 points] Define what it means for a cryptosystem to provide perfect secrecy. Explain all your notation. (Note that this question asks for the definition, not equivalent char- acterizations.) (e) [2 points] What is the worst case computational effort required for a brute-force attack on a block cipher with n-bit keys? CPSC 418/MATH 318 (cont’d.) Name: Page VI of X ID: 4. [8 points] Perfect Secrecy Consider a cryptosystem with plaintext spaceM = {x, y, z}, ciphertext space C = {a, b, c, d} and key space K = {K,L}. Suppose encryption is given by the following table: x y z K a b c L b c d Assume that keys are chosen equiprobably for encryption, i.e. p(K) = p(L), and that the plaintexts x, y, z occur with respective probabilities p(x) = 1/6, p(y) = 1/3, p(z) = 1/2. Recall the formulas for conditional and unconditional probabilities of ciphertexts: p(C|M) = ∑ K∈K EK(M)=C p(K) and p(C) = ∑ K∈K C∈EK(M) p(K)p(DK(C)) (C ∈ C, M ∈M) . (a) [3 points] Compute p(b|x). (b) [3 points] Compute p(b). (c) [2 point] Does this system provide perfect secrecy? Why or why not? CPSC 418/MATH 318 (cont’d.) Name: Page VII of X ID: 5. [10 points] Entropy Consider a function on a set X of 5 elements that takes on the 5 respective values 1/2, 1/4, 1/8, 1/16, 1/16. (a) [2 points] Is this a probability distribution? Why or why not? (b) [4 points] What is the entropy H(X)? Compute the actual numerical value as a fraction. (c) [2 points] Is this the maximal value for the entropy of any sample space with 5 outcomes? Why or why not? (d) [2 points] For what probability distribution on a sample space X with 5 outcomes does the entropy H(X) take on its minimal value? What is the value of H(X) in this case? CPSC 418/MATH 318 (cont’d.) Name: Page VIII of X ID: 6. [4 points] Polynomial Arithmetic Let f(x) = x3 + x + 1 , g(x) = x2 + 1 be polynomials with binary coefficients. Compute f(x)g(x) mod (x4 + 1). CPSC 418/MATH 318 (cont’d.) Name: Page IX of X ID: 7. [6 points] Affine Linear Cipher The affine linear cipher is a generalization of the shift cipher as follows. Plaintexts and ciphertexts are elements in Z26 (the integers modulo 26), and keys are pairs (J,K) with J,K ∈ Z26 and gcd(J, 26) = 1. The encryption of a message M under a key (J,K) is given by C ≡ JM + K (mod 26) (0 ≤ C ≤ 25) . (a) [2 points] Find the encryption of the plaintext M = 12 under the affine linear cipher key (J,K) = (3, 4). (b) [4 points] Find the decryption of the ciphertext C = 5 under the affine linear cipher key (J,K) = (3, 4). CPSC 418/MATH 318 (cont’d.) Name: Page X of X ID: ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ RS / rs
