Cryptography Reference
In-Depth Information
k
r−
1
q
r−
1
P
.
8. Let
Q
r
=
Q
r−
1
−
q
r
+1
Q
r
=
k
r
q
P
.
N
9. Determine
k
r
such that
10. If
r
=
e −
1, stop. Otherwise, return to step (7).
Then
k ≡ k
0
+
k
1
q
+
·
+
k
e−
1
q
e−
1
(mod
q
e
)
.
Whydoesthiswork? Wehave
N
q
Q
=
N
q
(
k
0
+
k
1
q
+
···
)
P
=
k
0
N
)
NP
=
k
0
N
q
P
+(
k
1
+
k
2
q
+
···
q
P,
since
NP
=
∞
. Therefore, step (2) finds
k
0
.Then
k
0
P
=(
k
1
q
+
k
2
q
2
+
Q
1
=
Q
−
···
)
P,
so
N
q
2
Q
1
=(
k
1
+
k
2
q
+
···
)
N
q
P
=
k
1
N
q
P
+(
k
2
+
k
3
q
+
···
)
NP
=
k
1
N
q
P.
Therefore, we find
k
1
. Similarly, the method produces
k
2
,k
3
,...
.Wehave
to stop after
r
=
e −
1since
N/q
e
+1
is no longer an integer, and we cannot
multiply
Q
e
by the noninteger
N/q
e
+1
. Besides, we do not need to continue
because we now know
k
mod
q
e
.
Example 5.4
Let
G
=
E
(
F
599
), where
E
is the elliptic curve given by
y
2
=
x
3
+1. Let
P
=(60
,
19) and
Q
= (277
,
239). The methods of Section 4.3.3 can be used
to show that
P
has order
N
= 600. We want to solve
Q
=
kP
for
k
.The
prime factorization of
N
is
600 = 2
3
·
3
·
5
2
.
We'll compute
k
mod 8, mod 3, and mod 25, then recombine to obtain
k
mod
600 (the Chinese Remainder Theorem allows us to do this).
kmod8
. We compute
T
=
{∞
,
(598
,
0)
}
.Since
N
2
P
,
(
N/
2)
Q
=
∞
=0
·
Search WWH ::
Custom Search