Cryptography Reference
In-Depth Information
Chapter 8
Public-Key Cryptosystems Based on the Discrete
Logarithm Problem
In the previous chapter we learned about the RSA public-key scheme. As we have
seen, RSA is based on the hardness of factoring large integers. The integer factoriza-
tion problem is said to be the
one-way function
of RSA. As we saw earlier, roughly
speaking a function is
one-way
if it is computationally easy to compute the func-
tion
f
(
x
)=
y
, but computationally infeasible to invert the function:
f
−
1
(
y
)=
x
.The
question is whether we can find other one-way functions for building asymmetric
crypto schemes. It turns out that most non-RSA public-key algorithms with practical
relevance are based on another one-way function, the discrete logarithm problem.
In this chapter you will learn:
The Diffie-Hellman key exchange
Cyclic groups which are important for a deeper understanding of Diffie-Hellman
key exchange
The discrete logarithm problem, which is of fundamental importance for many
practical public-key algorithms
Encryption using the Elgamal scheme
The security of many cryptographic schemes relies on the computational in-
tractability of finding solutions to the
Discrete Logarithm Problem (DLP)
. Well-
known examples of such schemes are the Diffie-Hellman key exchange and the
Elgamal encryption scheme, both of which will be introduced in this chapter. Also,
the Elgamal digital signature scheme (cf. Section 8.5.1) and the digital signature
algorithm (cf. Section 10.2) are based on the DLP, as are cryptosystems based on
elliptic curves (Section 9.3).
We start with the basic Diffie-Hellman protocol, which is surprisingly simple
and powerful. The discrete logarithm problem is defined in what are called
cyclic
groups
. The concept of this algebraic structure is introduced in Section 8.2. A formal
definition of the DLP as well as some illustrating examples are provided, followed
by a brief description of attack algorithms for the DLP. With this knowledge we will
revisit the Diffie-Hellman protocol and more formally talk about its security. We
will then develop a method for encrypting data using the DLP that is known as the
Elgamal cryptosystem.
