Cryptography Reference
In-Depth Information
Input
:
g
and
y
in a group
G
of order
n
Output
: the logari
th
m of
y
in basis
g
Complexity
:
(
√
n
) group operations
1:
pick a random function
h
:
G
O
−→ {
1
,
2
,
3
}
,
b
a
←
(1
,
0
,
0)
∈
G
×
Z
n
×
Z
n
2:
3:
repeat
4:
a
←
f
(
a
)
f
(
f
(
b
))
6:
until
a
1
=
b
←
5:
b
1
7:
output (
a
2
−
b
2
)
/
(
a
3
−
b
3
) mod
n
{
fail if not possible
}
Figure 7.8.
Pollard Rho Discrete Logarithm Algorithm.
Let
B
be
#
G
(if
#
G
is not available,
B
can be any upper bound of
#
G
). We proceed
as shown in Fig. 7.9. The algorithm eventually succeeds: if
x
is the unknown logarithm
modulo
#
G
, we know that
x
∈{
0
,...,
. It can thus be written
x
=
i
+
j
, for which
we get the match in the
ab
ove algorithm. Therefore this algorithm computes the discr
ete
logarithm within
O
(
√
B
)
group operations. (One problem is that it requires
O
(
√
B
)
memory space as well.)
2
−
1
}
7.4.3
Pohlig-Hellman Algorithm
Here we describe the
Pohlig-Hellman algorithm
(see Ref. [145]). It reduces the com-
putation of a discrete logarithm within a group
G
(the factorization of the order of
which
#
G
=
p
a
1
1
p
a
n
n
is known) into computing discrete logarithms in groups of order
···
p
n
. Combining this reduction with the Shanks baby steps - giant steps algo-
rithm we obtain an algorithm which solves the DLKOFP problem, i.e. which enables
the computation of discrete logarithms in a
B
-smooth ordered group of known factor-
p
1
,...,
Input
:
g
and
y
in a group
G
,
B
an upper bound for #
G
Output
: the logari
th
m of
y
in basis
g
Complexity
:
(
√
B
) group operations
Precomputati
on
1:
let
O
=
√
B
be the size of a “giant step”
2:
for
i
=
0
,...,
−
1
do
insert (
g
i
,
i
) into a hash table
3:
4:
end for
Algorithm
5:
for
j
=
0
,...,
−
1
do
yg
−
j
compute
z
=
6:
if
wehavea(
z
,
i
) in the hash table
then
7:
we get
yg
−
j
g
i
}
yield
x
=
i
+
j
and stop
{
=
8:
9:
end if
10:
end for
Figure 7.9.
Baby Steps - Giant Steps Algorithm.
Search WWH ::
Custom Search