Cryptography Reference
In-Depth Information
p that solve
equivalence (3.7). We can graphically interpret ( x, y ) as a point in the ( x, y )-plane
( x representing the horizontal axis and y representing the vertical axis). Such an
( x, y ) is representing a point on the respective elliptic curve E (
The resulting set E (
Z p ) consists of all ( x, y )
Z p × Z p =
Z
Z p ). In addition to the
points on the curve, one usually considers a point at infinity (typically denoted by
O
).
If we use E (
Z p ) to refer to an elliptic curve defined over
Z p , then we automatically
mean to include
.
Let p =23and consider the elliptic curve y 2
O
Z 23 .
In the notation of equivalence (3.7), a and b are both set to 1. It can easily be verified
that 4 a 3 +27 b 2
x 3 + x +1defined over
0(mod p ), and hence the curve E (
Z 23 ) indeed represents an
elliptic curve. The points in E (
Z 23 ) are
O
and the following:
(0 , 1)
(0 , 22)
(1 , 7)
(1 , 16)
(3 , 10)
(3 , 13)
(4 , 0)
(5 , 4)
(5 , 19)
(6 , 4)
(6 , 19)
(7 , 11)
(7 , 12)
(9 , 7)
(9 , 16)
(11 , 3)
(11 , 20)
(12 , 4)
(12 , 19)
(13 , 7)
(13 , 16)
(17 , 3)
(17 , 20)
(18 , 3)
(18 , 20)
(19 , 5)
(19 , 18)
In order to make use of an elliptic curve, we must define an associative
operation. In ECC, this operation is called addition (mainly for historical reasons),
meaning that two points on an elliptic curve are said to be added. 29 In the literature,
the addition rule is usually explained geometrically. In this topic, however, we use a
sequence of algebraic formulae to describe the addition of two points:
1. P +
O
O
+ P = P for all P
E (
Z q ).
=
2. If P =( x, y )
E (
Z q ),then( x, y )+( x,
y )=
O
. The point ( x,
y ) is
sometimes also denoted as
P and called the negative of P . Note that
P is
indeed a point on the elliptic curve (e.g., (3 , 10) + (3 , 13) =
O
).
3. Let P =( x 1 ,y 1 )
E (
Z q ) and Q =( x 2 ,y 2 )
E (
Z q ) with P
=
Q ,then
P + Q =( x 3 ,y 3 ) where
λ 2
x 3
=
x 1
x 2
y 3
=
λ ( x 1
x 3 )
y 1
and
λ =
y 2 −y 1
x 2 −x 1
i fP
= Q
3 x 1 + a
2 y 1
i fP = Q
By contrast, the group operation in Z p is multiplication. The differences in the resulting additive
notation and multiplicative notation can sometimes be confusing.
29
Search WWH ::




Custom Search