Cryptography Reference
In-Depth Information
IDEA BEHIND THE DIFFIE-HELLMAN PROTOCOL
The Diffie-Hellman protocol requires the existence of:
• A public-key cryptosystem with a special property, which we discuss shortly.
We denote the public and private keys of Alice and Bob in this cryptosystem
by (
P
A
,
S
B
), respectively. These may be temporary key pairs that
have been generated specifically for this protocol run, or could be long-term
key pairs that are used for more than one protocol run.
•A
combination function F
with a special property, which we discuss shortly.
By a 'combination' function, we mean a mathematical process that takes two
numbers
x
and
y
as input, and outputs a third number which we denote
F
(
x
,
y
).
Addition is an example of a combination function, with
F
(
x
,
y
)
=
x
+
y
.
The Diffie-Hellman protocol is designed for environments where secure channels
do not yet exist. Indeed, it is often used to establish a symmetric key, which can
then be used to secure such a channel. It is important to remember that, unless
otherwise stated, we assume that all the exchanged messages take place over
an unprotected (public) channel that an attacker can observe and, potentially,
modify. The basic idea behind the Diffie-Hellman protocol is that:
S
A
) and (
P
B
,
1. Alice sends her public key
P
A
to Bob.
2. Bob sends his public key
P
B
to Alice.
3. Alice computes
F
(
S
A
,
P
B
). Note that only Alice can conduct this computation,
since it involves her private key
S
A
.
4. Bob computes
F
(
S
B
,
P
A
). Note that only Bob can conduct this computation,
since it involves his private key
S
B
.
The special property for the public-key cryptosystem and the combination
function
F
is that
.
At the end of the protocol Alice and Bob will thus share this value, which we
denote
Z
AB
. As we will discuss in a moment, this shared value
Z
AB
can then easily
be converted into a key of the required length. Since the private keys of Alice and
Bob are both required to compute
Z
AB
, it should only be computable by Alice and
Bob, and not anyone else (an attacker) who observed the protocol messages. Note
that this is true despite the fact that the attacker will have seen
P
A
and
P
B
.
The somewhat surprising aspect of the Diffie-Hellman protocol is that
without
sharing any secret information
, Alice and Bob are able to jointly generate a secret
value by communicating only over a public channel. This was a revolutionary idea
when it was first proposed in 1976, and remains a slightly counterintuitive one.
This property makes the Diffie-Hellman protocol extremely useful.
F
(
S
A
,
P
B
)
=
F
(
S
B
,
P
A
)
INSTANTIATION OF THE DIFFIE-HELLMAN PROTOCOL
In order to fully specify the Diffie-Hellman protocol, we need to find a suitable
public-key cryptosystem and a suitable function
F
. Fortunately, we will not need
