Information Technology Reference
In-Depth Information
Elliptic Curve Point Multiplication
Alexander Rostovtsev and Elena Makhovenko
Department of Information Security of Computer Systems
St. Petersburg State Polytechnic University
Polytechnitcheskaya st., 29, St. Petersburg, 195251, Russia
{rostovtsev,helen}@ssl.stu.neva.ru
Abstract.
A method for ell
ipti
c curve poin
t m
ultiplication is proposed with
complex multiplication by
instead of point doubling,
speeding up multiplication about 1.34 times. Complex multiplication is given
by isogeny of degree 2. Higher radix makes it possible to use one instead of two
point doublings and to sp
eed
up computation about 1.61 times. Algorithm, rep-
resenting exponent in − -adic notation for digital signature protocols, is
proposed. Key agre
eme
nt and public key encryption protocols can be imple-
mented directly in
−
2
or by
(
±
−
7
)
2
−
2
-adic notation.
1
Introduction
Elliptic curves over finite fields, proposed in [1], are widely used in cryptography,
because of their speed and exponential strength. A wide range of cryptographic
primitives (digital signatures, public-key encryption, key agreement, zero-knowledge
proofs, oblivious transfer, etc.) can be implemented with elliptic curves.
Elliptic curve
E
(
K
) over the field
K
of characteristic ≠ 2 is given by affine equati
on
y
2
=
f
(
x
), where cubic polynomial
f
(
x
) =
x
3
+
a
2
x
2
+
a
4
x
+
a
6
has no multiple roots in
K
(algebraic closure of
K
). Pairs (
x
,
y
), satisfying affine equation, and the point of infin-
ity
P
∞
, which cannot be represented as a solution of elliptic curve affine equation,
form the set of affine elliptic curve points. The whole set of elliptic curve points is
given
Y
2
Z
=
X
3
+
a
2
X
2
Z
+
a
4
XZ
2
+
a
6
Z
3
,
by
projective
equation
where
(
X
,
Y
,
Z
) = (
uX
,
uY
,
uZ
) for any
u
∈
K
*
and
P
∞
= (0, 1, 0).
Elliptic curve points form additive Abelian group with the point
P
∞
as the group
zero, (
x
,
y
) + (
x
, -
y
) =
P
∞
. Multiple point addition (
x
,
y
) + … + (
x
,
y
) =
n
(
x
,
y
) gives
point multiplication by an integer
n
. Let
K
=
F
q
be finite field of
q
=
p
n
elements. Then
group
E
(
F
q
) has fi
nit
e order #
E
(
F
q
). According to Hasse's theorem [2] it holds
q
−
F
. Group
E
(
F
q
) is either cyclic or a direct sum of two cyclic
groups [1]. In the latter case group order is not square-free. For elliptic curve
E
1
(
F
q
)
with #
E
1
(
F
q
) =
q
+ 1 +
T
there exists twisted curve
E
2
(
F
q
) with #
E
2
(
F
q
) =
q
+ 1 -
T
.
|#
E
(
)
q
−
1
|
≤
2
q
