Visualizing complex points of elliptic curves

Elliptic Curve Cryptosystems

by: burt rosenberg
at: university of miami
date: nov 2021

Overview

Refer to the class text on elliptic curves.

An elliptic curve are those points satisfying the equation, 

    y2 = x3 + A x + B  (mod p)
The points P = (x,y) that satisfy this equation form a group, where the operation is denoted by addition(+). For points P1 and P2, there is a point P1+P2, as well as a unique point O such that P + O = P, for all points P and for every point P there is a unique point Q such that P+Q=0.

Multiplication of a point by an integer is defined as n P = P + P + ... + P, with n repetitions of P. This can be extended obviously to (-n) P = - (n P), and 0 P = O. Given an elliptic curve E and a point on the curve P, the map n &mapstoright; n P is efficiently calculated, but the inverse map is hard. This is the discrete log problem for elliptic curves, and forms the basis of elliptic curve cryptosystems.

El Gamel Elliptic Curve Cryptosystem

Let E be the points on an elliptic curve E(x,y), and P a point of high order in E. Let s be the secret key and s P the public key. Encrypt message m as 
E[sP](m) = (kP, ksP + m),

D[s](kP,ksP+m) = ksP + m - s(kP) = m
The point P is chosen so the order of P in E prime.

The project

The project template indicates the algorithms to complete. They include,

Note that we will need to take square roots in the field mod p. For this reason our project will consider only primes that are 3 mod 4 (i.e. 7 or 11). For these primes there is an easy formula for the square root, 
   √ x = x(x+1)/4 (mod p)
If x has a square root then this calculates it. If x does not have a square root I leave it to you to figure out what it is calculating, and why it is not the square root.

I suggest that your code represent points on the curve with three numbers, (x,y,z). For the points (x,y) that fit the curve equation, store this point as the triple (x,y,1). Store that zero point as (0,1,0), which otherwise is not a point on the curve. However, it is a point on this version of the curve, 

    y2 z = x3 + A x z2 + B z3 (mod p)
where every term is of degree 3. In these coordinates, we do not permit the point (0,0,0) and we identify as the same point any two points for which, 
 λ (x, y, z) =  (λ x, λ y, λ z) = (x', y', z')
hence we can assume that z is either zero or one.

To be continued...

Copy the files from class/proj5/ to your [username]/proj5 folder. Complete the code as necessary so that you run all tests successfully. Perform additional testing and solve the challenge problems.

In the follow-on project 6, we will explore algorithms for discrete logs.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 14 nov 2021
update: 16 nov 2021