Information Technology Reference
In-Depth Information
number of doublings can be performed instead of even number of complex multipli-
cations.
This method can be used for higher radix point multiplication. For example, if
radix is 16 and we are computing
kQ
, then we are to precompute 2
Q
, 3
Q
, …, 15
Q
, to
divide
k
(as binary vector) into 4-bit blocks:
k
=
k
0
+ 16
k
1
+ … + 16
m
k
m
and to com-
pute successively
P
m
=
k
m
Q
,
P
i
-1
= 16
P
i
+
k
i
-1
Q
(6)
for
i
=
m
,
m
- 1, …, 1.
One iteration in (6) takes four point doublings and one point addition. If we repre-
sent exponent
k
in δ-base notation with
= 2
2
, radix is 4 and
one iteration takes only two doublings instead of four ones. Precomputation includes
4
δ
=
−
2
(mod
r
)
, then δ
3
=
i
computation of points
c
δ
P
with
c
i
∈ {-1, 0, 1}. Vectors (
c
3
,
c
2
,
c
1
,
c
0
) are such
i
i
0
that (*, 1, *, 1)
=
(*, 0, *, -1), where * means arbitrary digit. So we need 24 vectors
(up to inverse): (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 0, 1, -1), (0, 1, 0, 0), (0, 1, 0, -1),
(0, 1, 1, 0), (0, 1, -1, 0), (0, 1, 1, -1), (0, 1, -1, 1), (0, 1, -1, -1), (1, 0, 0, 0), (1, 0, 0, 1),
(1, 0, 0, -1), (1, 0, -1, 1), (1, 0, -1, 1), (1, 0, -1, -1), (1, 1, 0, 0), (1, -1, 0, 0), (1, 1, 0, -1),
(1, 1, -1, 0), (1, 1, -1, -1), (1, -1, -1, 0), (1, -1, -1, 1).
Note that ECDSA uses point multiplication for fixed points, so the bases for these
points can be computed independently. Here the number of field multiplications is
1.61 times smaller for 4-digit radix comparatively to usual doubling-addition 4-bit
radix algorithm.
To generate elliptic curve we are to find integers
a
,
b
such that
p
=
a
2
+ 2
b
2
is
prime and
p
+ 1 + 2
a
or
p
+ 1 - 2
a
has required large prime factor
r
.
3
−
2
-ary Exponent Representation
Let
K
=
Q
[
−
2
]
be quadratic imaginary field and
O
=
Z
[
−
2
]
be its ring of inte-
gers. Elliptic curve
E
(
K
) has endomorphism, given by complex multiplication by
−
2
,
so
the
prime
r
=
#
E
(
K
)
2
in
O
K
is
uniquely
factored
as
r
=
(
c
+
−
2
d
)(
c
−
−
2
d
)
=
ρ
ρ
. This factorization can be obtained from (2), (3):
2
r
= (
a
± 1)
2
+ 2
b
2
,
2
2
r
=
b
+
2
((
a
±
1
2
. Both ρ and ρ are primes in
Z
[
−
2
]
,
because their norm is prime in
Z
. Hence one of two congruences
ρ
≡
0
(mod
r
)
,
ρ
≡
0
(mod
r
)
holds if we take
−
2
modulo
r
. According to (4), transitions between
ρ and its conjugate are obtained by changing the sign of
−
2
(mod
p
)
, so without
loss of generality the first congruence will be considered.
