MATH3302 – Sample Mid-Semester Examination Part A For each of the following multiple choice questions, circle the letter(s) corresponding to the correct answer(s). The number of correct answers is clearly indicated in each question. Each question having ONE correct answer is worth 1 mark. Each question having TWO correct answers is worth 2 marks. 1. Which ONE of the following integers does not have an inverse in Z26 ? (a) 3 (b) 7 (c) 13 (d) 19 (e) 21 2. Using an affine cipher with the key K = (a, b) = (3, 16), which ONE of the following letters is the ciphertext corresponding to the plaintext letter e? (a) B (b) C (c) E (d) F (e) M 3. Using the Playfair cipher with the following 5 × 5 array, which ONE of the following is the ciphertext corresponding to the plaintext hi? C G T K U (a) OE (b) AY O D I/J N A R Y P H B E F L M Q S V W X Z (c) EO (d) BN (e) TD 4. Using a row transposition cipher with the key π = (134)(25), which ONE of the following is the ciphertext corresponding to the plaintext lucky? (a) CYKLU (b) KYLCU (c) LYKCU (d) CUKLY (e) YKCUL 5. Using the ADFGVX cipher with the following substitution array and the keyword football, which ONE of the following is the ciphertext corresponding to the plaintext try? A D F G V X A D F G V X a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 (a) GDF XV A (b) XV AGF D (d) DGV AF X (e) V XGADF (c) AF DV GX 2 MATH3302 – Sample Mid-Semester Examination 6. Let the plaintext space and ciphertext space be the 26 letters of the English language. Which TWO of the following cryptosystems do not have perfect secrecy? (a) A general mixed alphabet in which all 26! keys are equally likely. (b) A modified shift cipher with keyspace {1, 2, . . . , 25} in which all 25 keys are equally likely. (c) A shift cipher in which all 26 keys are equally likely. (d) A shift cipher in which all even keys are used with probability 3/52 and all odd keys are used with probability 1/52. Recall that IDEA uses the operations ⊕, and which are defined as bitwise exclusive or, addition modulo 2n and multiplication modulo 2n + 1, respectively, where the n-bit blocks are considered as their integer values for and and the integer 2n is represented by the n-bit block of zeros for . For the following three questions, n = 4. 7. Which ONE of the following gives the value of 1101 ⊕ 1110? (a) 0010 (b) 1100 (c) 0011 (d) 1011 8. Which ONE of the following gives the value of 1110 0101? (a) 0001 (b) 1100 (c) 1000 (d) 0011 9. Which ONE of the following gives the value of 1100 0011? (a) 0010 (b) 1000 (c) 0100 3 (d) 0111 MATH3302 – Sample Mid-Semester Examination Part B Answer each of the following questions in the space provided. (Note that the space has been deleted to save paper for this sample exam.) The number of marks allocated to each question appears on the right. 10. (a) Briefly describe what is meant by the word cryptography. (2 marks) (b) List 5 properties that a cryptosystem should have to be considered a good cryptosystem. (5 marks) 9 4 11. Let C = P = Z26 , and let the encryption key for the Hill Cipher be K = . 1 3 Find the plaintext which encrypts to the ciphertext AB cipher and the key K. (Hint: first find the decryption key K −1 .) when using the Hill (5 marks) 12. (a) Briefly describe the Vigenere cipher, including a discussion of the encryption and decryption processes. (3 marks) (b) The following partial output was obtained by analysing some ciphertext from English plaintext. The first table gives some of the repeated strings found in the ciphertext, and the character positions within the ciphertext of the start of each of the repeated strings. The second table gives values of Friedman’s Index of Coincidence (IC) obtained for potential values of the keyword length m ranging from 1 to 6. String ejqe kbml vbrd xgmlb mlbqk fgt oatra Locations 177 237 306 330 419 459 150 206 152 308 336 244 345 346 426 m 1 2 3 4 5 6 IC 0.0480 0.0513 0.0508 0.0671 0.0507 0.0486 0.0582 0.0487 0.0696 0.0384 0.0572 0.0450 0.0683 0.0646 0.0436 0.0470 0.0538 0.0489 0.0588 0.0555 0.0634 (i) What information from these tables suggests that encryption was not done using a General Mixed Alphabet? (Explain your answer briefly.) (2 marks) (ii) Using Kasiski’s test, what is the most probable keyword length m used in the encryption? (Explain your answer briefly.) (2 marks) (iii) Using Friedman’s test (method 1), what is the most probable keyword length m used in the encryption? (Explain your answer briefly.) (2 marks) 4 MATH3302 – Sample Mid-Semester Examination 13. Consider a 4-stage LFSR stream cipher with initial key (k1 , k2 , k3 , k4 ) and keystream l1 , l2 , l3 . . . generated by lj = kj for j = 1, 2, 3, 4 and li+4 = c0 li + c1 li+1 + c2 li+2 + c3 li+3 for i = 1, 2, 3 . . . . (a) Explain why the linear recurrence relation li+4 = li+1 + li+3 would be a poor choice. (2 marks) (b) Suppose Oscar knows that a 4-stage LRSR stream cipher was used to encrypt the plaintext 101010101010 to obtain the ciphertext 001001011111. Determine the linear recurrence relation used. (5 marks) 14. Consider a cryptosystem with P = {a, b, c}, K = {k1 , k2 , k3 } and C = {A, B, C, D}. Let pP (a) = pP (b) = pP (c) = 1/3 and let pK (k1 ) = 1/2, pK (k2 ) = 1/3 and pK (k3 ) = 1/6. Let the encryption function be defined as ek (x) is the entry in row k and column x of the following table. a b c k1 B C D k2 C D A k3 D A B (a) Determine pC (A). (3 marks) (b) Determine pP (b|A). (3 marks) 15. (a) Describe what is meant by a ‘Feistel Cipher’. (3 marks) (b) DES includes S-boxes as part of its encryption and decryption steps. Each of eight S-boxes is a fixed 4 × 16 array, whose entries come from the integers 0, 1, . . . , 15. Describe in detail how DES transforms a 48 bit string into a 32 bit string using the S-boxes. (5 marks) (c) Without giving details of the algorithm, briefly discuss some of the shortcomings of DES. (2 marks) 5 MATH3302 – Sample Mid-Semester Examination 16. The Advanced Encryption Standard (AES) includes the operations addition, written +, and multiplication, written ∗, performed over the Galois Field of order 256, written GF[256]. (a) Elements of GF[256] can be written as bitstrings, as polynomials, and using hexadecimal notation. Write the element {4e} in bitstring and polynomial form. (2 marks) (b) Multiplication in the AES uses the irreducible polynomial m(x) = x8 + x4 + x3 + x + 1. Evaluate {01000011} ∗ {00010100} and give your answer as a bitstring. (You may use any method that you like.) (4 marks) 17. For the RSA algorithm, prove that if you encrypt a message x ∈ Zn and then decrypt the result, you obtain x ∈ Zn ; that is, prove the following statement. If x ∈ Zn , then (xb )a = x (mod n) where a, b, n are as defined for the RSA algorithm. (5 marks) 6 MATH3302 – Sample Mid-Semester Examination Reference Page a,A b,B c,C d,D 0 1 2 3 n,N o,O p,P q,Q 13 14 15 16 e,E f,F g,G h,H 4 5 6 7 r,R s,S t,T u,U 17 18 19 20 i,I j,J k,K 8 9 10 v,V w,W x,X 21 22 23 l,L 11 y,Y 24 m,M 12 z,Z 25 Tables 2 and 3 from the AES specification paper L(xy) y 0 x 0 1 2 3 4 5 6 7 8 9 a b c d e f 64 7d 65 96 66 7e 2b af 2c 7f cc 97 53 44 67 Table E(xy) x 0 1 2 3 4 5 6 7 8 9 a b c d e f 1 2 00 19 04 e0 c2 1d 2f 8a 8f db dd fd 6e 48 79 0a 58 a8 d7 75 0c f6 bb 3e b2 87 39 84 11 92 4a ed 2 Logs: L 3 4 5 6 7 8 9 a b c d e f 01 32 02 1a c6 4b c7 1b 68 33 ee df 03 0e 34 8d 81 ef 4c 71 08 c8 f8 69 1c c1 b5 f9 b9 27 6a 4d e4 a6 72 9a c9 09 78 05 21 0f e1 24 12 f0 82 45 35 93 da 8e bd 36 d0 ce 94 13 5c d2 f1 40 46 83 38 30 bf 06 8b 62 b3 25 e2 98 22 88 91 10 c3 a3 b6 1e 42 3a 6b 28 54 fa 85 3d ba 15 9b 9f 5e ca 4e d4 ac e5 f3 73 a7 57 50 f4 ea d6 74 4f ae e9 d5 e7 e6 ad e8 7a eb 16 0b f5 59 cb 5f b0 9c a9 51 a0 6f 17 c4 49 ec d8 43 1f 2d a4 76 7b b7 5a fb 60 b1 86 3b 52 a1 6c aa 55 29 9d 90 61 be dc fc bc 95 cf cd 37 3f 5b d1 3c 41 a2 6d 47 14 2a 9e 5d 56 f2 d3 ab d9 23 20 2e 89 b4 7c b8 26 77 99 e3 a5 de c5 31 fe 18 0d 63 8c 80 c0 f7 70 07 values such that {xy} = {03}L for a given a finite field element {xy} y 0 01 5f e5 53 4c 83 b5 fe fb c3 9f 9b fc 45 12 39 Table 1 2 3 4 5 6 7 8 9 a b c d e f 03 05 0f 11 33 55 ff 1a 2e 72 96 a1 f8 13 35 e1 38 48 d8 73 95 a4 f7 02 06 0a 1e 22 66 aa 34 5c e4 37 59 eb 26 6a be d9 70 90 ab e6 31 f5 04 0c 14 3c 44 cc 4f d1 68 b8 d3 6e b2 cd d4 67 a9 e0 3b 4d d7 62 a6 f1 08 18 28 78 88 9e b9 d0 6b bd dc 7f 81 98 b3 ce 49 db 76 9a c4 57 f9 10 30 50 f0 0b 1d 27 69 bb d6 61 a3 19 2b 7d 87 92 ad ec 2f 71 93 ae e9 20 60 a0 16 3a 4e d2 6d b7 c2 5d e7 32 56 fa 15 3f 41 5e e2 3d 47 c9 40 c0 5b ed 2c 74 9c bf da 75 ba d5 64 ac ef 2a 7e 82 9d bc df 7a 8e 89 80 b6 c1 58 e8 23 65 af ea 25 6f b1 c8 43 c5 54 1f 21 63 a5 f4 07 09 1b 2d 77 99 b0 cb 46 ca cf 4a de 79 8b 86 91 a8 e3 3e 42 c6 51 f3 0e 36 5a ee 29 7b 8d 8c 8f 8a 85 94 a7 f2 0d 17 4b dd 7c 84 97 a2 fd 1c 24 6c b4 c7 52 f6 01 3 Antilogs: field elements {E} such that {E} = {03}{xy} given the power {xy} 7

© Copyright 2020