Chapter 3 Cryptography 69
Cryptography Overview
elliptic curve parameters.
Coefficients Over a Field of Even Characteristic
An elliptic curve E over a field of even characteristic F
2
m is all the pairs of points (x,y)
that satisfy the equation:
y
2
+ xy = x
3
+ax
2
+b
In this equation, x and y are elements of F
2
m, and so are a and b. The whole equation is
evaluated over F
2
m. 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 F
2
m is different from the equation over F
p
. Over
F
2
m there is a quadratic term, ax
2
, 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, F
q
, 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, F
q
, and our elliptic curve E, determined by a and b, we can consider all
the pairs (x,y) in F
q
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 F
q
; this
