Cryptography Reference
In-Depth Information
ization, within a complexity which is essentially
O
(
√
B
)
group operations (plus some
extra logarithmic complexity factors).
Let
N
=
#
G
of given factorization
N
=
p
a
1
1
p
a
n
.
...
We first reduce the discrete logarithm computation to the case of
n
=
1
with the
following argument. If
x
is a discrete logarithm of
y
, then
x
is a discrete logarithm
of
y
α
i
in the subgroup generated by
g
α
i
. With
α
i
=
Np
−
a
i
, the later discrete logarithm
is in a subgroup of
G
of order
p
a
i
i
generated by
g
i
=
g
α
i
, thus a number modulo
p
a
i
.
Conversely,
x
i
is a discrete logarithm of
y
Np
−
a
i
modulo
p
a
i
i
in the subgroup generated by
g
Np
−
a
i
, and from the Chinese Remainder Theorem we can reconstruct
x
mod
N
such that
x
x
i
(mod
p
a
i
)
. We then notice that
yg
−
x
is equal to 1. This way we reduce the problem
of computing
x
in
G
into
n
problems of computing discrete logarithms in groups of
order
p
a
i
i
≡
for
i
=
1
,...,
n
.
To go further we can thus assume that
n
=
1
and
N
=
p
a
. We will reduce
the computation by
a
computations of discrete logarithms in subgroups of order
p
.
We proceed by computing
x
by more precise approximations of
x
by
x
j
=
x
mod
p
j
for
j
=
1
,...,
a
. Note that
x
0
=
1
is known. Assuming that we know
x
j
−
1
, we notice that
(
yg
−
x
j
−
1
)
p
a
−
j
is a power of
g
p
a
−
1
, hence of order
p
. Its discrete logarithm is indeed the
next base-
p
digit of
x
and enables the computation of
x
j
. We thus compute the discrete
logarithm of
(
yg
−
x
j
−
1
)
p
a
−
j
and get
x
j
.
To summarize, we have reduced the computation of
x
into
a
1
+···+
a
n
discrete
logarithm problems in subgroups of orders which are the prime factors of
N
. Since
a
1
+···+
a
n
=
O
(log
N
)
, we can combine
th
is reduction with Shanks algorithm and
obtain a full algorithm of complexity
O
(
√
B
log
N
)
group operations. The algorithm is
shown in Fig. 7.10.
As an example, we want to compute the logarithm of
y
=
123
in base
g
=
6
modulo
125651
. We first check that
p
is a prime, so
Z
p
is a cyclic group in which 123
is included. We have
p
−
1
=
125650
=
2
×
5
2
p
=
359
. We finally check that 6 is a
×
7
×
generator of
Z
p
because
6
p
−
1
1
for
q
=
2
,
5
,
7
,
359
. So 123 must be a power of 6
mod
p
=
q
modulo p.
Applying the Pohlig-Hellman algorithm, we have to compute the following loga-
rithms.
p
−
1
mod
p
(
y
p
−
2
)
mod
p
(
y
p
−
7
)
log
g
p
−
1
2
,
log
g
p
−
1
mod
p
(
y
)
,
log
g
p
−
1
7
,
5
2
5
2
mod
p
(
y
p
−
1
log
g
p
−
1
359
)
359
Search WWH ::
Custom Search