Cryptography Reference
In-Depth Information
Using, e.g., the extended Euclidean algorithm, we can compute 2
−
1
≡
6 mod 11
from which the discrete logarithm follows as:
2
−
1
3
x
≡
≡
7 mod 11
The discrete logarithm can be verified by looking at the small table provided above.
We can generalize the above trick to any group (
Z
n
,
+) for arbitrary
n
and ele-
ments
β
∈
Z
n
. Hence, we conclude that the generalized DLP is computationally
easy over
α
,
Z
n
. The reason why the DLP can be solved here easily is that we have
mathematical operations which are not in the additive group, namely multiplication
and inversion.
After this counterexample we now list discrete logarithm problems that have been
proposed for use in cryptography:
1. The multiplicative group of the prime field
Z
p
or a subgroup of it. For instance,
the classical DHKE uses this group, but also Elgamal encryption or the Digital
Signature Algorithm (DSA). These are the oldest and most widely used types of
discrete logarithm systems.
2. The cyclic group formed by an elliptic curve. Elliptic curve cryptosystems are
introduced in Chapter 9. They have become popular in practice over the last
decade.
3. The multiplicative group of a Galois field
GF
(2
m
) or a subgroup of it. These
groups can be used completely analogous to multiplicative groups of prime fields,
and schemes such as the DHKE can be realized with them. They are not as pop-
ular in practice because the attacks against them are somewhat more powerful
than those against the DLP in
Z
p
. Hence DLPs over
GF
(2
m
) require somewhat
higher bit lengths for providing the same level of security than those over
Z
p
.
4. Hyperelliptic curves or algebraic varieties, which can be viewed as generalization
as elliptic curves. They are currently rarely used in practice, but in particular
hyperelliptic curves have some advantages such as short operand lengths.
There have been proposals for other DLP-based cryptosystems over the years,
but none of them have really been of interest in practice. Often it was found that the
underlying DL problem was not difficult enough.
8.3.3 Attacks Against the Discrete Logarithm Problem
This section introduce methods for solving discrete logarithm problems. Readers
only interested in the constructive use of DL schemes can skip this section.
As we have seen, the security of many asymmetric primitives is based on the
difficulty of computing the DLP in cyclic groups, i.e., to compute
x
for a given
α
and
β
in
G
such that
