Cryptography Reference
In-Depth Information
Let
E
be an elliptic curve over
F
q
.Let
P, Q
∈
E
(
F
q
). Let
N
be the order
of
P
. Assume that
gcd(
N, q
)=1
.
We want to find
k
such that
Q
=
kP
. First, it's worthwhile to check that
k
exists.
LEMMA 5.1
Thereexists
k
su ch that
Q
=
kP
ifand onlyif
NQ
=
∞
and the W eilparing
e
N
(
P, Q
)=1
.
PROOF
If
Q
=
kP
,then
NQ
=
kNP
=
∞
.Also,
e
N
(
P, Q
)=
e
N
(
P, P
)
k
=1
k
=1
.
Conversely, if
NQ
=
∞
,then
Q ∈ E
[
N
]. Since gcd(
N, q
)=1,wehave
E
[
N
]
Z
N
⊕
Z
N
, by Theorem 3.2. Choose a point
R
such that
{P, R}
is a
basis of
E
[
N
]. Then
Q
=
aP
+
bR
for some integers
a, b
. By Corollary 3.10,
e
N
(
P, R
)=
ζ
is a primitive
N
th
root of unity. Therefore, if
e
N
(
P, Q
)=1,wehave
1=
e
N
(
P, Q
)=
e
N
(
P, P
)
a
e
N
(
P, R
)
b
=
ζ
b
.
This implies that
b ≡
0(mod
N
), so
bR
=
∞
. Therefore,
Q
=
aP
, as desired.
The idea used to prove the lemma yields the MOV attack on discrete logs
for elliptic curves. Choose
m
so that
E
[
N
]
⊆ E
(
F
q
m
)
.
Since all the points of
E
[
N
] have coordinates in
F
q
=
∪
j≥
1
F
q
j
,suchan
m
exists. By Corollary 3.11, the group
μ
N
of
N
th roots of unity is contained in
F
q
m
. All of our calculations will be done in
F
q
m
. The algorithm is as follows.
1. Choose a random point
T ∈ E
(
F
q
m
).
2. Compute the order
M
of
T
.
3. Let
d
=gcd(
M, N
), and let
T
1
=(
M/d
)
T
.Then
T
1
has order
d
,which
divides
N
,so
T
1
∈ E
[
N
].
4. Compute
ζ
1
=
e
N
(
P, T
1
)and
ζ
2
=
e
N
(
Q, T
1
). Then both
ζ
1
and
ζ
2
are
in
μ
d
⊆
F
q
m
.
in
F
q
m
. This will give
k
(mod
d
).
5. Solve the discrete log problem
ζ
2
=
ζ
1
Search WWH ::
Custom Search