The University of Melbourne School of Computing and Information Systems COMP90043 Cryptography and Security Assignment 2, Semester 2 2024 Due Date: Friday October 11, 23:59 AEST Objectives To improve your understanding of RSA, hash functions and ElGamal. To develop problem-solving and design skills. To improve written communication skills. Questions 1. [10 marks] A manager selects two large primes, p and q, where p ̸= q, to set up a secure communication channel between three employees, Alice, Bob, and Carlo, using RSA encryption. He first computes n = pq and corresponding ϕ(n). Then, he uses this < p, q > pair to generate three RSA key pairs (with different e being relatively prime to each other and corresponding d), assigns them to the staff individually, and destroys p, q, ϕ(n) immediately afterwards (meaning nobody knows the values). The following lists the key pairs: Alice: < n, eA >, < n, dA > Bob: < n, eB >, < n, dB > Carlo: < n, eC >, < n, dC > Answer the following questions with detailed justification. (a) [5 marks] Alice wants to send a message M to both Bob and Carlo, so she cal- culates CB = M eB mod n and CC = M eC mod n. Explain how an adversary can recover the message M without knowing private keys dB and dC . (b) [5 marks] Carlo is interested in messages sent to Alice. Outline a strategy that may help Carlo recover an alternative private key d′A that can perform the same function as dA to decrypt messages sent to Alice. 2. [30 marks] Hash Functions. (a) [15 marks] Consider the following hash function based on RSA function. The key < n, e > is known to the public. A message M is represented by blocks of predefined fixed size {M1,M2,M3, ...,Mm} such that 0 ≤ Mi < n. We can assume that n is large enough to hold the RSA assumptions. The hash value is calculated by: 1 H(M) = ((M1 ⊕M2 ⊕ ...⊕Mm)e) mod n Does this hash function satisfy each of the following requirements? Justify your answers. You can give examples, if necessary, to support your arguments. i. [3 marks] Fixed output size ii. [3 marks] Efficiency (easy to calculate) iii. [3 marks] Preimage resistant iv. [3 marks] Second preimage resistant v. [3 marks] Collision resistant (b) [15 marks] Explain how to efficiently find collisions in the following hash functions: i. [5 marks] The function Ha : {0, 1}512 → {0, 1}256 is defined as follows: Ha(x, y) = F (y, x⊕ y)⊕ y. Let the pair F, F−1 be a public secure symmetric key block cipher with block size and key length 256. That is, y is interpreted as the ‘symmetric key’, and x⊕ y is the ‘plaintext’ for F . To compute Ha, we first XOR y with x, then apply the block cipher to the result, and finally XOR the block cipher output with y one more time to get the final output. ii. [5 marks] Hb = F (y ⊕ x, x), where F, F−1 is as in last question (i). x ⊕ y is the ‘key’ and y is the ‘plaintext’. iii. [5 marks] Hc : {0, 1}257 → {0, 1}256 is defined as follows: Let H : {0, 1}∗ → {0, 1}256 be a collision-resistant hash function for arbitrary-length messages, then for x||b ∈ {0, 1}257, Hc(x, b) = H(x) if b = 0 and Hc(x, b) = H(H(x)) if b = 1. Here, a||b refers to concatenating a and b together as a single string. 3. [20 marks] ElGamal. (a) [10 marks] ElGamal Encryption A variant of ElGamal crypto system over the prime field GF (q) is given as follows. Assume the parameters are as discussed in the lectures. Let yA = a xA mod q, be the public address of Alice, where xA, 1 < xA < q − 1, is Alice’s private key. Encryption function is defined as follows: E(M) = [C1, C2], where C1 = a k mod q, where k is a random integer 1 ≤ k ≤ q − 1, C2 = K ⊕M , where K = ykA mod q and ⊕ is binary XOR applied to binary representation of K and M . i. [5 marks] Describe the Decryption Function D(C1, C2) that Alice can use to recover the message. ii. [5 marks] Show how the security of the encryption function is based on Com- putational Diffie-Hellman (CDH) problem. CDH Problem: Let q be a prime number and a be a generator of the mul- tiplicative cyclic group of modulo q. Given ax, ay, the CDH problem is to compute axy. 2 (b) [10 marks] ElGamal signature. Let’s consider a variant of ElGamal signature over the prime field GF (q). Let H be a public hash function and let yA = a xA mod q be the public key of Alice, where xA, 1 < xA < q − 1 is the private key and a is a primitive element in the field. Alice uses the following equation to define a related ElGamal signature scheme by using: m S2 + xAS1 = k mod (q − 1), where m = H(M), M an arbitrary message, k a random number, S1 = a k mod q and S2 are signature parameters. The signature for a message M is represented as [M,S1, S2]. i. [5 marks] What are the signing and verification equations? ii. [5 marks] Is this shceme secure? Justify your answer with reasons. 4. [15 marks] We studied the Needham–Schroeder protocol in lectures. An alternative key distribution method suggested by a network vendor is illustrated in the figure below. Figure 1: Key Distribution Between A and B. (a) [5 marks] How do A and B know that the key is freshly generated? (b) [5 marks] How could A and B know that the key is not available to other users in the system? (c) [5 marks] At this stage, A and B cannot authenticate with each other. Explain why and extend the scheme with a few steps so that A and B can authenticate with each other. Your modifications should be based on symmetric key methods used in this key distribution protocol, not public key primitives. 5. [NO marks] Additional Question: ******************* 3 Following questions are NOT counted to your marks of this assignment. However, we strongly encourage you to have a try. ******************* (a) Use two primes: 10921304574392093059217153525481121125933934477429 and 89855181341172893110 764453512406142438324081807631 to construct an RSA key. Determine the small- est valid RSA public exponent and its corresponding private key. Show the detailed workings with an explanation justifying your answer. You need to attach any code you implemented in the appendix (do NOT use screenshots for code) or mention the tools you used. (b) Consider the following version of a classical cipher where plaintext and ciphertext elements are from Z31. The encryption function, which maps any plaintext p to a ciphertext c, is given by c = Ea(p) ≡ a× p2(mod 31), where a from the Z31. i. Generally, finding a square root (known as quadratic residue) in module arithmetic is difficult. In fact, for a b, deciding if there is an x such that x2 ≡ b mod n is hard. Determine the decryption function for c. HINT: As a starting point, you may try to solve c={YOUR STUDENT NUM}mod 29, a={YOUR STUDENT NUM}2 mod 29. ii. However, if the module is a special prime, we have a general formula for getting the root. Derive the decryption function for this scheme. Show your work. (0 mark for solutions like √ x mod 31) iii. Should this cipher be considered as mono-alphabetic cipher or poly-alphabetic cipher? Why? iv. Assume there is a helper that can output the corresponding ciphertext for an arbitrary plaintext you supply. Describe an efficient way to retrieve the key using this helper. You may have noticed that there are two potential plaintexts regarding one ciphertext. Find a simple way to slightly tweak the encryption scheme so that the receiver can confirm which root is the correct plaintext. (c) A commitment scheme is a digital analog of a “sealed envelope.” Specifically, a sender can commit to a message m and send the resulting commitment c to a receiver (i.e., seal the message in an envelope). The commitment c should not reveal anything about the committed value m. Later on, the sender can open up the commitment and convince the receiver that c is indeed a commitment to the message m (i.e., open up the envelope and recover the original message). The commitment scheme is hiding if c hides the message m and is binding if the sender cannot open the commitment c to any message m′ ̸= m. In this problem, we will construct a commitment scheme from the discrete log assumption: 4 • Public parameters: Let G be a group of the prime order p and let g, h ∈ G be arbitrary elements of G, and are not identity element. Identity element: an element that leaves unchanged every element when the operation is applied. • Commitment: To commit to a message m ∈ Zp, sample r ← Zp and output the commitment c← gmhr. • Open: To open the commitment c to the message m, the sender gives (m, r) to the receiver and the receiver checks that c = gmhr. i. Show that the above commitment scheme is perfectly hiding (i.e., the com- mitment c does not leak any information about the committed message m). Namely, show that given the commitment c ∈ G, every candidate message m′ ∈ Zp is equally likely (over the randomness of r). One way is to show for every m′ ∈ Zp, there is a unique r′ ∈ Zp such that c = gm′hr′ . ii. Show that the above commitment scheme is computationally binding assum- ing hardness of discrete log in G. Namely, show that if an efficient adversary can output a commitment c together with openings (m, r) and (m′, r′) such that gmhr = c = gm ′ hr ′ and m ̸= m′, then it means the adversary can know the value of a given h = ga. Remember to give a brief explanation why any inverses you take actually exist. Hint: Assume h = ga 5 Submission and Evaluation • You must submit a PDF document via the COMP90043 Assignment 2 submission entry on the LMS by the due date. Handwritten, scanned images, and/or Microsoft Word submissions are not acceptable — if you use Word, create a PDF version for submission. • Late submission will be possible, but a late submission will attract a penalty of 10% available marks per day (or part thereof). Requests for extensions on medical grounds will need to be supported by a medical certificate. Any request received less than 48 hours before the assessment date (or after the date) will generally not be accepted except in the most extreme circumstances. • This assignment will be marked out of 75 marks, and will contribute to 7.5% of your total marks in this subject. Marks are primarily allocated for the correctness of your thinking and clarity of your communication, rather than (only) the correct result without sufficient justification. • We expect your work to be neat — parts of your submission that are difficult to read or decipher will be deemed incorrect. Make sure that you have enough time towards the end of the assignment to present your solutions carefully. The time you put in early will 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 work. For many students, discussions with friends will form a natural part of the undertaking of the assignment work. However, it is still an individual task. You are welcome to discuss strategies to answer the questions, but not to share the work (even draft solutions) on social media or discussion boards. It is University policy that cheating by students in any form is not permitted, and that work submitted for assessment purposes must be the independent work of the student concerned. Please see https://academicintegrity.unimelb.edu.au If you have any questions, you are welcome to post them on the Ed discussion board so long as you do not reveal details about your own solutions. We encourage you to make your questions public, so that Your classmates may also benefit from the discussion should they have a similar concern. 6 51作业君版权所有