# Cryptography Homework 8: Elliptic Curves & Elliptic Curve Cryptography

Purpose

This homework is designed to do several things:

• The proficiency proble

Cryptography 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.

(Feel free to verify your answers using the online calculator we saw in class, but show all work to justify

your answers.)