RSA Security 5.2.2 manual Order of an Elliptic Curve, Order of a Point, Point of Prime Order

Cryptography Overview

is written E(Fq).

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 p2 or (2m)2 = 22m 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(Fq).

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(Fq).

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, Fq, 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 xP and yP. Therefore, the special point P gives us two parameters:

•A point P = (xP,yP) of prime order

7 0 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e