Cryptography Reference
In-Depth Information
Exercise 6.33
Show that each element of
G
has
n
distinct preimages by the function
h
g
r
a
s
, where
G
is a cyclic group of order
n
,
: Z
n
× Z
n
→
(
,
)
=
G
given by
h
r
s
g
a generator of
G
, and
a
G
. (Hint: This follows from the fact that Ker
h
is a
subgroup of order
n
or it can also be checked directly).
∈
We will briefly mention another generic method for the DLP which was also
introduced by Pollard at the same time as the rho method and has similar complexity
to the latter and minimal storage requirements too. It is called the
lambda method
or the
kangaroo method
. The idea is to take a walk from the group element
a
whose
logarithm we want to compute and another one from an element whose discrete
logarithm is known. If the two walks converge (which, when the paths are drawn
upwards produces the '
' shape) then the discrete logarithm of
a
can be found.
Pollard regarded the steps in these walks as jumps of two kangaroos, a tame one
starting at an element whose discrete logarithm is known, and a wild one starting
at the element
a
whose logarithm we search for. This algorithm is especially useful
when the discrete logarithm we search is known to lie in a short interval, in which
case this information can be exploited to make the algorithm run faster. We refer to
[60, 194] for detailed descriptions of the method.
An interesting feature of both the rho and the lambda methods is that they can
be parallelized (see [60] for details). The current record for an elliptic curve discrete
logarithm, to which we will come back with more details in Example 11.20, was
established in 2009 by means of a parallelized version of the rho method. This
computation found a discrete logarithm in a group whose order is a 112-bit prime
in a time of 3
λ
5 months (not counting idle time) on a cluster of more than 200
PlayStation 3 consoles (see [39] for more details). We will analyze the significance
of this computation when discussing the security of elliptic curve cryptography in
.
6.5.3 The Rho Method for Discrete Logarithms in Maple
Z
m
,
We next give a Maple implementation of the rho method for cyclic subgroups of
with
m
2, using the partition defined by Pollard. We follow the algorithm structure
sketched above to define the function
RhoDiscreteLog
which is given next. The
function has four input parameters:
m,g,a
and
n
, with the first three required and
the last optional.
m
is used to specify the modulus, i.e., to define the group
≥
Z
m
.
g
specifies the base
g
of the discrete logarithms and may (but need not) be a generator
of
G
.
a
is used to specify the element
a
whose logarithm we want to compute,
which should belong to the cyclic group generated by
g
(of course,
a
can be any
element of
Z
m
in case this group is cyclic and
g
is a generator). Finally,
n
takes as
value the order of
g
and, if not specified, it is computed by Maple using the function
numtheory:-order
, which supplies the default value. The function proceeds
according to the summary given in Algorithm 6.7, using the function
f
defined by
Pollard and, in case
b
[
3
]≡
c
[
3
]
(
mod
n
)
(with the above notation) and the order
