C&O 487/687: Assignment #4 Due date: November 17, 2022 (Thursday)
Note: Some questions use randomization to customize to you specifically. Please include your
max-8-character UW user id (c544liu) at the beginning of your answer so we can look up your
custom solution.
1. [8 marks] Hybrid encryption.
Recently, the University of Waterloo LEARN server was hacked by a group calling themselves
“Really Super Awesome Association of Engineering Students” (RSA-AES), a terrorist organization
bent on world domination. The first phase of their evil plan is to ensure that engineering students
have better grades and hence get better co-op jobs than math students, so they hacked into the
LEARN server and encrypted this CO 487 assignment in hopes of causing you to get a lower mark
in this course. Luckily for you, they made some mistakes during encryption because they did not
take CO 487.
Your first task for this assignment is to decrypt the encrypted assignment PDF so that you can
actually do the rest of your assignment.1
I managed to capture some logs showing some of the Python code they used to encrypt the assign-
ments, which you might find helpful in figuring out how to break their encryption. This is in the
file a4q1 attacker log.py on LEARN.
You might have to do some number theory operations in Python as you try to solve this question.
Here are a few functions that might be helpful:
pow(x, y, z): computes xy mod z
factorint(x): attempts to factor the integer x, and if successful returns the factors and their
multiplicities; see documentation at https://docs.sympy.org/latest/modules/ntheory.
html?highlight=factorint#sympy.ntheory.factor_.factorint
mod inverse(x, z): computes x?1 mod z
pow is included with Python by default, but to get factorint and mod inverse, you have to install
an additional library called sympy (try running pip3 install sympy) and then importing those
functions into your program using the following source code:
from sympy import mod_inverse
from sympy.ntheory import factorint
(a) [4 marks] By inspecting a4q1 attacker log.py, describe 4 cryptographic mistakes made by
the hackers and what you would do differently.
(b) [3 marks] Describe the procedure you used to decrypt the file. Submit any code you write
through Crowdmark, as you would a normal assignment – as a PDF or screenshot. We will be
reading it, but not executing it.
(c) [1 marks] To prove that you successfully decrypted the file, copy the following random num-
ber into your solution: Your secret random number can only be obtained by decrypting your
encrypted assignment file.
Please include your max-8-character UW user id (c544liu) at the beginning of your
answer so we can look up your custom solution.
1You can also download the decrypted version of (most of) the assignment from LEARN if you want to get started on
other questions, but the decrypted version from LEARN is missing a part (worth a few marks) that can only be obtained
by decrypting your own customized encrypted assignment.
8jJUrTR5xXP3Vw
2. [4 marks] Diffie–Hellman equivalents.
Let p be a prime and let g be an element of large prime order q in Z?p. Show that the Diffie–Hellman
assumption is equivalent to the square Diffie–Hellman assumption, which is that: let a be chosen
uniformly at random from Z?p. Given g and ga, it is computationally infeasible to determine ga
2
.
To do so, you need to show two directions: DH assumption =? square DH assumption, and vice
versa.
Use the contrapositive. For example, the contrapositive of the forward direction is: if there is an
efficient algorithm A that breaks the square DH assumption, then we can use A to break the DH
assumption.
Note that the reverse direction is trickier than it may first appear.
3. [4 marks] ElGamal encryption.
Let G be a finite group of order q, and suppose that g ∈ G generates G. This means that G =
{g0, g1, . . . , gq?1}, i.e., every element of G can be written as gr for some r ∈ Zq.
The ElGamal encryption scheme uses key pairs of the form (z, gz), where z ∈ Zq is the private
key and gz is the public key. The encryption of a message m ∈ G under the public key gz is
(c0, c1) = (g
r,m(gz)r), where r ∈R Zq is chosen randomly for each encryption.
(a) [2 marks] Suppose that OD is an efficient decryption oracle for ElGamal under arbitrary public
keys. That is, given the inputs Z and (c0, c1), where Z = g
z and (c0, c1) = (g
r,m(gz)r) for
any z, r ∈ Zq, the oracle OD returns m.
Recall the Diffie–Hellman problem: given g, gx, and gy, compute gxy. Suppose that you are
given X,Y ∈ G, where X = gx and Y = gy. (The generator g is known to you, but x and y
are not.) Describe how to efficiently compute gxy using a single call to OD.
You may assume that computing inverses in G is efficient.
(b) [2 marks] Now, suppose that ODH is an efficient Diffie–Hellman oracle. That is, given the
inputs X = gx and Y = gy, the oracle ODH returns gxy.
You are given an ElGamal public key Z = gz and an ElGamal ciphertext (c0, c1) = (g
r,m(gz)r).
(The values Z, c0, and c1 are known to you, but z, r, and m are not.) Describe how to efficiently
compute m using a single call to ODH .
You may assume that inversion and multiplication in G can be computed efficiently.
4. [9 marks] Side-channel attacks.
In this problem, you will explore side channel attacks on elliptic curve cryptography. A side channel
attack targets a flaw in an implementation of a cryptosystem which may be secure in theory.
A hardware security module, or HSM, is a type of computer which is specifically designed to store
cryptographic keys and perform cryptographic operations in a secure fashion. An HSM provides
an interface whereby an authenticated user can request that operations such as hashing, signing,
and key generation can be performed. Usually, an HSM will not expose secret values to users. For
example, if Alice requests that an RSA key pair be generated, an HSM will securely store both the
public and the private key but output only the public key. Later, Alice can decrypt messages using
the stored private key by authenticating to the HSM and providing the message to be decrypted.
For this question, suppose that Alice is using an HSM to perform elliptic curve Diffie-Hellman
key exchange, with point multiplication implemented using the iterative double-and-add algorithm.
(See slides 21 and 23 of Topic 3.6.) You have sneakily installed a device on the HSM’s power supply
which allows you to observe its power consumption.
By observing Alice’s network traffic, you deduce that at 04:08:07 UTC time, she performed an
elliptic curve Diffie-Hellman key exchange with Bob.
Suppose that you observe the following graph for the power consumption of Alice’s HSM at
04:08:07:
8jJUrTR5xXP3Vw
(a) [2 marks] Determine the most significant byte (8 bits) of Alice’s private key, and explain how
you obtained your answer.
(b) [3 marks] Let E be the elliptic curve y2 = x3 ? x + 3 over the field Z7. Let P = (2, 3) and
Q = (5, 2) be points on E. Compute the following using the formulas from class:
i. P + P
ii. P + Q
iii. Q + Q
(c) [3 marks] Now, perform the same calculations using
m =
(xP + xQ)
2 ? xPxQ + a
yP + yQ
for both addition and doubling.
(d) [1 marks] How could the HSM’s implementation of double-and-add be modified to prevent the
side-channel attack from part (a)? You may assume that yP + yQ 6= 0 unless P = ?Q.
5. [5 marks] DSA.
Recall that in the signing step of the DSA, the signature must be regenerated if any of k, r, and s
are 0.
(a) [1 marks] What problems arise if k = 0?
(b) [2 marks] Show how an adversary can forge a signature on any message if signatures with r = 0
are released, and said adversary intercepts a signature of the form (0, s) and the corresponding
message. Explain why your forgery is a valid signature.
(c) [2 marks] Show how an adversary can forge a signature on any message if signatures with s = 0
are released, and said adversary intercepts a signature of the form (r, 0) and the corresponding
message. Explain why your forgery is a valid signature.
Academic integrity rules
You should make an effort to solve all the problems on your own. You are also welcome to collaborate
on assignments with other students in this course. However, solutions must be written up by yourself.
If you do collaborate, please acknowledge your collaborators in the write-up for each problem. If you
obtain a solution with help from a book, paper, a website, or any other source, please acknowledge your
source. You are not permitted to solicit help from other online bulletin boards, chat groups, newsgroups,
or solutions from previous offerings of the course.
8jJUrTR5xXP3Vw
Due date
The assignment is due via Crowdmark by 8:59:59pm on November 17, 2022. Late assignments will not
be accepted.
Office hours
Office hours will take place online via the Gather.town platform; see the link on LEARN under Contents
→ Course Information → Office hours.
Monday November 7 11am–12pm
Thursday November 10 1–2pm
Monday November 14 11am–12pm
Tuesday November 15 11am–12pm
Wednesday November 16 11am–12pm
Wednesday November 16 2–3pm
Wednesday November 16 4–5pm
Thursday November 17 1–2pm
Changelog
Tues. Nov. 8: assignment posted
Mon. Nov. 14: clarify wording in question 5