Question 1
(a) Suppose you have a network of n users. You need to protect the communication in the network such that a non-user cannot read the messages transmitted. On the other hand, every user can read all the messages. How many keys do you need if you are using a secret-key algorithm to encrypt the message?
(b) Explain the following types of cryptanalytic attacks:
(i) Ciphertext only
(ii) Chosen plaintext
(iii) Chosen ciphertext
(a) You just need to have 1 key.
This is because every user can use the same key to encrypt and decrypt all the messages; whereas a non-user without the key cannot read any of the messages.
There is a key management issue. If one of the users’ machine is compromised, the key for the entire network will need to be changed. This could be a complex process.
(b)
Ciphertext only: One possible attack is the brute-force approach of trying all possible keys. If the key space is very large, this becomes impractical. Thus, the opponent must rely on an analysis of the ciphertext itself, usually applying various statistical tests to it.
Known plaintext: The analyst may be able to capture one or more plaintext messages as well as their encryptions. With this knowledge, the analyst may be able to deduce the key on the basis of the way in which the known plaintext is transformed.
Chosen plaintext: If the analyst is able to choose the messages to encrypt, the analyst may deliberately pick patterns that can be expected to reveal the structure of the key.
Question 2
(a) Consider a symmetric key algorithm with a 11-bit key. Suppose you are using this algorithm. How many times do you have to try to obtain the key for the following cases?
(i) the best case
(ii) the worst case
(iii) the average case.
Explain your answers.
(b) Consider the two plaintext-ciphertext pairs (P1, C1) and (P2, C2). The ciphertext C1 is obtained by encrypting the plaintext P1 using an algorithm with a 20 bits key K1. The C2 is obtained by encrypting P2 using another algorithm with a 40 bits key K2.
(i) Suppose exhaustive search is used to find the keys. Which key is more likely to take a shorter time to find? Explain your answer.
(ii) Is it possible that you could obtain the other key first? Explain your answer.
Solutions:
(a)
(i) For the best case, you need only one try.
This is because each try has an equal chance to succeed. If you happen to choose the correct one in the first try, you will get the key.
(ii) For the worst case, you need 211 = 2048 tries.
This could happen when the correct key happens to be the last one you try.
(iii) On the average, you have to do (1/2)*2048=1024 tries.
If you do a large number of tries, statistically, the average will give half of the maximum tries i.e. 1024 tries.
(b)
(i) Most likely, K1 will be found first. This is because K1 (20 bits) has a smaller search space than K2 (40 bits).
(ii) Yes, it is possible. This is because one cannot be certain how long the search is needed. One could be lucky to select the correct key, K2, first.
Question 3
A company is run by a management committee, consisting of a CEO, Bob, and 4 managers: Mary, John, Tan and Lee. You are required to set up a secure means of communications among the five persons. Each pair of users must have a means of sending each other confidential message that the rest are unable to decipher. Suppose you want to use AES. How many keys are required? List down all the keys needed.
Solutions
Given the 5 users are Bob, Mary, John, Tan and Lee. There will be 10 keys needed as follows:
Bob and Mary will need a key K(B, M)
Bob and John will need a key K(B, J)
Bob and Tan will need a key K(B, T)
Bob and Lee will need a key K(B, L)
Mary and John will need a key K(M, J)
Mary and Tan will need a key K(M, T)
Mary and Lee will need a key K(M, L)
John and Tan will need a key K(J, T)
John and Lee will need a key K(J, L)
Tan and Lee will need a key K(T, L)
Question 4
(a) What is the difference between a monoalphabetic cipher and a polyalphabetic cipher?
(b) Given the monoalphabetic cipher as follows:
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
m n b v c x z a s d f g h j k l p o i u y t r e w q
(i) Using the above cipher, encode the message “This is an easy problem”
(ii) Using the above cipher, decode the message “rmij’u uamu xyj”
(a) A monoalphabetic cipher maps a plaintext alphabet to a ciphertext alphabet, so that each letter of the plaintext alphabet corresponds to a single unique letter of the ciphertext alphabet.
A polyalphabetic cipher uses a separate monoalphabetic cipher for each successive letter of plaintext, depending on a key.
(b) (i) The encoding gives: “uasi si my cmiw lokngch”
(ii) The decoding gives: “wasn’t that fun”