Cryptography Reference
In-Depth Information
factorization methods we have seen. This idea turned out to be fruitful and led to a
class of algorithms for the DL problem that are generically known as
index calculus
algorithms
(we recall here that 'index' is just another name for discrete logarithm).
As we will indicate, the similarities with the smoothness-based factorizationmethods
extend to the running times, which are also subexponential in this case.
We will give a description of the basic index calculus method for the groups
Z
p
but we shall not go into much detail for a couple of reasons. The first is that, from
a theoretical point of view, these algorithms are similar to factorization algorithms
such as the quadratic sieve which we have already discussed in some detail. More
importantly, the very fact that these algorithms exist has discouraged the use of
cryptographic schemes based on the DL problem in the multiplicative groups of finite
fields. The reason is that there are some important classes of groups—in particular
the elliptic curve groups that we will study in Chap.
11
—for which the only known
methods to solve the DL problem are the generic ones, which are exponential. This
makes these groups very appealing from a cryptographic point of view because the
additional difficulty of the problem allows the use of smaller key lengths, which
is obviously beneficial for key management, efficiency and so on. In addition, we
also remark that some of the more advanced index calculus algorithms, such as the
ones inspired by NFS and those that use function fields, require a mathematical
background that is beyond the scope of this topic.
We next describe the basic index calculus algorithm for
Z
p
. Suppose that
g
∈ Z
p
is
∈ Z
p
. The problem
a primitive root modulo
p
, i.e., a generator of the group, and that
a
∈ Z
p
−
1
. In a similar way to the quadratic sieve factorization
algorithm, the basic idea is to choose a factor base
FB
is then to compute log
g
a
={
p
1
,
p
2
,...,
p
k
}
, consisting
of small primes (usually all the primes
B
for a smoothness bound
B
), and obtain
factorizations over the factor base of group elements of the form
g
t
mod
p
.Here
the integers
t
will be randomly chosen in the interval
≤
and so the resulting
algorithm is probabilistic. To factorize these residues, a method such as trial division,
the rho method, or the more powerful Elliptic Curve Method, is used and a series of
relations
is obtained:
[
1
,
p
−
2
]
k
p
e
1
j
j
g
t
1
mod
p
=
,
j
=
1
k
p
e
2
j
j
g
t
2
mod
p
=
,
j
=
1
.
k
p
e
lj
j
g
t
l
mod
p
=
.
(6.3)
j
=
1
