Public key cryptography, also known as asymmetric cryptography is widely used now days in distributed environments. From key distribution to secure communication and message signing, public key cryptography is everywhere. However, public key algorithms generally are power hungry and clearly not suitable for wireless sensors. Over the last few years Elliptic curve cryptography (ECC) has emerged as an attractive and viable public key system for constrained environments. An elliptic curve E can be defined as points on the equation of the form y2 =x3+ax +b, along with a point at infinity. Here a and b are real numbers and 4a3 + 27b2 ≠ 0(mod p), p is a prime number greater than 3. This condition makes the curve defined by the above equation to be non singular. The graph of a non singular curve has two components if the discriminant is positive and one if the discriminant is negative. An example of the elliptic curve used in practice is shown below
y2 = x3 + 317689081251325503476317476413827693272746955927x
+ 79052896607878758718120572025718535432100651934
This elliptic curve is used in the Microsoft Windows Media Digital Rights Management Version 2.
The points on an elliptic curve form an abelian group. An abelian group exhibits the following characteristics. We'll see how each of these properties is satisfied by an elliptic curve.
(1) has a group operator
(2) has an identity element with respect to the operator
(3) exhibits closure and associativity with respect to the operator
(4) exhibits commutative property
(4) the existence of inverses with respect to the operator.
GROUP OPERATOR
The group operator defined on the points on an elliptic curve is known as addition. Geometrically the addition of two points on the curve takes place as follows.
Let there be two points P and Q on the elliptic curve, to add these points a straight line is drawn which passes through the two points. This straight line may or may not intersect the curve at a third point. If it does, then a mirror image of this point is taken on the x axis and this point R is called the sum of P and Q. If the line does not intersect the curve at a third point, we say the sum is the point at infinity.
Algebraically
If we have two points P(xP,yP) and Q(xQ,yQ), then the point R(xR,yR)=P+Q is given by
s = (yP - yQ) / (xP - xQ)
xR = s2 - xP - xQ and yR = -yP + s(xP - xR)
xR = s2 - xP - xQ and yR = -yP + s(xP - xR)
Point doubling is done as below
2P = R where
s = (3xP2 + a) / (2yP )
xR = s2 - 2xP and yR = -yP + s(xP - xR)
s = (3xP2 + a) / (2yP )
xR = s2 - 2xP and yR = -yP + s(xP - xR)
The point at infinity acts as the identity element of the group, therefore, P + O = P.
INVERSE
The additive inverse of a point is its mirror image across the x axis. Let’s assume we have a point P and its inverse -P which is its mirror image across the s axis. A straight line passing through these two points will be parallel to the y axis and thus will never intersect the curve at any other point. Which implies that P + (-P) = O. So we have a valid inverse operation.
CLOSURE
We can see from the above discussion that the addition operation will only produce points which are on the elliptic curve, which satisfies the closure property.
COMMUTATIVE PROPERTY
Geometrically it’s easy to see that two points P and Q will define the same straight line, irrespective of the order. This implies that irrespective of the order the straight line will intersect the curve at the same point and thus produce the same result for P+Q and Q+P.
ASSOCIATIVITY
The proof for associativity is a tedious one which I am skipping here because it’s not relevant to the matter at hand. It should suffice here to say that the group defined by, the points on the elliptic curve obeys the associativity rule.
REFERENCES
