The University of Melbourne

Department of Computing and Information Systems

COMP90043-CRYPTOGRAPHY AND SECURITY

Practice Exam 2021

Exam Duration: 15 minutes reading + 120 minutes Exam writing;

Instructions to Students:

Total marks for the exam is 40 (Worth 40% of the final mark in the subject).

Note that you should complete writing the exam within 2.15 minutes. Then you will

have 30 minutes to scan and uplaod the work. Other exam rules apply.

The exam will have two parts: Part A is a quiz on canvas, Part B is this assignment

and will have 10 questions.

The test is open book, which means you may only use course materials provided

via the LMS or the text book but must not use any other resource including the

Internet.

You also must not contact or communicate with any other person (other than teach-

ing team) or make use of the Internet.

Solutions must be written on blank A4 page paper with pen and pencil. You must

write your solutions to each question on a new sheet of paper by clearly identifying

the question number.

You must not use tablet or any electronic device to generate your solution.

Scanning instructions are already made available on Canvas in an announcement.

Page 1 of 13 continued on next page

Part A (Q1-3

Please complete the Quiz on Canvas available at Assignments - Practice Exam - Part A

Part B: This Assignment:

1. Classical Ciphers (3 marks)

(a) The Vatsyana cipher is a specific version of a classical substitution cipher with

the following two conditions:

i. A character x is mapped to another distinct character y and

ii. If a character x is mapped to y, then the character y will be mapped to x.

In other words, substitution happens in pairs where the characters in each

pair are mapped to each other.

How many possible keys are there when the cipher is defined over 26 English

characters?

(b) Consider the following version of a classical cipher where plain text and cipher

text elements are from integers from 0 to 25. The encryption function, which

takes any plain text p to a cipher text c, is given by

c = E[a,b](p) = (ap + b) mod 26,

where a and b are integers less than 26.

Show how an adversary can attack the system under the “Chosen Plaintext

Attack” model.

2. (3 marks) This question is about computing the inverse of a number modulo n, where

n a positive integer. Note: Inverse of a number a mod n is a number x such that

xa = 1 mod n. In this semester, we studied methods for finding inverse modulo n

using the Extended GCD algorithm (XGCD) and Fermat’s or Euler’s theorems.

(a) When n is a prime number, write a pseudocode for the function inverse modulo

n using the properties of the Fermat’s theorem.

Page 2 of 13 continued on next page

(b) The Extended GCD algorithm (XGCD), also known as the Euclidean algo-

rithm, takes two given integers a and b as inputs and returns three integers g,

x and y such that

a x + b y = g,

where g is the greatest common divisor of the input integers.

You have provided the results from the XGCD function and exponentiation

modular identities below:

i. XGCD(12986, 46799) = 1, 8905,2471

ii. XGCD(12, 39) = 3,3, 1

iii. XGCD(17, 29) = 1, 12,7

iv. 1229 mod 31 = 13

v. 1029 mod 31 = 28

Now determine the inverse of the following numbers:

i. 12 mod 39

ii. 12986 mod 46799

iii. 17 mod 29

iv. 12 mod 17

v. 12 mod 31

vi. 10 mod 31

Page 3 of 13 continued on next page

3. (4 marks) This question is about hash and MAC.

(a) What is the main difference between hash functions and message authentication

codes (MAC)?

(b) Consider a version of the practical RSA signature algorithm discussed in the

lectures. Let n, e be Alice’s RSA public key and d be Alice’s private key. The

signature of a message m, 0 < m < n? 1 is given by

(m, s = (h(m))d mod n),

where h is a hash function. Answer the following questions:

i. What is the verification equation?

ii. Describe the “second preimage resistant” property of the hash functions.

Page 4 of 13 continued on next page

iii. A researcher discovers that the hash function used in the above scheme

failed the second preimage resistance property. What are the consequences

for the collision resistance property of the function and the security of the

signature algorithm? Explain your answers.

(c) (For Study) In the subject, we looked at the seven requirements of Hash func-

tions. Out of these, one-way property, second image resistance and collision

resistance are the three key requirements. Describe these three requirements.

4. (2 marks) Consider the finite field GF (23) as poynomails modulo 1 + x2 + x3 .

i Elements:xi As Polynomials As Vectors

?∞ 0 0 [0, 0, 0]

0 1 1 [1, 0, 0]

1 x x [0, 1, 0]

2 x2 x2 [0, 0, 1]

3 x3 [ ]

4 x4 [ ]

5 x5 [ ]

6 x6 [ ]

7 x7 1 [1, 0, 0]

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

(a) Complete the polynomial representations of the missing elements of the table.

(b) Solve the equation in y: xy = x3.

(c) Compute x3 + x6 + x5;

Page 5 of 13 continued on next page

5. (3 marks) Consider the ElGamal signature scheme over the prime field GF (q) given

in lectures. Let H be a public hash function, yA = a

xA mod q be the public key of

Alice, where xA, 1 < xA < q 1 is the private key and a is a primitive element in

the field. Alice uses the following equation to define the ElGamal signature scheme:

k S2 + xAS1 = m mod (q 1),

where m = H(M), M an arbitrary message and k, S1 and S2 are the signature

parameters used in the scheme.

(a) What are the signing and verification equations?

(b) What is the consequence of using same k for signing two different messages?

(c) What is the consequence if the function H used in the signing equation violates

the second preimage resistant property of hash functions?

6. (3 mark) Assume the RSA signature parameters for this question. Marvin (an

adversary) accidentally discovers the following message and signature pairs in Alice,s

computer.

(m1, s1) and (m2, s2),

where s1 = (m1)

d mod n and s2 = (m2)

d mod n. To his amazement, he discovers

that the message he wanted to forge was exactly m = (m31 m2) mod n. Is it possible

to forge Alice,s signature on the message m? If so, describe how to construct a forged

signature on the message. Note that in this question we assume the basic textbook

RSA signature scheme which do not employ any hash function.

7. (3 marks) Alice and Bob exchange their authentic RSA key parameters. Let na, ea

and nb, eb be public RSA parameters of Alice and Bob respectively. Similarly let da

and db be private RSA keys of Alice and Bob respectively. Let Ek() and Dk() be

encryption and decryption functions of the popular symmetric key cipher AES. Bob

wants to send a large file FILE to Alice as explained below:

Page 6 of 13 continued on next page

(a) Chooses a random session key ks, and encrypts as C = k

ea

s mod na.

(b) Encrypts FILE using the AES cipher as: ENC FILE = Eks(FILE).

(c) Computes h = HASH(FILE), where HASH is a public hash function.

(d) Computes the signature as S = hdb mod nb.

(e) Sends (ENC FILE, C, S) to Alice.

Now complete the missing parameters in the following steps to be performed by

Alice if the messages are error free and not tampered.

(a) ks = ............................. modna.

(b) FILE RECEIVED = ..............................

(c) h? = HASH(.............................).

(d) Seb mod nb = ..............................

Page 7 of 13 continued on next page

8. (2 marks) The following equations and figure describe one of the standard modes of

usage of symmetric key encryption.

Figure 1: A Standard Mode of Encryption

Encryption:

C1 = (EK [IV ⊕ P1]).

Cj = (EK [Cj?1 ⊕ Pj ]), j > 1.

(a) What is the name of this mode?

(b) Expand the abbreviations and functions used in the equations:

i. IV = .............................

ii. K = .............................

iii. Cj = .............................

iv. Pj = .............................

v. Ey[x] = .............................

(c) Complete the equations for decryption below:

Decryption:

P1 = ————–.

Pj = ————–.

(d) What is the effect on the plain text of a one bit error in the transmission of an

encrypted “block Cj”?

Page 8 of 13 continued on next page

9. (3 marks) Consider the following two protocols considered in the subject which are

variations of Needham-Schroeder protocol:

Protocol A (Denning’s Protocol):

1. A → KDC: IDA || IDB

2. KDC → A: E(KA, [Ks||IDB||T ||E(Kb, [Ks||IDA||T ])])

3. A → B: E(KB, [Ks||IDA||T ])

4. B →A: E(Ks, N1)

5. A → B E(Ks, f(N1))

Protocol B (An improvement to Denning’s Protocol):

1. A → B: IDA || Na

2. B → KDC: IDB||Nb||E(Kb, [IDA||NA||Tb])

3. KDC → A: E(KA, [IDB, Na||Ks||Tb])||E(KB, [IDA,Ks||Tb])||Nb

4. A →B: E(Kb, [IDA||Ks||Tb])||E(Ks, Nb)

(a) What is the role of T in Protocol A?

(b) What is Suppress-Replay Attack?

(c) Is Protocol A susceptible to Suppress-Replay Attack? Explain your answer and

suggest a remedy if your answer is yes.

Page 9 of 13 continued on next page

(d) Explain how Protocol B address the above susceptibility.

10. (4 marks)

(a) Describe the Diffie-Hellman (DH) key agreement protocol defined over the

group of integers modulo p, where p is a prime number. You are welcome

to use any assumptions required to complete the statement of the protocol.

Your answer should include the public parameters of the scheme and series of

messages exchanged between the users A and B.

Page 10 of 13 continued on next page

(b) Show how this protocol is susceptible to a man-in-the-middle attack.

Page 11 of 13 continued on next page

(c) Modify the protocol in part (a) so that it is secure against the vulnerability

found in part (b) using the public key certificate scheme as defined in this

subject. Briefly justify your solution. For your benefit, some relevant details

about the certificate scheme are given below. You may have to fill in missing

details if required.

Let [PUauth, PRauth] be the public and private key pair of the certificate

authority.

Let E(PU, .) and D(PR, .) be the public key encryption and decryption

functions used in the scheme.

The format of the certificate for a user A is given as CA = E(PRauth, [T ‖

IDA ‖ PUA]), where T is a timestamp.

Page 12 of 13 continued on next page

END OF EXAMINATION

版权所有：留学生编程辅导网 2020,All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。