Information Technology Reference
In-Depth Information
Z
. If the set
of these endomorphisms is strongly larger than
Z
, elliptic curve has complex multi-
plication.
Security of elliptic curve cryptosystems, such as ECDSS [3], public key encryp-
tion, Diffie-Hellman key agreement, etc. relies upon the complexity of elliptic curve
discrete logarithm problem (ECDLP): given elliptic curve
E
(
F
q
), generator
Q
∈
E
(
F
q
)
of prime order
r
and
P
∈ 〈
Q
〉 find an exponent
l
such that
P
=
lQ
.
Generalized Pollard's algorithm [4] of complexity
Infinite group
E
F
(
)
has endomorphisms (
x
,
y
)
→
n
(
x
,
y
), where
n
∈
q
(
O
is the best known one
for solving ECDLP. If
E
(
F
q
) has efficiently counted non-trivial automorphism group,
then Pollard's algorithm can be executed in two stages. The first one deals with the
orbits of automorphism group and the second one refines logarithm inside the orbit
[5]. Usually such automorphisms correspond to complex multiplication.
For example, elliptic curve
E
(
F
p
):
y
2
=
x
3
+
B
,
p
)
≡
1 (mod 6), has automorphism
- ω + 1 = 0 in
F
p
. If
r
2
does not divide #
E
(
F
p
), then ϕ acts
in the cyclic subgroup of order
r
and ϕ
2
ϕ(
x
,
y
) = (ω
x
, -
y
), where ω
6
≡ 1 (mod
r
). Cardinality of affine point orbit
for this subgroup is equal to 6. For all the elements of the orbit the value
x
3
(and
y
2
) is
the same. There exists ρ ∈
F
r
such that ρ
6
= 1. If
l
denotes discrete logarithm of an
arbitrary element of the orbit, then ρ
l
(mod
r
) is discrete logarithm of so
m
e other
element of the orbit. This property decreases ECDLP complexity about 6 times.
Similarly, elliptic curve
E
(
F
p
):
y
2
=
x
3
+
Ax
,
p
≡ 1 (mod 4), has automorphism:
ϕ(
x
,
y
) = (-
x
,
iy
), where
i
2
= -1 in
F
p
. If
r
2
does not divide #
E
(
F
p
), then ϕ acts in the
cyclic subgroup of order
r
and ϕ
i
4
≡ 1 (mod
r
). For this curve ECDLP complexity is
decreased about 2 times.
ECDLP is hard if the following situation holds:
−
r
is a large prime (160 bits for ECDSS and 254-256 bits for Russian digital signa-
ture standard GOST R 34.10-2001;
r
2
does not divide group order in both stan-
dards),
*
−
there is no Weil pairing injective homomorphism [6] from
E
(
F
q
) to any group
F
n
for small exponents
n
(i.e.
q
k
≠ 1 (mod
r
) for 1 ≤
k
≤ 20 in ECDSS and 1 ≤
k
≤ 31
in GOST), and
−
there is no surjective homomorphism from
E
(
F
q
) to
F
p
[7] (i.e.
r
≠
p
, where
p
is the
characteristic of
F
q
).
2
Elliptic Curve with Complex Multiplication by
−
2
Elliptic curve cryptosystem rate is dictated by the complexity of multiplication a point
by a number. Usually this procedure is performed by doublings and additions [1]. For
example, to compute 25
Q
we represent 25 in binary: (11001), and then compute the
chain, beginning from the most significant digits: 2
3
(2
Q
+
Q
) +
Q
.
Point multiplication procedure allows further acceleration if higher radix exponent
representation is used, combined with signed binary digits (0, 1, -1) [8]. In signed
