Cryptography Reference
In-Depth Information
x
β
=
α α
...
α
=
α
x times
holds. We still do not know the exact difficulty of computing the discrete logarithm
x in any given actual group. What we mean by this is that even though some at-
tacks are known, one does not know whether there are any better, more powerful
algorithms for solving the DLP. This situation is similar to the hardness of integer
factorization, which is the one-way function underlying RSA. Nobody really knows
what the best possible factorization method is. For the DLP some interesting gen-
eral results exist regarding its computational hardness. This section gives a brief
overview of algorithms for computing discrete logarithms which can be classified
into generic algorithms and nongeneric algorithms and which will be discussed in
a little more detail.
Generic Algorithms
Generic DL algorithms are methods which only use the group operation and no
other algebraic structure of the group under consideration. Since they do not exploit
special properties of the group, they work in any cyclic group. Generic algorithms
for the discrete logarithm problem can be subdivided into two classes. The first
class encompasses algorithms whose running time depends on the size of the cyclic
group, like the brute-force search ,the baby-step giant-step algorithm and Pollard's
rho method. The second class are algorithms whose running time depends on the
size of the prime factors of the group order, like the Pohlig-Hellman algorithm.
Brute-Force Search
A brute-force search is the most naıve and computationally costly way for comput-
ing the discrete logarithm log α β
. We simply compute powers of the generator
α
successively until the result equals
β
:
=
1
α
β
=
2
α
β
.
=
x
α
β
Search WWH ::




Custom Search