Cryptography Reference
In-Depth Information
8 Public-Key Cryptosystems Based on the Discrete Logarithm Problem
approximately 2 40 = 2 80 computations and memory locations, which is easily
achievable with today's PCs and hard disks. Thus, in order to obtain an attack com-
plexity of 2 80 , a group must have a cardinality of at least
2 160 . In the case of
|
G
|≥
Z p , the prime p should thus have at least a length of 160 bit. However,
as we see below, there are more powerful attacks against DLPs in
groups G =
Z p which forces
even larger bit lengths of p .
Pollard's Rho Method
(
Pollard's rho method has the same expected run time
) as the baby-step
giant-step algorithm but only negligible space requirements. The method is a prob-
abilistic algorithm which is based on the birthday paradox (cf. Section 11.2.3). We
will only sketch the algorithm here. The basic idea is to pseudorandomly generate
group elements of the form
O
|
G
|
j . For every element we keep track of the values i
and j . We continue until we obtain a collision of two elements, i.e., until we have:
i
α
· β
i 1
j 1 =
i 2
j 2 .
· β
· β
α
α
(8.3)
x and compare the exponents on both sides of the equation,
the collision leads to the relation i 1 + xj 1
If we substitute
β
=
α
i 2 + xj 2 mod
|
G
|
. (Note that we are in
a cyclic group with
|
G
|
elements and have to take the exponent modulo
|
G
|
.) From
here the discrete logarithm can easily computed as:
i 2
i 1
x
mod
|
G
|
j 1
j 2
An important detail, which we omit here, is the exact way to find the collision (8.3).
In any case, the pseudorandom generation of the elements is a random walk through
the group. This can be illustrated by the shape of the Greek letter rho, hence the
name of this attack.
Pollard's rho method is of great practical importance because it is currently the
best known algorithm for computing discrete log arit hms in elliptic curve groups.
Since the method has an attack complexity of
( |
) computations, elliptic curve
groups should have a size of at least 2 160 . In fact, elliptic curve cryptosystems with
160-bit operands are very popular in practice.
There are still much more powerful attacks known for the DLP in
O
G
|
Z p , as we will
see below.
Pohlig-Hellman Algorithm
The Pohlig-Hellman method is an algorithm which is based on the Chinese Re-
mainder Theorem (not introduced in this topic); it exploits a possible factorization
of the order of a group. It is typically not used by itself but in conjunction with any
of the other DLP attack algorithms in this section. Let
 
Search WWH ::




Custom Search