Cryptography Reference
In-Depth Information
9.2.3 Elliptic Curve Scalar Multiplication
Scalar multiplication, the operation of repetitively adding a point to itself on an elliptic
curve, is the most important primitive in ECC and its execution time dominates the
time required to perform ECC operations. This operation is analogous in many ways
to the modular exponentiation operation employed in RSA and similar systems.
A naive way to perform a scalar multiplication is repeated addition, which requires
a number of group operations proportional to the group size. A much better solution
is the double-and-add algorithm, analogous to the square-and-multiply algorithm for
modular exponentiation. Algorithm 9.1 illustrates a basic variant of the double-and-
add method. This approach requires a number of group operations proportional to
the logarithm of the group size.
Algorithm 9.1:
Double-and-add scalar multiplication
Input
:
P
∈
E
(
K
)
,
k
=
(
k
n
−
1
,
k
n
−
2
,...,
k
0
)
Output
:
kP
1
Q
←
O
2
for
i
←
n
−
1
downto
0
do
Q
←
2
Q
3
if
k
i
=
1
then
4
Q
←
Q
+
P
5
6
end
7
end
8
return
Q
It can be seen from Algorithm 9.1 that a doubling operation is required in every
iteration, while an addition operation is required only when the corresponding bit of
the scalar
k
is 1, which is true in half of the iterations on average. It is possible to
reduce the cost of the scalar multiplication by reducing the number of point additions,
which can be achieved by recoding the scalar
k
. For example, the nonadjacent form
(NAF) representation, with the property that no two nonzero digits are adjacent, can
be used to reduce the number of 1s in the scalar. The simplest instance is the 2-NAF,
which uses the digits 0, 1, and
1 and ensures that no two consecutive digits are
nonzero. The use of the 2-NAF representation reduces the number of additions from
n
−
3 on average [297].
Double-and-add-always variant
It can be easily seen that the iterations of Algorithm 9.1 take different times for
different values of
k
i
, which can be exploited by simple power or timing analysis
attacks to determine the secret scalar
k
. To solve this problem, the computations
performed should not depend on the secret data and branching should be avoided.
This results in regular iterations as illustrated in Algorithm 9.2, presented in [102].
More recently, other regular scalar multiplication algorithms have been introduced,
e.g., in [195].
/
2to
n
/
