Cryptography Reference
In-Depth Information
Discrete Logarithm Problem
This chapter sketched the most important attack al-
gorithms for solving discrete logarithm problems. A good overview on these, in-
cluding further references, are given in [168, p. 164 ff.]. We also discussed the re-
lationship between the Diffie-Hellman problem (DHP) and the discrete logarithm
problem (DLP). This relationship is a matter of great importance for the foundations
of cryptography. Key contributions which study this are [31, 118].
The idea of using the DLP in groups other than
p
is exploited in elliptic curve
cryptography, a topic that is treated in Chapter 9. Other cryptoystems based on the
generalized DLP include hyperelliptic curves, a comprehensive treatment of which
can be found in [44]. Rather than using the prime field
Z
p
it is also possible to use
certain extension fields which offer computational advantages. Two of the better-
studied DL systems over extension fields are Lucas-Based Cryptosystems [26] and
Efficient and Compact Subgroup Trace Representation (XTR) [109].
Z
8.7 Lessons Learned
The Diffie-Hellman protocol is a widely used method for key exchange. It is
based on cyclic groups.
The discrete logarithm problem is one of the most important one-way functions
in modern asymmetric cryptography. Many public-key algorithms are based on
it.
In practice, the multiplicative group of the prime field
Z
p
or the group of an
elliptic curve are used most often.
Z
p
, the prime
p
should be at least 1024 bits
long. This provides a security roughly equivalent to an 80-bit symmetric cipher.
For a better long-term security, a prime of length 2048 bits should be chosen.
For the Diffie-Hellman protocol in
The Elgamal scheme is an extension of the DHKE where the derived session key
is used as a multiplicative masked to encrypt a message.
Elgamal is a probabilistic encryption scheme, i.e., encrypting two identical mes-
sages does not yield two identical ciphertexts.
Z
p
, the prime
p
should be at least 1024
For the Elgamal encryption scheme over
bits long, i.e.,
p
>
2
1000
.
