Cryptography Reference
In-Depth Information
we have
k
0
= 0. Therefore,
Q
1
=
Q −
0
P
=
Q.
N
Since (
N/
4)
Q
1
= 150
Q
1
= (598
,
0) = 1
·
2
P
,wehave
k
1
= 1. Therefore,
Q
2
=
Q
1
−
1
·
2
· P
=(35
,
243)
.
N
Since (
N/
8)
Q
2
=75
Q
2
=
∞
=0
·
2
P
,wehave
k
2
= 0. Therefore,
k
=0+1
·
2+0
·
4+
···≡
2(mod
.
kmod3
.Wehave
T
=
{∞
,
(0
,
1)
,
(0
,
598)
}
.Since
N
3
P,
(
N/
3)
Q
=(0
,
598) = 2
·
we have
k
0
= 2. Therefore,
k ≡
2(mod
.
kmod25
.Wehave
T
=
{∞
,
(84
,
179)
,
(491
,
134)
,
(491
,
465)
,
(84
,
420)
}
.
Since (
N/
5)
Q
=(84
,
179), we have
k
0
=1. Then
Q
1
=
Q −
1
· P
= (130
,
129)
.
Since (
N/
25)
Q
1
= (491
,
465), we have
k
1
= 3. Therefore,
k
=1+3
·
5+
···≡
16
(mod 25)
.
We now have the simultaneous congruences
⎧
⎨
x
2(mod )
x ≡
2(mod )
x ≡
16
≡
.
⎩
(mod 25)
These combine to yield
k
≡
266 (mod 600), so
k
= 266.
The Pohlig-Hellman method works well if all of the prime numbers dividing
N
are small. However, if
q
is a large prime dividing
N
, then it is di
cult to
list the elements of
T
, which contains
q
elements. We could try to find the
k
i
without listing the elements; however, finding
k
i
is a discrete log problem in
the group generated by (
N/q
)
P
, which has order
q
.If
q
is of the same order of
magnitude as
N
(for example,
q
=
N
or
q
=
N/
2), then the Pohlig-Hellman
method is of little use. For this reason, if a cryptographic system is based on
Search WWH ::
Custom Search