Homework 8: Elliptic Curves & Elliptic Curve Cryptography

Purpose

This homework is designed to do several things:

• The proficiency problems may become part of your portfolio that demonstrates meeting the content objectives of the course.

• Doing challenge problems and submitting them (and their revised version(s)) demonstrates some of our overall objectives.

• Submitting your check in memo and homework problems are an opportunity to get feedback from Dr. Bolkema.

Instructions

Do as many of the proficiency problems as you feel necessary to meet the objectives. The challenge problems are optional but encouraged. Recall that you can submit up to three problems per week for direct feedback from Dr. Bolkema.

Content Objectives – Module 8

By doing this homework you will demonstrate that you are able to

1. use the addition law on real elliptic curves graphically or algebraically

2. compute points on elliptic curves over finite fields

3. discuss applications of elliptic curves in cryptographic systems

Proficiency Problems

1. (Obj. 1) Consider the real elliptic curve given by

y2 = x3 ? 2x + 4

and the points P = (0, 2) and Q = (?2, 0). (a) Verify that P and Q are on the given curve.

(b) Compute P + Q, showing all work and describing the process.

(c) Illustrate the addition P + Q graphically, either sketching by hand or using Desmos (or the graphing program of your preference).

(d) Compute P + P , showing all work and describing the process. (Note that your answer may not be integer-valued, and that is okay!)

2. (Obj. 1) Consider the real elliptic curve given by

y2 = x3 + 17

and the points P = (?1, 4) and Q = (2, 5). (a) Verify that P and Q are on the given curve.

(b) Compute P ?Q, showing all work and describing the process. (c) What happens when you try to compute P + Q? How do you interpret this result?

3. (Obj. 1) Show that (2, 4) and (4, 8) are both points on y2 = x3?4x+16, but that (2, 4)+(2, 4) 6= (4, 8).

4. (Obj. 2) Fill in the missing points in the addition table below for the elliptic curve y2 = x3 + x + 2 over F5 by computing (1, 3) + (1, 2), (1, 3) + (1, 3), and (4, 0) + (1, 2).

+ ? (1, 2) (1, 3) (4, 0)

? ? (1, 2) (1, 3) (4, 0)

(1, 2) (1, 2) (4, 0) ? (1, 3)

(1, 3) (1, 3) (1, 2)

(4, 0) (4, 0) (1, 2) ?

Show all work and explain your process.

5. (Obj. 2) Consider the elliptic curve y2 = x3 + 3x + 5 over F19. Show that P = (4, 9) is on the curve and compute 2P .

6. (Obj. 3) In your own words, compare elliptic curve Diffie-Hellman key exchange protocol and the classic Diffie-Hellman key exchange protocol. (Note that this will likely require some research!)

7. (Obj. 3) In your own words, compare and contrast elliptic curve Elgamal public key cryptosystem and the classic Elgamal public key cryptosystem. (Note that this will likely require some research!)

Challenge Problems

Recall you can submit as many drafts as you want of a challenge problem. Justify your answers with complete sentences explaining your reasoning.

8. Consider the elliptic curve y2 = x3 + x + 1 over F5, and let P = (4, 2) and Q = (0, 1) be points on this curve. Solve the elliptic curve discrete logarithm problem for P and Q; that is, find a positive integer n such that Q = nP .

9. Consider the real elliptic curve y2 = x3 + 1, and let P = (0, 1).

(a) Compute 2P .

(b) Compute 3P, 4P, 5P, 6P, 7P .

(c) Based on your calculations, give a formula for nP for any positive integer n.

10. Consider the elliptic curve y2 = x3 + 8 over Fp. (a) Find all points on the curve if p = 5.

(b) Find all points on the curve if p = 7.

(c) Find all points on the curve if p = 11.