Part A

Please complete the Quiz on Canvas available at Assignments - Semester 2 Ex- ams, 2020 - Exam Part A

Part B: This Assignment:

1.  [2 marks] List two general methods employed to protect against replay attacks in protocols studied in the subject?  What are the main relative advantages and disadvantages of these two methods?

2.  [4 marks] For each of the following ciphers, compute number of possible non- trivial keys. A trivial key is the one which maps all elements to themselves.

(a) Cipher1 : A Vegenere Cipher defined over the alphabet GF(29) having a key of length between m1  and m2  characters.

(b) Cipher2 :  A transposition cipher over the alphabet GF(29) with a key length m3 .

(c) Cipher3 : A product cipher defined by product of Cipher1  and Cipher2 , where the plaintext symbols first encrypted by Cipher1   and then en- crypted by Cipher2 .

3.  [4 marks] Evaluate or simplify the following expressions.  Show the steps in your calculations.

(a) ap − 1 + (p − 1)a  mod p, where p is a prime number and a is an odd integer co-prime to p.

(b) Solve x in 3x14  + 4x10  + 6x − 18 ≡ (0 mod 5).

(a) What  are  the  important  require- ments  of a  modern  symmetric  ci- pher?

(b) We studied Fiestel cipher which is an example of an iterated block ci- pher. We consider a version of Fies- tel cipher with two rounds whose en- cryption ladder is illustrated below. Draw the corresponding decryption ladder.  You may assume any miss- ing information required in the func- tion definitions and data formats.

Figure 1. Encryption ladder of a two round Fiestel Cipher

5.  [2 marks] In RSA algorithm, if two primes p  =  29  and q  =  41  are used, what are the three smallest possible values for d?  Please show your working (however, you don’t need to show the steps for calculating modulo inverse).

6.  [3 marks] Consider GF(23 )  =  GF(2)[x] mod  (x3  + x2  + 1), a field with 8 elements.

(a) Express all the elements of GF(23 )  =  GF(2)[x] mod  (x3  + x2  + 1) as polynomials.

Table 1: Elements of GF (23 ) as powers of x

(b) Find the multiplicative inverse of the polynomial x2  + x in the above field.

7.  [4 marks] This question is about hash and MAC.

(a) Consider the following hash function based on RSA. The key < n, e > is known to the public. A message M is represented by blocks of predefined fixed size M1 , M2 , M3 , ..., Mm , m ≥ 1 such that Mi  < n and positive for all i ≤ m. The hash is constructed as follows: take the first block, XOR

with the second block, take the result and XOR with the third block, etc. Encrypt the final result using RSA. For example, the hash value of a message consisting of m blocks is calculated by

H(M) = H(M1 , M2 , ..., Mm ) =

(M1  XOR M2  XOR ... XOR Mm )e  mod n

Does this hash function satisfy each of the following requirements? Jus- tify your answers (with examples if necessary).

i. Variable input size

ii.  Fixed output size

iii.  Efficiency

iv.  Preimage resistant

v.  Second preimage resistant

vi.  Collision resistant

(b) What are the consequences of the above hash function being used in a public key signature algorithm?

8.  [3 mark] Assume the textbook RSA signature which uses no hash for this question.   Marvin  (an adversary) accidentally discovers a series of message and signature pairs in Alice’s computer.

(m1 , s1 ), (m2 , s2 ), (m3 , s3 ), (m4 , s4 ) and (m5 , s5 ),

where si  = (mi )d  mod n, 1 ≤ i ≤ 5.

Marvin wishes to create some new messages that are the functions of the above discovered messages as follows:

Which of the above messages could he forge and which could he not? Explain both the reasoning and the construction steps involved in the forged signatures.

9.  [2 marks] The following key distribution scenario was discussed in the subject, which is based on Needam/Schroder protocol where each user shares a unique master key with the key distribution centre (KDC).

Is this protocol susceptible to Man-in-the-Middle attack? If Yes, explain how it is susceptible. If No, explain why the attack is not effective. You can assume the symmetric key algorithm used is strong.