Cryptography Reference
In-Depth Information
Diffie-Hellman Key Exchange
Alice
Bob
choose
a
=
k
pr
,
A
∈{
2
,...,
p
−
2
}
choose
b
=
k
pr
,
B
∈{
2
,...,
p
−
2
}
a
b
compute
A
=
k
pub
,
A
≡
α
mod
p
compute
B
=
k
pub
,
B
≡
α
mod
p
k
pub
,
A
=
A
−−−−−−−−−−−−−−→
k
pub
,
B
=
B
←−−−−−−−−−−−−−−
k
AB
=
k
k
pr
,
A
k
AB
=
k
k
pr
,
B
pub
,
B
≡
B
a
pub
,
A
≡
A
b
mod
p
mod
p
Here is the proof that this surprisingly simple protocol is correct, i.e., that Alice
and Bob in fact compute the same session key
k
AB
.
Proof.
Alice computes
B
a
b
)
a
ab
≡
(
α
≡
α
mod
p
while Bob computes
A
b
a
)
b
ab
≡
(
α
≡
α
mod
p
ab
mod
p
. The key can
now be used to establish a secure communication between Alice and Bob, e.g., by
using
k
AB
as key for a symmetric algorithm like AES or 3DES.
and thus Alice and Bob both share the session key
k
AB
≡
α
We'll look now at a simple example with small numbers.
Example 8.1.
The Diffie-Hellman domain parameters are
p
= 29 and
α
= 2. The
protocol proceeds as follows:
Alice
Bob
choose
a
=
k
pr
,
A
= 5
choose
b
=
k
pr
,
B
= 12
A
=
k
pub
,
A
= 2
5
B
=
k
pub
,
B
= 2
12
≡
3 mod 29
≡
7 mod 29
A
=3
−−−−−−−−−−−−→
B
=7
←−−−−−−−−−−−−
k
AB
=
B
a
7
5
= 16 mod 29
k
AB
=
A
b
= 3
12
≡
≡
16 mod 29
As one can see, both parties compute the value
k
AB
= 16, which can be used as a
joint secret, e.g., as a session key for symmetric encryption.
The computational aspects of the DHKE are quite similar to those of RSA. Dur-
ing the set-up phase, we generate
p
using the probabilistic prime-finding algorithms
discussed in Section 7.6. As shown in Table 6.1,
p
should have a similar length as
the RSA modulus
n
, i.e., 1024 or beyond, in order to provide strong security. The
integer
needs to have a special property: It should be a primitive element, a topic
which we discuss in the following sections. The session key
k
AB
that is being com-
puted in the protocol has the same bit length as
p
. If we want to use it as a symmetric
key for algorithms such as AES, we can simply take the 128 most significant bits.
Alternatively, a hash function is sometimes applied to
k
AB
and the output is then
used as a symmetric key.
α
