Cryptography Reference
In-Depth Information
of
G
that do not belong to
will not be exploited by the algorithm. Moreover,
we will generally assume that the order
n
of
g
is known (although in some cases it
is enough to know an upper bound on
n
). The most basic generic algorithm for the
DLP is a brute-force search in which the elements
g
x
are computed successively for
x
g
and compared to
a
until one such that
g
x
a
is found (note that here,
in contrast with the binary exponentiation method, we cannot take a shortcut and we
must compute all the powers
g
x
between
x
=
1
,
2
,...
=
=
1 and
x
=
log
g
a
). Since this process
stops at the latest when
x
steps each of which consists of
a group multiplication. For example, in the case of the group
G
=
n
−
1, it requires
O
(
n
)
= Z
p
, we obtain
2
that the running time is
O
. But we will see that, even for generic groups,
there are algorithms which are more efficient.
At the opposite extreme to the brute-force search, we have seen in Example 3.3
an efficient algorithm for the DLP in the additive group
(
n
len
(
p
)
)
Z
n
which, given a generator
g
∈ Z
n
(i.e., an element
g
∈ Z
n
such that gcd
(
g
,
n
)
=
1), and
a
∈ Z
n
, returns log
g
a
.
g
−
1
mod
n
(
·
)
This is just the element
a
mod
n
which may be computed in time
2
(
(
)
)
using the extended Euclidean algorithm. This discrete log algorithm is
specific to the groups
O
len
n
Z
n
because we have gone beyond the group structure and used
the fact that
Z
n
is actually a ring in which the generators of its additive group are the
same as the units of the ring.
6.5.1 The Baby-Step Giant-Step Algorithm and Its Maple
Implementation
The naive brute-force search algorithm for the DLP can be improved by using meth-
ods inspired by the birthday paradox. One possibility is to build, instead of just one
list of elements of
G
, two appropriate lists and search for a collision between them.
This is the idea underlying Shank's
baby-step giant-step
(BSGS) algorithm. As men-
tioned before, we will assume that the order of the cyclic group
G
is known,
although knowing an upper bound on this order is sufficient for this algorithm. So
let
n
be the order of
G
(or an upper bound) and
t
=
g
=
√
n
g
−
1
t
and suppose
,
h
=
(
)
that we want to compute the discrete logarithm of
a
∈
G
. Consider the lists of
elements of
G
:
g
2
g
t
−
1
,
1. 1
,
g
,
,...,
ah
2
ah
t
−
1
,
,
,
,...,
2.
a
ah
where the first one is constructed with multiplications by
g
(“baby steps”) and the
second with multiplications by
h
g
−
t
(“giant steps”). Then we look for a collision
between the lists, i.e., for a group element in their intersection, say
g
i
=
ah
j
=
=
g
−
1
tj
g
tj
)
−
1
. Multiplying both terms by
g
tj
we obtain
a
g
i
+
tj
and hence
a
(
)
=
a
(
=
we have that log
g
a
tj
. We will assume that the elements of the group
G
are
represented by strings that can be sorted (such will be the case in all our applications).
The algorithm may be described as follows:
=
i
+
