Cryptography Overview
70 RSA BSAFE Crypto-C Developer’s Guide
is written E(F
q
).
The Order of an Elliptic Curve
The addition system that makes the points on the elliptic curve into what is called a
group has a number of properties. First, there can only be a finite number of points on
the curve. If every possible pair (x,y) were on the curve, there would be only p
2
or
(2
m
)
2
= 2
2m
possibilities of pairs. The total number of points, including the point Ο, is
called the order of the elliptic curve. The order is written as #E(F
q
).
The special point Ο plays the role of the additive identity, zero, in the group of the
elliptic curve.
The Order of a Point
Given any point on the curve, P, the addition rule lets you add that point to itself.
Then you can add your new point to the old point, and so on. When you add a point
to itself a number of times, it is called scalar multiplication. Although this is not
multiplication in the usual sense — it is an iteration of point addition k times — it still
has the usual math properties like commutativity and associativity over addition.
Adding a point P to itself k times gives another point denoted kP.
No matter what P is, there is always some n such that nP = Ο. The smallest n that
works for a given P is called the order of P. Not only does n exist, but it is always true
that n evenly divides the order of the elliptic curve, #E(F
q
).
The order n of P is important because it means that when we use P as the starting
point of our calculations, we can apply the rules of arithmetic modulo n. That is, we
have the following important fact:
r = r’ mod n if and only if rP = r’P
A Point of Prime Order
Now that we have those concepts, we can go on to the next parameter. Given our
elliptic curve, E, defined over our finite field, F
q
, we want to fix a special point that
will be used to mask the private key in a public/private key pair. The properties of P
are important to the security of our system. Not just any point will do: we need a
point P whose order n is prime; the larger the prime, the more secure the
cryptosystem.
Remember, P is of the form P =(x,y) where x and y satisfy the elliptic curve equation.
To show that x and y are specific to P, we usually write them as x
P
and y
P
. Therefore,
the special point P gives us two parameters:
• A point P = (x
P
,y
P
) of prime order
