The University of Melbourne
School of Computing and Information Systems
COMP90043 Cryptography and Security
Assignment 2, Semester 2 2024
Due Date: Friday October 11, 23:59 AEST
Objectives
To improve your understanding of RSA, hash functions and ElGamal.
To develop problem-solving and design skills.
To improve written communication skills.
Questions
1. [10 marks] A manager selects two large primes, p and q, where p ̸= q, to set up a
secure communication channel between three employees, Alice, Bob, and Carlo, using
RSA encryption. He first computes n = pq and corresponding ϕ(n). Then, he uses
this < p, q > pair to generate three RSA key pairs (with different e being relatively
prime to each other and corresponding d), assigns them to the staff individually, and
destroys p, q, ϕ(n) immediately afterwards (meaning nobody knows the values). The
following lists the key pairs:
Alice: < n, eA >, < n, dA >
Bob: < n, eB >, < n, dB >
Carlo: < n, eC >, < n, dC >
Answer the following questions with detailed justification.
(a) [5 marks] Alice wants to send a message M to both Bob and Carlo, so she cal-
culates CB = M
eB mod n and CC = M
eC mod n. Explain how an adversary can
recover the message M without knowing private keys dB and dC .
(b) [5 marks] Carlo is interested in messages sent to Alice. Outline a strategy that
may help Carlo recover an alternative private key d′A that can perform the same
function as dA to decrypt messages sent to Alice.
2. [30 marks] Hash Functions.
(a) [15 marks] Consider the following hash function based on RSA function. The
key < n, e > is known to the public. A message M is represented by blocks
of predefined fixed size {M1,M2,M3, ...,Mm} such that 0 ≤ Mi < n. We can
assume that n is large enough to hold the RSA assumptions. The hash value is
calculated by:
1
H(M) = ((M1 ⊕M2 ⊕ ...⊕Mm)e) mod n
Does this hash function satisfy each of the following requirements? Justify your
answers. You can give examples, if necessary, to support your arguments.
i. [3 marks] Fixed output size
ii. [3 marks] Efficiency (easy to calculate)
iii. [3 marks] Preimage resistant
iv. [3 marks] Second preimage resistant
v. [3 marks] Collision resistant
(b) [15 marks] Explain how to efficiently find collisions in the following hash functions:
i. [5 marks] The function Ha : {0, 1}512 → {0, 1}256 is defined as follows:
Ha(x, y) = F (y, x⊕ y)⊕ y.
Let the pair F, F−1 be a public secure symmetric key block cipher with block
size and key length 256. That is, y is interpreted as the ‘symmetric key’, and
x⊕ y is the ‘plaintext’ for F . To compute Ha, we first XOR y with x, then
apply the block cipher to the result, and finally XOR the block cipher output
with y one more time to get the final output.
ii. [5 marks] Hb = F (y ⊕ x, x), where F, F−1 is as in last question (i). x ⊕ y is
the ‘key’ and y is the ‘plaintext’.
iii. [5 marks] Hc : {0, 1}257 → {0, 1}256 is defined as follows: Let H : {0, 1}∗ →
{0, 1}256 be a collision-resistant hash function for arbitrary-length messages,
then for x||b ∈ {0, 1}257, Hc(x, b) = H(x) if b = 0 and Hc(x, b) = H(H(x)) if
b = 1. Here, a||b refers to concatenating a and b together as a single string.
3. [20 marks] ElGamal.
(a) [10 marks] ElGamal Encryption
A variant of ElGamal crypto system over the prime field GF (q) is given as follows.
Assume the parameters are as discussed in the lectures. Let yA = a
xA mod q,
be the public address of Alice, where xA, 1 < xA < q − 1, is Alice’s private key.
Encryption function is defined as follows:
E(M) = [C1, C2],
where C1 = a
k mod q, where k is a random integer 1 ≤ k ≤ q − 1, C2 = K ⊕M ,
where K = ykA mod q and ⊕ is binary XOR applied to binary representation of
K and M .
i. [5 marks] Describe the Decryption Function D(C1, C2) that Alice can use to
recover the message.
ii. [5 marks] Show how the security of the encryption function is based on Com-
putational Diffie-Hellman (CDH) problem.
CDH Problem: Let q be a prime number and a be a generator of the mul-
tiplicative cyclic group of modulo q. Given ax, ay, the CDH problem is to
compute axy.
2
(b) [10 marks] ElGamal signature.
Let’s consider a variant of ElGamal signature over the prime field GF (q). Let
H be a public hash function and let 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 a related ElGamal signature
scheme by using:
m S2 + xAS1 = k mod (q − 1),
where m = H(M), M an arbitrary message, k a random number, S1 = a
k mod q
and S2 are signature parameters. The signature for a message M is represented
as [M,S1, S2].
i. [5 marks] What are the signing and verification equations?
ii. [5 marks] Is this shceme secure? Justify your answer with reasons.
4. [15 marks] We studied the Needham–Schroeder protocol in lectures. An alternative
key distribution method suggested by a network vendor is illustrated in the figure
below.
Figure 1: Key Distribution Between A and B.
(a) [5 marks] How do A and B know that the key is freshly generated?
(b) [5 marks] How could A and B know that the key is not available to other users
in the system?
(c) [5 marks] At this stage, A and B cannot authenticate with each other. Explain
why and extend the scheme with a few steps so that A and B can authenticate
with each other. Your modifications should be based on symmetric key methods
used in this key distribution protocol, not public key primitives.
5. [NO marks] Additional Question:
*******************
3
Following questions are NOT counted to your marks of this assignment.
However, we strongly encourage you to have a try.
*******************
(a) Use two primes:
10921304574392093059217153525481121125933934477429 and 89855181341172893110
764453512406142438324081807631 to construct an RSA key. Determine the small-
est valid RSA public exponent and its corresponding private key. Show the
detailed workings with an explanation justifying your answer. You need
to attach any code you implemented in the appendix (do NOT use screenshots
for code) or mention the tools you used.
(b) Consider the following version of a classical cipher where plaintext and ciphertext
elements are from Z31. The encryption function, which maps any plaintext p to
a ciphertext c, is given by
c = Ea(p) ≡ a× p2(mod 31),
where a from the Z31.
i. Generally, finding a square root (known as quadratic residue) in module
arithmetic is difficult. In fact, for a b, deciding if there is an x such that
x2 ≡ b mod n is hard. Determine the decryption function for c. HINT: As a
starting point, you may try to solve c={YOUR STUDENT NUM}mod 29,
a={YOUR STUDENT NUM}2 mod 29.
ii. However, if the module is a special prime, we have a general formula for
getting the root. Derive the decryption function for this scheme. Show your
work. (0 mark for solutions like
√
x mod 31)
iii. Should this cipher be considered as mono-alphabetic cipher or poly-alphabetic
cipher? Why?
iv. Assume there is a helper that can output the corresponding ciphertext for
an arbitrary plaintext you supply. Describe an efficient way to retrieve the
key using this helper. You may have noticed that there are two potential
plaintexts regarding one ciphertext. Find a simple way to slightly tweak the
encryption scheme so that the receiver can confirm which root is the correct
plaintext.
(c) A commitment scheme is a digital analog of a “sealed envelope.” Specifically, a
sender can commit to a message m and send the resulting commitment c to a
receiver (i.e., seal the message in an envelope). The commitment c should not
reveal anything about the committed value m. Later on, the sender can open up
the commitment and convince the receiver that c is indeed a commitment to the
message m (i.e., open up the envelope and recover the original message). The
commitment scheme is hiding if c hides the message m and is binding if the sender
cannot open the commitment c to any message m′ ̸= m. In this problem, we will
construct a commitment scheme from the discrete log assumption:
4
• Public parameters: Let G be a group of the prime order p and let g, h ∈ G
be arbitrary elements of G, and are not identity element.
Identity element: an element that leaves unchanged every element when the
operation is applied.
• Commitment: To commit to a message m ∈ Zp, sample r ← Zp and output
the commitment c← gmhr.
• Open: To open the commitment c to the message m, the sender gives (m, r)
to the receiver and the receiver checks that c = gmhr.
i. Show that the above commitment scheme is perfectly hiding (i.e., the com-
mitment c does not leak any information about the committed message m).
Namely, show that given the commitment c ∈ G, every candidate message
m′ ∈ Zp is equally likely (over the randomness of r). One way is to show for
every m′ ∈ Zp, there is a unique r′ ∈ Zp such that c = gm′hr′ .
ii. Show that the above commitment scheme is computationally binding assum-
ing hardness of discrete log in G. Namely, show that if an efficient adversary
can output a commitment c together with openings (m, r) and (m′, r′) such
that gmhr = c = gm
′
hr
′
and m ̸= m′, then it means the adversary can know
the value of a given h = ga.
Remember to give a brief explanation why any inverses you take actually exist.
Hint: Assume h = ga
5
Submission and Evaluation
• You must submit a PDF document via the COMP90043 Assignment 2 submission
entry on the LMS by the due date. Handwritten, scanned images, and/or Microsoft
Word submissions are not acceptable — if you use Word, create a PDF version for
submission.
• Late submission will be possible, but a late submission will attract a penalty of 10%
available marks per day (or part thereof). Requests for extensions on medical grounds
will need to be supported by a medical certificate. Any request received less than 48
hours before the assessment date (or after the date) will generally not be accepted
except in the most extreme circumstances.
• This assignment will be marked out of 75 marks, and will contribute to 7.5% of your
total marks in this subject. Marks are primarily allocated for the correctness of your
thinking and clarity of your communication, rather than (only) the correct result
without sufficient justification.
• We expect your work to be neat — parts of your submission that are difficult to read
or decipher will be deemed incorrect. Make sure that you have enough time towards
the end of the assignment to present your solutions carefully. The time you put in
early will usually turn out to be more productive than a last-minute effort.
• You are reminded that your submission for this assignment is to be your work. For
many students, discussions with friends will form a natural part of the undertaking
of the assignment work. However, it is still an individual task. You are welcome
to discuss strategies to answer the questions, but not to share the work (even draft
solutions) on social media or discussion boards. It is University policy that cheating
by students in any form is not permitted, and that work submitted for assessment
purposes must be the independent work of the student concerned.
Please see https://academicintegrity.unimelb.edu.au
If you have any questions, you are welcome to post them on the Ed discussion board so
long as you do not reveal details about your own solutions. We encourage you to make your
questions public, so that Your classmates may also benefit from the discussion should they
have a similar concern.