The University of MelbourneSchool of Computing and Information SystemsCOMP90043 Cryptography and SecurityAssignment 2, Semester 2 2019Due Date: October 8, 23:59ObjectivesTo improve your understanding of RSA, hash functions, MAC and key distribution.To develop problem-solving and design skills. To improve written communication skills.Questions1. [18 marks] Professor Parampalli selected two large prime numbers p and q. He decidedto generate three pairs of RSA keys (with different e being relatively prime to eachother, and corresponding d) for his tutors, using the same p and q. He destroyed bothp and q immediately after generating the following keys:Ge: < n, eG >, < n, dG >Jiajia: < n, eJ >, < n, dJ >Zhuohan: < n, eZ >, < n, dZ >Answer the following questions with detailed justification.(a) Zhuohan wants to send a message M to both Ge and Jiajia, so he calculatesCG =MeG mod n and CJ =M eJ mod n. Explain how Lianglu could recover themessage without knowing Ge’s or Jiajia’s private key.(b) Suppose Lianglu has access to private key for Ge. However, he is only interested indecrypting messages sent to Zhuohan. Outline a strategy that may help Lianglurecover Zhuohan’s private key.2. [17 marks] Consider the following 3-person encryption scheme based on RSA. Lianglu(can be trusted in this case) generates two large primes p and q, calculates both nand φ(n). He also chooses k1, k2 and k3 such that GCD(ki, n) = 1 and k1k2k3 ≡1 mod φ(n). Keys are securely distributed to three other tutors as follows:Ge: < n, k1, k2 >Jiajia: < n, k2, k3 >Zhuohan: < n, k3, k1 >Answer the following questions.1(a) Ge has a message M1 for Jiajia. Give the encryption function for Ge as well asthe decryption function for Jiajia, so that the message won’t be seen by anyoneelse.(b) Jiajia has a message M2 for both Ge and Zhuohan. Give the encryption functionfor Jiajia, as well as decryption functions for both Ge and Zhuohan, so that themessage won’t be seen by any other person.3. [14 marks] An alternative key distribution method suggested by a network vendor isillustrated in the figure below.Key DistributionCenter (KDC) Initiator AResponder B(1) IDa || (2) IDa || E(Ka, Na)|| IDb || E(Kb, Nb) (3) E(Kb, [Ks || IDa || Nb])|| E(Ka, [Ks || IDb || Na])(4) E(Ka, [Ks || IDb || Na])E(Ka, Na)(a) Describe the scheme in steps.(b) Estimate the key storage requirements of both the KDC and users. You mayneed to make some appropriate assumptions.(c) Does this scheme ensure the authenticity of both A and B? Justify your answer.(d) Could a replay attack be detected in this scheme? If yes, explain which step(s)could it be identified and how. If no, show how an attacker could perform theattack.4. [12 marks] The Diffie-Hellman (DH) key agreement protocol is vulnerable to a man-in-the-middle attack. Is it possible to secure the key agreement protocol against thisattack by using each of the following primitives? If yes, sketch the method. If no,give reasons.(a) Public Key Digital Signatures(b) Hash functions(c) Message Authentication Codes (with a prior agreed key)25. [14 marks] Consider the following hash function based on RSA. The key < n, e > isknown to the public. A message M is represented by blocks of predefined fixed sizeM1,M2,M3, …,Mm such that Mi < n. The hash is constructed as: encrypt the firstblock, XOR the result with the second block and encrypt again, etc. For example, thehash value of a message consisting of two blocks is calculated byH(M) = H(M1,M2) = ((Me1 mod n) XOR M2)e mod nDoes this hash function satisfy each of the following requirements? Justify your an-swers (with examples if necessary).(a) Variable input size(b) Fixed output size(c) Efficiency (easy to calculate)(d) Preimage resistant(e) Second preimage resistant(f) Collision resistant3Submission and Evaluation• You must submit a PDF document via the COMP90043 Assignment 2 Turnitin sub-mission form on LMS by the due date. Handwritten, scanned images, and/or MicrosoftWord submissions are not acceptable — if you use Word, create a PDF version forsubmission.• Late submission will be possible, but a late submission will attract a penalty of 10%per day (or part thereof).• This assignment contributes 7.5% of the total marks in this subject. Marks are pri-marily allocated for correctness, but how clearly you communicate your thinking willalso be taken into account.• We expect your work to be neat — parts of your submission that are difficult to reador decipher will be deemed incorrect. Make sure that you have enough time towardsthe end of the assignment to present your solutions carefully. Time you put in earlywill 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 own individualwork. For many students, discussions with friends will form a natural part of theundertaking of the assignment work. However, it is still an individual task. Youare welcome to discuss strategies to answer the questions, but not to share the work(even draft solutions) on social media or discussion board. It is University policythat cheating by students in any form is not permitted, and that work submitted forassessment purposes must be the independent work of the student concerned.Please see https://academicintegrity.unimelb.edu.auIf you have any questions, you are welcome to post them on the LMS discussion boardso long as you do not reveal details about your own solutions. You can also email the HeadTutor, Lianglu Pan ([email protected]) or the Lecturer, Udaya Parampalli([email protected]). In your message, make sure you include COMP90043 in thesubject header. In the body of your message, include a precise description of the problem.4
