SIT PROJECT

Instructions

This is an individual assignment. The aim of the assignment is that the student applies concepts and methods studied in weeks 2-11 to solve problems on secret sharing and applications of elliptic curves to cryptography.

The assignment has a value of 151 points and is worth 40% of the unit marks. It consists of four problems that are to be solved.

Submission

Students must submit the assignment in clear handwriting. 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 Sunday 10 October 2021 (Week 12) at 8pm. The student should submit the assignment electronically through the unit site by the due date and time.

Only three files must be submitted. A pdf file with all the written answers and workings, a PowerPoint presentation, and a video. You will lose 5% of the marks if you submit files that do not follow this instruction. It is your responsibility to ensure yours file are not corrupted and can be read by a standard .pdf viewer, PowerPoint, and video program, respectively. Failure to comply will result in zero marks.

References

• Learning materials of Weeks 2-11 of the SIT281 Unit site on.
• Trappe and Washington, Introduction to cryptography with coding theory
• McAndrew, Introduction to Cryptography with open-source software.

1

Problems

• This question is about secret
  • You set up a (3, 29) Shamir threshold scheme, working modulo the prime Three of the shares are (1, 4), (2, 5), and (3, 6). Another share is (4, 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.
  • In a (4, 31) Shamir threshold scheme, working mod the prime The shares (1, 8), (2, 16), (3, 32), and (4, 64) were given to Alice, Bob, Jerry, and Charles. Calculate the corresponding interpolation polynomial p(x) modulo 223; that

is, write p(x) = a₀ + a₁x + a₂x² + a₃x³ with a₀, a₁, a₂, a₃ ∈ Z₂₂₃. Also, identify

the secret.

• Verify the solutions of Parts (a) and (b) in

26+20+6=52 marks

• This question is about factoring with elliptic

  • Alice wants to factor n = 5959 using elliptic curves of the form y² = x³+ax+1. She sees that the point P = (0, 1) belongs to all such curves regardless of the value of a. For the particular value of a = 175, describe all the steps to apply the corresponding elliptic curve to factor n.

You could use sagemath only for the following intermediate com- putations: computations of inverses and modular arithmetic.

• In this exercise, you factor a reasonably large number

m = 10000000002200000000057

using an elliptic curve of form y² = x³ + ax + 1. Write sagemath code that, given m, returns the factors of m, the value of a that gives the elliptic curve, the point Q that you used, and the value k for the multiple kQ that enabled the factorisation. The sagemath code should show some level of exhaustive search. In addition, you should provide at most two lines of sagemath code that shows that kQ = ∞ for the curve with the a you give.

Note: This is a question for those aiming an HD grade. In this exercise, you may need some new python commands.

• Verify the answer of Part (a) in sagemath. (3 marks)

25+20+5=50 marks

• This exercise is about elliptic curve ElGamal Alice and Bob agrees to use the public prime p = 3863 and the elliptic curve E = y² = x³ + 324x + 1287 (mod 3863).

In this exercise, you could use sagemath only for the following inter- mediate computations: computations of multiples of points on a curve, sums of points on a curve, and computations of square roots.

• Alice needs help choosing her public key (p, P, Q, E) and private key k ∈ [2, p − 2], where P is a point on E and Q = kP (mod p). Choose P and k, and compute Q. Justify your
• Bob has downloaded Alice’s public Determine what Bob should do to send the message Pm = (410, 868) to Alice. Justify all the steps.
• Describe what Alice should do to decrypt the pair she receives from Bob. Justify all your
• Eve has had access to Alice’s public key (p, P, Q, E), and she claims that she can write sagemath code to find Alice private Write a sagemath code that, giving Alice’s public key, returns Alice’s private k.

4+9+5+6=24 marks

• In this problem, you will study independently a new public-key cryptosystem based on a hard mathematical problem. We have seen three such public-key cryptosys- tems, including one based on the difficulty of factoring large integers (RSA) and one base on the difficulty of computing discrete algorithms (ElGamal). It is impor- tant to have cryptosystems based on several hard mathematical problems, because a breakthrough in solving one mathematical problem would not compromise the security of all

A public-key cryptosystem consists of three parts or algorithms.

Key creation: This algorithm produces the public and private keys for Alice and Bob.

Encryption: Given Alice’s public key, Bob uses this algorithm to send a mes- sage m to Alice.

Decryption: Alice uses this algorithm to decrypt the data that Bob sends and obtain the message or an error.

Describe a new public-key cryptosystem based on a hard mathematical problem, for instance, a cryptosystem based on knapsack problems (Ch 6 of Introduction to Cryptography with open-source software by A. McAndrew) or a cryptosystem based on based on lattice problems (Ch 23 of the textbook). You could also come up with others or your own cryptosystem!

• In this description, you should concisely describe each of the algorithms defin- ing the system (key creation, encryption, and decryption). Then you should give an example showing all the The example should be different from the ones in the books described in the references; no marks will be given for the examples of the textbook.

To this end, you will create a PowerPoint presentation with at most five pages, no title page is needed but you should write your name, unit, trimester, and year on the first slide.

• You will also provide a video of at most 5 minutes describing the PowerPoint presentation, where at least once we are able to see
• An additional slide can be provided if you provide in it sagemath code to describe the three algorithms of the systems, but only in this

10+10+5=25 marks