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:
- 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 = Ea,b = (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. - (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 - (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. - (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] - 1 1 [1, 0, 0]
- x x [0, 1, 0]
- x2 x2 [0, 0, 1]
- x3 []
- x4 []
- x5 []
- x6 []
- 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 - (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? - (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. - (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 - (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 - (3 marks) Consider the following two protocols considered in the subject which are
variations of Needham-Schroeder protocol:
Protocol A (Denning’s Protocol): - A → KDC: IDA || IDB
- KDC → A: E(KA, [Ks||IDB||T ||E(Kb, [Ks||IDA||T])])
- A → B: E(KB, [Ks||IDA||T])
- B →A: E(Ks, N1)
- A → B E(Ks, f(N1))
Protocol B (An improvement to Denning’s Protocol): - A → B: IDA || Na
- B → KDC: IDB||Nb||E(Kb, [IDA||NA||Tb])
- KDC → A: E(KA, [IDB, Na||Ks||Tb])||E(KB, [IDA,Ks||Tb])||Nb
- 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. - (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