Cryptography Reference
In-Depth Information
Exercise 6.32
Modify the function
BSGS
so that it uses Maple's commands
compiletable
and
tablelook
(it should work well for small numbers but
for larger numbers it will require much more memory and will be significantly less
efficient than
BSGS
).
6.5.2 Pollard's Rho Method for Discrete Logarithms
As already mentioned, the main drawback of the baby-step giant-step algorithm
is that it requires a lot of storage. Pollard devised a method to compute discrete
logarithms that is analogous to the rho factoring method and that, while having the
same running time as the BSGS method, requires almost no storage. The original
formulation was for the group
Z
p
but the method can be applied to any group whose
elements can be encoded as strings. So let
G
be a finite cyclic group of order
n
,
g
∈
G
a generator, and let
a
∈
G
be an element whose discrete logarithm to the base
g
,
l
∈ Z
n
, we want to compute.
The idea is then to find a collision between elements
g
r
a
s
and
g
t
a
u
. Since we can
compute inverses and exponentiations efficiently in
G
, this gives us
g
r
−
t
=
log
g
a
a
u
−
s
=
and hence
g
r
−
t
g
l
(
u
−
s
)
. The exponents here are uniquely determined modulo the
order
n
of
g
so that this equality is equivalent to
l
=
and we
can recover the discrete logarithm
l
by solving this congruence as explained below.
As in the rho factoringmethod, the procedure to obtain a collision consists of using
a function
F
(
u
−
s
)
≡
r
−
t
(
mod
n
)
:
→
G
which is sufficiently simple to keep track of its images but
behaves heuristically like a random function. Following the original idea of Pollard,
we may consider a partition of
G
into three disjoint subsets which are not related to
the group structure of
G
,
G
G
=
S
1
∪
S
2
∪
S
3
, and define
F
:
G
→
G
as follows:
⎧
⎨
gx
if
x
∈
S
1
,
x
2
F
(
x
)
=
if
x
∈
S
2
,
⎩
ax
if
x
∈
S
3
.
Now, if we repeatedly apply the function
F
starting at
x
0
=
1, we obtain, after
g
r
i
a
s
i
and the idea is to compute the values of
x
i
and of the exponents
r
i
and
s
i
at the same time until a collision is found which,
by the birthday paradox, is to be expected after
O
i
steps, an element of the form
x
i
=
(
√
n
)
steps (note that we should
assume that 1
1 for, otherwise, this would be a fixed
point and the sequence would remain stationary at this value).
The procedure to keep track of the exponents
r
i
,
∈
S
2
if we want to start at
x
0
=
s
i
is to lift the sequence
x
0
=
1,
x
1
=
F
(
x
0
)
,
...
,
x
i
=
F
(
x
i
−
1
)
,
...
to a sequence
{
(
r
i
,
s
i
)
}
in
Z
n
× Z
n
such that
g
r
i
a
s
i
=
x
i
. In fact, these two sequences are related by the group homomorphism
g
r
a
s
, which is actually surjective because the
generator
g
belongs to its image which, being a subgroup, must be equal to all
G
.
If we use the function
F
h
: Z
n
× Z
n
→
G
given by
h
(
r
,
s
)
=
:
G
→
G
defined above, then the sequence
{
(
r
i
,
s
i
)
}
of
Z
n
× Z
n
such that
h
((
r
i
,
s
i
))
=
elements of
x
i
for each
i
, is computed as follows. It
