Cryptography Reference
In-Depth Information
8.1 Diffie-Hellman Key Exchange
The
Diffie-Hellman key exchange (DHKE)
, proposed by Whitfield Diffie and Mar-
tin Hellman in 1976 [58], was the first asymmetric scheme published in the open
literature. The two inventors were also influenced by the work of Ralph Merkle.
It provides a practical solution to the key distribution problem, i.e., it enables two
parties to derive a common secret key by communicating over an insecure chan-
nel
1
. The DHKE is a very impressive application of the discrete logarithm problem
that we'll study in the subsequent sections. This fundamental key agreement tech-
nique is implemented in many open and commercial cryptographic protocols like
Secure Shell (SSH), Transport Layer Security (TLS), and Internet Protocol Security
(IPSec).The basic idea behind the DHKE is that exponentiation in
Z
p
,
p
prime, is a
one-way function and that exponentiation is commutative, i.e.,
x
)
y
y
)
x
k
=(
α
≡
(
α
mod
p
y
)
x
mod
p
is the joint secret which can be used as the
session key between the two parties.
Let us now consider how the Diffie-Hellman key exchange protocol over
x
)
y
≡
≡
The value
k
(
α
(
α
Z
p
works. In this protocol we have two parties, Alice and Bob, who would like to
establish a shared secret key. There is possibly a trusted third party that properly
chooses the public parameters which are needed for the key exchange. However, it is
also possible that Alice or Bob generate the public parameters. Strictly speaking, the
DHKE consists of two protocols, the set-up protocol and the main protocol, which
performs the actual key exchange. The set-up protocol consists of the following
steps:
Diffie-Hellman Set-up
1. Choose a large prime
p
.
2. Choose an integer
α
∈{
2
,
3
,...,
p
−
2
}
.
3. Publish
p
and
α
.
These two values are sometimes referred to as
domain parameters
. If Alice and
Bob both know the public parameters
p
and
computed in the set-up phase, they
can generate a joint secret key
k
with the following key-exchange protocol:
α
1
The channel needs to be authenticated, but that will be discussed later in this topic.
