INsTRucTIoNs

This is an individual assignment. The aim of the assignment is that the student applies concepts and methods studied in weeks 2-10 to solve problems on discrete logarithms, ElGamal public-key system, the Diffie-Hellman key exchange, secret sharing, and public- key cryptography.

The assignment has a value of 138 points and is worth 20% of the unit marks.   It consists of five problems that are to be solved.

SuBMIssIoN

Students must submit the workings in the assignment in clear handwriting or typeset. The solutions should be clear enough so that a fellow student can understand all their steps; and they should demonstrate the student’s understanding of all procedures used to solve the problems. No marks will be awarded for answers without workings.

The assignment is due on Friday 23 September 2022 (Week 10) at 8pm.  The student should submit the assignment electronically through the CouldDeakin unit site by the due date and time.

Note 1: A student should attempt all problems he/she can solve.

Note 2: The student is solving the assignment by hand, and then (after that) he/she is verifying the answers of some questions with sagemath. Sagemath code should be provided only when the question asks the student to do so.

Note 3: Only three files must be submitted: one pdf file with the workings for questions 1-4, and one PowerPoint presentation and one .mp4 video for question 5. You will lose 5% of the marks if you submit a file or files that do not follow this instruction. It is your responsibility to ensure your files is not corrupted and can be read by a standard .pdf viewer or media viewer. Failure to comply will result in zero marks.

Note 4: Only one submission is allowed; that is, only one .pdf file, only one PPT presentation, and only one .mp4 video. Students should submit the assignment when they are sure of their answers.

REFERENcEs

(1) Learning materials of Weeks 2-10 of the SIT281 Unit site on CloudDeakin.

(2) Trappe and Washington, Introduction to cryptography with coding theory 3e.

(3) A. McAndrew, Introduction to Cryptography with open-source software.

PRoBLEMs

(1) This problem computes discrete logarithms.

(a) Describe a Baby Step, Giant Step attack to find x in 3z  = 57  (mod 137).     (b) (D grade question) In this exercise you will independently study the Pohlig-

Hellman algorithm  (Section of 10.2.1 of the textbook).  Apply the Pohlig- Hellman algorithm to find y in 3y  = 45  (mod 137).

(c) (HD grade question) Without using a Baby Step, Giant Step attack or the Pohlig-Hellman algorithm or brute force,  compute manually 33   =  95 (mod 137).

Note: In this whole question, you may use sagemath to compute the intermediate modular exponentiations that you will encounter.

10+18+6=34 marks

(2) This exercise is about the Diffie-Hellman exchange protocol. Alice and Bob agrees to use the public prime p =  1051 and the public primitive root α = 7. Alice also chooses a secret random number x = 113. And Bob chooses a secret random number y = 53.

(a) Describe what information Alice and Bob send each other.  Justify your an- swer.

(b) Determine the shared secret that each obtains.

(c) Suppose that Eve witnesses this entire exchange, the information that Alice sent to Bob, the information that Bob sent to Alice, and the public informa- tion of this exchange. That is, Eve has p = 1051, α = 7, αz   (mod 1051) = 7113 (mod 1051), and αy   (mod 1051) = 753   (mod 1051). Eve cannot compute dis- crete logarithms directly, but she is able to compute modular exponentiation with positive exponents only. Describe how she can obtain Alice’s and Bob’s shared secret,  namely αzy   (mod 1051);  this involves solving the necessary equations that Eve should solve.

Note: In this whole question, you may use sagemath to compute the intermediate modular exponentiations that you will encounter.

4+4+12=20 marks

(3) Alice and Bob has designed a public key cryptosystem based on the ElGamal. Bob has chosen the prime p = 113 and the primitive root α = 6. Bob’s private key is an integer b = 70 such that β = αb  = 18  (mod p). Bob publishes the triple (p, α, β).

(a) Alice chooses a secret number k = 30 to send the message 2022 to Bob. What pair or pairs does Bob receive?

(b) What should Bob do to decrypt the pair or pairs he received from Alice? During the computation, make sure Bob does not compute any inverses.

(c) Verify the answer of Parts (a) and (b) in sagemath.

(d) Before choosing k = 30, Alice was thinking of choosing k = 32. Do you think that Alice should have chosen k = 32? Give an answer and justify it.

10+7+(3+2)+3=25 marks

(4) This question is about secret sharing.

(a) You set up a (3, 37) Shamir threshold scheme, working modulo the prime 227. Three of the shares are (1, 4), (2, 8), and (3, 16). Another share is (5, x), but the part denoted by x is unreadable. Find the correct value of x, the relevant polynomial, and the message. Justify all your steps.

(b) In a  (4, 41) Shamir threshold scheme working modulo the prime 229, the shares (1, 9), (2, 27), (3, 81), and (4, 243) were given to Alice, Bob, Jerry, and Charles. Calculate the corresponding Lagrange interpolation polynomial p(x) modulo 229; that is, write p(x) = a0 + a1 x + a2 x2 + a3 x3  with a0 , a1 , a2 , a3  e Z229 . Also, identify the secret.

(c) Verify the solutions of Parts (a) and (b) in sagemath.

24+14+5=43 marks