p.p1 {margin: 0.

0px 0.0px 2.0px 0.0px; font: 14.0px ‘Helvetica Neue’; color: #454545}p.p2 {margin: 0.0px 0.0px 0.

0px 0.0px; font: 12.0px ‘Helvetica Neue’; color: #454545}p.

p3 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px ‘Helvetica Neue’; color: #454545; min-height: 14.

0px}span.s1 {font: 12.0px ‘Apple Symbols’}span.s2 {font: 12.

0px ‘Lucida Grande’}Elliptic Curve Basics An elliptic curve over a field K is a cubic curve has variables, f (X, Y ) = 0, creating the set of points (x, y) ? K satisfying the equation y2 = x3 + ax + b. These points, along with a single element O called the “point at infinity,” make up an elliptic curve. K will be either the field R (real numbers) or the finite field Fq of q = pr elements. The general formation of the elliptic curve is based ony2 +ay=x3 +bx2 +cxy+dx+e;a,b,c,d,e?K. Arithmetic of Elliptic Curves What makes elliptic curves so darned prominent with respect to cryptography is that the set of points on an elliptic curve form an abelian group. To show how elliptic curves satisfy the fundamental properties of groups, along with commutativity, we will explore the geometry of these curves. Elliptic Curves and Abelian Groups Let’s begin by letting E be an elliptic curve over R, with P, Q ? E. We can now define the arithmetic of these curves using a few rules.

6.3.1 Additive Identity IfthepointP isthe”pointatinfinity”O,then?P =0andP+Q=Q.

This makes O the additive identity (like 0) for the group of points on E. 17 6.3.2 Additive Inverse Figure 5: Elliptic Curves: Additive Inverse Assuming P ?= O (as we will for the remainder of these definitions), we define ?P , where P = (x, y) to be (x, ?y).

A quick look at the general formula for elliptic curves verifies that (x, ?y) ? E iff (x, y) ? E. 18 6.3.3 Addition of Points on E Figure 6: Elliptic Curves: Addition When P and Q have different x-coordinates, then there is a line l = P Q that intersects the curve at exactly one point R. If l is tangent to the curve at P or Q, then R = P or R = Q, respectively. P +Q is therefore defined to be ?R (Figure 6). 19 6.3.

4 Addition of Points, Case 2 If Q = ?P , then we define P + Q to be O, the “point at infinity.” 6.3.5 Addition of Points, Case 3 IfP =Q,thenlisthetangentlinetothecurveatP,andRistheonly other point of intersection of l with E, and we define P + Q = ?R. If P is a point of inflection, then P = R.

6.3.6 E Forms an Abelian Group The geometric argument is just one way to prove that the definitions we have just laid out for P + Q makes the points on E an abelian group. One could also use real analysis or an algebraic argument, as well. For further reading on the topic, along with the complete proofs.

Elliptic Curves over Finite Fields Now, let K be the finite field Fq, where q = pr, and E is an elliptic curve defined over K. As we have seen in earlier discussions, it is important to cryptographers that a group have a finite number of points. Finding these points therefore becomes an important task. E has at most 2q + 1 Fq points: 2q pairs of (x, y) along with O, the point at infinity. Counting points on elliptic curves is important to cryptographers using these curves, as it’s nice to know the structure of the abelian group; i.

e. is it cyclic. Hasse’s Theorem deals with the size of N, the number of Fq points on E, but is beyond the scope of this paper – don’t worry too much about it. Again, if you wish to explore the mathematics a bit further, 9 is an excellent source.

Elliptic Curve Cryptosystems We now have a multiplicative group of a finite field Fq, the finite abelian group F?q. As with our conventional public key cryptographic examples, we can use this abelian group to form a public key cryptosystem. 20 As you recall, the discrete log problem formed a nice one-way function for use in our cryptosystem. It would be nice if we could find an analogous problem using elliptic curves over finite fields.