COMP2300/COMP6300 Applied Cryptography
Assignment 2
Total marks: 30
Weighting: 15%
Deadline: Tuesday (Week 13), 1 June 2021 (11:59 pm).
Note: Submit the assignment via Turnitin (Include Student Name and ID in assignment).
Objectives
This assignment has been designed to test your knowledge of public-key cryptography and application of
cryptography in cryptocurrencies.
Notes
• Assumptions (if any) must be stated clearly in your answers.
• There may not be one right answer for some of the questions. So, your explanations need to present
your case clearly. The explanations you provide do not have to be long; conciseness is preferred to
meandering.
• The hints to solutions of almost all questions in this assignment are in the lecture slides, and the
textbooks [Sma16] and [NBF+16].
1
Submission
• On line submission via Turnitin.
Assignments will be marked and returned online. There are no hardcopy submissions for written assignments.
Ensure you submit the correct file. The submission process shows you a complete preview of your entire
assignment after you have uploaded it but before you have submitted it. Carefully check through every
single page to ensure everything is there and the correct version has been uploaded.
Multiple submissions may be possible via Turnitin prior to the final due date and time of an assessment task
and originality reports may be made available to students to view and check their levels of similarity prior to
making a final submission. Students are encouraged to use these reports to ensure that they do not breach
the Academic Honesty Policy through high levels of similarity (plagiarism).
Teaching staff will use the report to judge whether plagiarism has occurred and whether penalties should
apply for breaches of the Academic Honesty Policy. Any similar text identified by Turnitin will be considered
carefully to see if it is indeed a breach of the Academic Honesty Policy.
2
Question 1 (6 marks)
Recall the (randomised) Elgamal cryptosystem. Let p be a prime. Let G be the group Z
∗
p = {1, 2, . . . , p − 1}
under multiplication modulo p. Let g ∈ G be a generator of the group. Let (x, h) denote Bob’s (private key,
public key) pair, where x is a random element of Zp−1 = {0, 1, . . . , p − 1}, and h ≡ g
x
(mod p).
(a) Suppose Alice sends a message m ∈ G with ciphertext c = (c1, c2) to Bob, encrypted using a random
k ∈ Zp−1. Suppose Eve, the eavesdropper, comes to know both the message m, and its ciphertext c. Explain
what can Eve do if Alice were to encrypt m0 ∈ G using the same k, resulting in ciphertext c
0 = (c
0
1
, c0
2
). (2
marks)
An encryption system is considered malleable if given a ciphertext of some unknown plaintext, it is possible
to obtain a valid ciphertext of a related plaintext without even knowing the contents of the plaintext. This is
problematic depending on the application. For instance, in bidding for a contract, a company might outbid
its competitor by simply multiplying it’s rival company’s encrypted bid by 0.9, without even knowing the
bid [DDN03]. The following questions relates to the malleability of the Elgamal cryptosystem taught in the
lecture.
(b) Suppose we are given the ciphertext c = (c1, c2) of some unknown message m, where c1 ≡ g
k
(mod p)
for some unknown random integer k ∈ Zp−1 and c2 ≡ m · h
k
(mod p), where h is the public key of some
unknown private key x, in the Elgamal cryptosystem. Let m0 be a message that you know. Can you obtain
a valid ciphertext of the message m · m0 without knowing m? (2 marks)
(c) Let p = 227. Given the following ciphertext of some message m1 encrypted using randomized Elgamal,
what is the ciphertext of m1 · m2, where m2 ≡ 11 (mod p)? Show the steps in PARI/GP. (1 mark)
(c1, c2) = (48, 3)
(d) Continuing from part(c), suppose the private key is x = 73. What is the message m1? (1 mark)
Question 2 (6 marks)
Let X be a random variable taking on n values with probabilities p1, p2, . . . , pn. Recall from Lecture 9 that
the min-entropy of X, denoted E∞(X), is given by
E∞(X) = min
i
1
pi
.
If X is uniformly distributed then p1 = p2 = · · · = pn =
1
n
.
(a) Show that if X is not uniformly distributed then necessarily one of the pi
’s is > 1/n. (2 marks)
(b) Show that if X is not uniformly distributed then E∞(X) < n. (2 marks)
(c) Argue that min-entropy is the highest if X is uniformly distributed. What is the minimum entropy in
this case? (2 marks)
Question 3 (2 marks)
Let H be a hash function that has the properties of hiding and collision-resistance. Recall that collision
resistance property means that it is infeasible to find two inputs x, y with x 6= y such that H(x) = H(y).
3
Consider the commitment scheme from Lecture 9. To commit to a message m, Alice samples a random
nonce r, and computes
C = H(r||m),
and publishes C as her commitment. A commitment scheme is binding if it is infeasible to find two pairs
(m, r) and (m0
, r0
) with m 6= m0
such that
H(r||m) = H(r
0
||m0
).
Show that if you can find a collision in H, this does not necessarily break the binding property of the
commitment scheme. (2 marks)
Question 4 (3 marks)
In lecture 10, we saw that the initial value for block reward for bitcoins was 50 Bitcoins, which halves every
210,000 blocks. Recall that the sum of an infinite geometric series is
S = a + ar + ar2 + ar3 + · · · =
a
1 − r
,
where a is the starting coefficient, and r is the common ratio between adjacent terms. Since new Bitcoins
can only be created if a new block is created, using the above formula, calculate the final number of Bitcoins
that will ever be created. Your answer should explain your choice of a and r. (3 marks)
Question 5 (3 marks)
Recall from Lecture 10 that a 51% attacker is an attacker who holds at least 51% of the total hash power.
Let α represent the proportion of hash power held by this attacker. Then, α ≥ 0.51. Suppose this attacker
wants to suppress Carol’s transactions by not including any of her transactions. To do so, whenever the
attacker (or the attacker’s nodes) solves the hash puzzle, it proposes a block without Carol’s transactions.
Show that the attacker will be successful in the sense that the longest valid consensus chain will eventually
be the one proposed by the attacker. Why this will not be the case if α < 0.5?(3 marks)
Question 6 (10 marks)
Recall hash puzzles from Lecture 10. In this question, we will see how they work in practice. This question
requires programming in a language that has an implementation of SHA-256 hash function. You could use
Java to program, although, you are free to use any other language with a library containing SHA-256, e.g.,
Python’s hashlib. Create a string s containing all the digits in your student ID. For example, if my student
ID is MQ12345678, then s = 12345678. Set the target t to:
t =
2
256
20
Let H be the SHA-256 hash function. Let r be a counter starting from 0.
(a) Implement a program that tries successive values of r, i.e., r = 0, 1, 2, 3, . . ., computes H(s||r), compares
it with t and halts whenever H(s||r) < t, with the output r. You need to provide the program and the
output r. (5 marks)
4
(b) Modify the program from part (a) by adding i to s, where i = 0 to 999 inclusive, and for each i computing
the hash until the value falls before the target. What is the average number of attempts (over 1,000) before
you found the target? You need to provide your program. (3 marks)
(c) If you drew random values between 0 and 2255 inclusive, how many attempts on average it would take
before you find a value below the target? What does it tell you about SHA-256? (2 marks)
References
[DDN03] Danny Dolev, Cynthia Dwork, and Moni Naor. Nonmalleable cryptography. SIAM review,
45(4):727–784, 2003.
[NBF+16] Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven Goldfeder. Bitcoin
and cryptocurrency technologies: a comprehensive introduction. Princeton University Press,
2016.
[Sma16] Nigel P Smart. Cryptography made simple, volume 481. Springer, 2016.