Cryptography Reference
In-Depth Information
13
P
=
P
+
P
+
...
+
P
where
P
=(5
,
1). In this case, we can simply use the table that was compiled earlier:
13
P
=(16
,
4)
.
Point multiplication is analog to exponentiation in multiplicative groups. In or-
der to do it efficiently, we can directly adopt the square-and-multiply algorithm.
The only difference is that squaring becomes doubling and multiplication becomes
addition of
P
. Here is the algorithm:
Double-and-Add Algorithm for Point Multiplication
Input
: elliptic curve
E
together with an elliptic curve point
P
a scalar
d
=
i
=0
d
i
2
i
with
d
i
∈
0
,
1 and
d
t
= 1
∑
Output
:
T
=
dP
Initialization
:
T
=
P
Algorithm
:
1
R
i
=
t
−
1DOWNTO0
1.1
T
=
T
+
T
mod
n
IF
d
i
= 1
1.2
T
=
T
+
P
mod
n
2
RETURN (
T
)
For a random scalar of length of
t
+ 1 bit, the algorithm requires on average
1
.
5
t
point doubles and additions. Verbally expressed, the algorithm scans the bit
representation of the scalar
d
from left to right. It performs a doubling in every
iteration, and only if the current bit has the value 1 does it perform an addition of
P
.
Let's look at an example.
Example 9.7.
We consider the scalar multiplication 26
P
, which has the following
binary representation:
26
P
=(11010
2
)
P
=(
d
4
d
3
d
2
d
1
d
0
)
2
P
.
The algorithm scans the scalar bits starting on the left with
d
4
and ending with the
rightmost bit
d
0
.