Cryptography III Assignment 1 1. Suppose we use the Vigenere cipher using 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 XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX a) Suppose we encrypt the word...

cryptography


Cryptography III Assignment 1 1. Suppose we use the Vigenere cipher using 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 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 a) Suppose we encrypt the word ARTHUR using the keyword FORD. Compute the ciphertext. b) Suppose we know a matching plaintext/ciphertext pair: plaintext = ARTHUR ciphertext = DVGAXV. What is the keyword? 2. We define a new cipher. Let m and n be positive integers. Write out the plaintext into m × n rectangles. Then form the ciphertext by taking the columns of these rectangles in order. For example, with m � 4 and n � 3 we would encrypt the plaintext CRYPTOGRAPHY by forming the following rectangle: C R Y P T O G R A P H Y The ciphertext would then be CTAROPYGHPRY. a) Describe how Bob would decrypt a ciphertext (given he knows the values m � 4 and n � 3). b) Decrypt the following ciphertext, which was obtained using this method of encryption: AYSLSUWAMASETORHSKACNTAOWEOSARTLIHGTHUMUYSOE 3. Suppose we have a symmetric key algorithm with encryption rule Ek(x), and we want to increase the security. An obvious approach is to try a ‘double encryption’. That is, to apply the same cipher twice, using different keys k1,k2 each time, and so use the encryption rule E(x) � Ek2(Ek1(x)). We consider this for the affine cipher, and show that a double encryption with the affine cipher is only as secure as single encryption. (As is often the case in cryptography, the result is different from the expected and/or desired one.) Consider the affine cipher and two different keys k1 � (a1,b1), k2 � (a2,b2). So we have the two encryption rules Ek1(x) � a1x+ b1 (mod 26) Ek2(x) � a2x+ b2 (mod 26). a) Suppose we encrypt a plaintext by first using the encryption rule Ek1 , then using Ek2 on the result, that is, use the encryption rule E(x) � Ek2(Ek1(x)). Show that there is a single encryption rule Ek3(x) � a3x+ b3 (mod 26) which performs exactly the same encryption, that is, Ek3(x) � Ek2(Ek1(x)). b) Find the values for a3,b3 when Ek1(x) � 3x+ 5 (mod 26) Ek2(x) � 11x+ 7 (mod 26). c) Check your solution by: i. encrypt the plaintext NO first using Ek1 and then encrypt the result using Ek2 ii. encrypt the plaintext NO using Ek3 . d) Suppose an exhaustive key-search attack is applied to a double-encrypted affine ciphertext, is the effective key space increased? (Explain your answer.) 4. The complexity of a computer algorithm gives the time needed to run the algorithm in terms of the length of the input. If a,b are two n-bit numbers, then assume the following: • the calculation a+ b has complexity n • the calculation a× b has complexity n2 • the calculation ab has complexity n3. Suppose we have a computer processor which performs one million operations per second, compute the time taken for calculations of the following complexities in the cases when n � 32, 64, 128, 256. Summarise your answers in a table formatted as follows. Complexity n � 32 n � 64 n � 128 n � 256 n n2 n3 2n