RSA Security 5.2.2 manual Point P and its Order, Coefficients Over a Field of Even Characteristic

Cryptography Overview

elliptic curve parameters.

Coefficients Over a Field of Even Characteristic

An elliptic curve E over a field of even characteristic F2m is all the pairs of points (x,y) that satisfy the equation:

y2 + xy = x3 + ax2 +b

In this equation, x and y are elements of F2m, and so are a and b. The whole equation is evaluated over F2m. For computational reasons, there is also a “point at infinity”, Ο, that is included as well.

The numbers a and b are called the coefficients of the elliptic curve; they are part of the elliptic curve parameters.

Note: Note that the equation over F2m is different from the equation over Fp. Over F2m there is a quadratic term, ax2, instead of the linear term ax in the odd prime case, as well as a new cross-term, xy. The differences in the equation arise because of the differences in arithmetic between the two types of fields.

The Point P and its Order

Obviously, you can’t create a cryptosystem out of just any equation. The elliptic curve equation is important because it has special properties. One of these properties is that it is possible to set up an addition system that lets you add one point on the elliptic curve to another. The addition is complex and non-obvious, but it is possible to set up a system of equations that determine the sum of two points. Adding two points on an elliptic curve involves several operations in the underlying field, Fq, including multiplications, additions, and the computation of inverses. The complexity of the addition is what makes elliptic curve cryptosystems work — if you add a point P to itself k times to get kP, there is no known fast way to get k.

To implement an elliptic curve cryptosystem, we need to specify a point P on our curve that has some special properties. To understand these properties, we need some more concepts: the points on a curve, the order of a curve, and the order of a point on the curve.

The Points of an Elliptic Curve

For our field, Fq, and our elliptic curve E, determined by a and b, we can consider all the pairs (x,y) in Fq that satisfy the elliptic curve equation. Each such pair is called a point of the elliptic curve. The collection of all the points that satisfy the equation, along with the special point Ο mentioned earlier, is called the points of E over Fq; this

C h a p t e r 3 C r y p t o g r a p h y 6 9