PFA
COMP2300/COMP6300 Applied Cryptography Assignment 2 Total marks: 30 Weighting: 15% Deadline: Friday (Week 12), 29 October 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 (8 marks) This question tests your knowledge of what constitutes a group. Let n be a composite number. Let X = {1, 2, . . . , n− 1}. (a) Let x ∈ X. Show that if there are integers a, b such that ax+ bn = 1, then gcd(x, n) = 1. (2 marks) (b) Let x ∈ X. Show that if gcd(x, n) 6= 1 then ax ≡ 1 (mod n) has no solution for any integer a. (2 marks) (c) Show that there is at least one element x ∈ X, such that gcd(x, n) 6= 1. (2 marks) (d) Let ∗ be multiplication modulo n. That is, for x, y ∈ X, x ∗ y = xy (mod n). Prove that (X, ∗) is not a group. (2 marks) Question 2 (4 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. (a) Suppose we are given the ciphertext c = (c1, c2) of some unknown message m, where c1 ≡ gk (mod p) for some unknown random integer k ∈ Zp−1 and c2 ≡ m · hk (mod p), where h is the public key of some unknown private key x, in the Elgamal cryptosystem. Let m′ be a message that you know. Can you obtain a valid ciphertext of the message m ·m′ without knowing m? (2 marks) (b) Let p = 739. Given the following ciphertext of some message m1 encrypted using randomized Elgamal, what is the ciphertext of m1 ·m2, where m2 ≡ 2 (mod p)? Show the steps in PARI/GP. (1 mark) (c1, c2) = (246, 609) Note that the integers are reduced modulo p. (c) Continuing from part(c), suppose the private key is x = 419. What is the message m1? (1 mark) Question 3 (6 marks) Let X be a random variable taking on n values with probabilities p1, p2, . . . , pn. We will assume all proba- bilities are non-zero. Recall from Lecture 9 that the min-entropy of X, denoted E∞(X), is given by E∞(X) = min i log2 ( 1 pi ) = min { log2 ( 1 p1 ) , log2 ( 1 p2 ) , . . . , log2 ( 1 pn )} . We will drop the logarithm and simply work with the quantity: F∞(X) = min i 1 pi , by noting that whatever pi minimizes F∞(X), also minimizes E∞(X). Also, note that if X is uniformly distributed then p1 = p2 = · · · = pn = 1n . 3 (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 F∞(X) < n.="" (2="" marks)="" (c)="" argue="" that="" min-entropy="" is="" the="" highest="" if="" x="" is="" uniformly="" distributed.="" what="" is="" the="" min-entropy="" (e∞(x))="" in="" this="" case="" (2="" marks)="" question="" 4="" (2="" 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?(2="" marks)="" question="" 5="" (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="" (which="" maybe="" easier="" to="" implement).="" create="" an="" integer="" s="" containing="" all="" the="" digits="" in="" your="" student="" id.="" for="" example,="" if="" my="" student="" id="" is="" mq12345678,="" then="" s="12345678." let="" “str”="" denote="" the="" string="" function,="" i.e.,="" given="" any="" integer="" s,="" the="" function="" str(s)="" casts="" it="" into="" a="" string.="" for="" example,="" s="12345678" becomes="" str(s)="“12345678”." set="" the="" target="" t="" to:="" t="2256" 20="" let="" h="" be="" the="" sha-256="" hash="" function.="" let="" r="" be="" a="" counter="" starting="" from="" 0.="" finally,="" let="" “||”="" denote="" string="" concatenation.="" (a)="" implement="" a="" program="" that="" tries="" successive="" values="" of="" r,="" i.e.,="" r="0," 1,="" 2,="" 3,="" .="" .="" .,="" computes="" h(str(s)||str(r)),="" compares="" it="" with="" t="" and="" halts="" whenever="" h(str(s)||str(r))="">< t, with the output r. you need to provide the program and the output r. (5 marks) (b) let us call the program from part (a) as: puzzlefinder(s, t). write a program that calls puzzlefinder with successive inputs (s+ i, t), for i = 0 to 999, and records the output for each of these 1,000 runs. what is the average number of attempts 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? compare this number to the answer obtained in part (b). 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. 4 [nbf+16] arvind narayanan, joseph bonneau, edward felten, andrew miller, and steven goldfeder. bit- coin and cryptocurrency technologies: a comprehensive introduction. princeton university press, 2016. [sma16] nigel p smart. cryptography made simple, volume 481. springer, 2016. 5 t,="" with="" the="" output="" r.="" you="" need="" to="" provide="" the="" program="" and="" the="" output="" r.="" (5="" marks)="" (b)="" let="" us="" call="" the="" program="" from="" part="" (a)="" as:="" puzzlefinder(s,="" t).="" write="" a="" program="" that="" calls="" puzzlefinder="" with="" successive="" inputs="" (s+="" i,="" t),="" for="" i="0" to="" 999,="" and="" records="" the="" output="" for="" each="" of="" these="" 1,000="" runs.="" what="" is="" the="" average="" number="" of="" attempts="" 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?="" compare="" this="" number="" to="" the="" answer="" obtained="" in="" part="" (b).="" 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.="" 4="" [nbf+16]="" arvind="" narayanan,="" joseph="" bonneau,="" edward="" felten,="" andrew="" miller,="" and="" steven="" goldfeder.="" bit-="" coin="" and="" cryptocurrency="" technologies:="" a="" comprehensive="" introduction.="" princeton="" university="" press,="" 2016.="" [sma16]="" nigel="" p="" smart.="" cryptography="" made="" simple,="" volume="" 481.="" springer,="" 2016.="">