COMP2300编程设计代做、代写Java，CSS程序、Python编程代做

日期：2021-05-30 08:29

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.

5