Cryptography Reference
In-Depth Information
=
p
e
1
p
e
2
p
e
l
l
|
G
|
·
·
...
·
be the prime factorization of the group order
|
G
|
. Again, we attempt to compute
a discrete logarithm
x
= log
in
G
. This is also a divide-and-conquer algorithm.
The basic idea is that rather than dealing with the large group
G
, one computes
smaller discrete logarithms
x
i
≡
α
β
x
mod
p
e
i
i
in the subgroups of order
p
e
i
. The desired
discrete logarithm
x
can then be computed from all
x
i
,
i
= 1
,...,
l
,byusingthe
Chinese Remainder Theorem. Each individual small DLP
x
i
can be computed using
Pollard's rho method or the baby-step giant-step algorithm.
The run time of the algorithm clearly depends on the prime factors of the group
order. To prevent the attack, the group order must have its largest prime factor in the
range of 2
160
. An important practical consequence of the Pohlig-Hellman algorithm
is that one needs to know the prime factorization of the group order. Especially in
the case of elliptic curve cryptosystems, computing the order of the cyclic group is
not always easy.
Nongeneric Algorithms: The Index-Calculus Method
All algorithms introduced so far are completely independent of the group being
attacked, i.e., they work for discrete logarithms defined over any cyclic group. Non-
generic algorithms efficiently exploit special properties, i.e., the inherent structure,
of certain groups. This can lead to much more powerful DL algorithms. The most
important nongeneric algorithm is the index-calculus method.
Both the baby-step giant-step algorithm and Pollard's rho method have a run time
which is exponential in the bit length of the group order, namely of about 2
n
/
2
steps,
where
n
is the bit length of
. This greatly favors the crypto designer over the
cryptanalyst. For instance, increasing the group order by a mere 20 bit increases the
attack effort by a factor of 1024 = 2
10
. This is a major reason why elliptic curves
have better long-term security behavior than RSA or cryptosystems based on the
DLP in
|
G
|
Z
p
. The question is whether there are more powerful algorithms for DLPs
in certain specific groups. The answer is yes.
The index-calculus method is a very efficient algorithm for computing discrete
logarithms in the cyclic groups
Z
p
and
GF
(2
m
)
∗
. It has a subexponential running
time. We will not introduce the method here but just provide a very brief description.
The index-calculus method depends on the property that a significant fraction of
elements of
G
can be efficiently expressed as products of elements of a small subset
of
G
. For the group
Z
p
this means that many elements should be expressable as a
product of small primes. This property is satisfied by the groups
Z
p
and
GF
(2
m
)
∗
.
However, one has not found a way to do the same for elliptic curve groups. The
index calculus is so powerful that in order to provide a security of 80 bit, i.e., an
attacker has to perform 2
80
Z
p
should be at least
1024 bit long. Table 8.3 gives an overview on the DLP records achieved since the
early 1990s. The index-calculus method is somewhat more powerful for solving
the DLP in
GF
(2
m
)
∗
. Hence the bit lengths have to be chosen somewhat longer to
steps, the prime
p
of a DLP in
