Cryptography Reference
In-Depth Information
resulting value 49 to B. B, in turn, randomly selects
x
b
=39, computes
y
b
≡
11
39
(mod 347) = 285, and sends the resulting value 285 to A. A
now computes
y
x
a
b
285
240
(mod 347) = 268, and B computes
y
x
b
a
≡
49
39
(mod 347) = 268. Consequently,
K
= 268 is the shared secret that can
be used as a session key.
≡
Note that an adversary eavesdropping on the communication channel between
A and B knows
p
,
g
,
y
a
,and
y
b
, but does not know
x
a
and
x
b
. The problem of
determining
K
g
x
a
x
b
(mod
p
) from
y
a
and
y
b
(without knowing
x
a
or
x
b
)is
known as the DHP (see Definition 7.6). As already explained in Section 7.2.1, the
DHP is as difficult to solve as the DLP, but it is still an open question whether it is
always (i.e., in every group) necessary to compute a discrete logarithm to solve an
instance of the DHP.
Also note that the Diffie-Hellman key exchange protocol can be transformed
into a (probabilistic) asymmetric encryption system. For a plaintext message
m
(that
represents an element of the cyclic group), A randomly selects an
x
a
, computes
the common key
K
ab
(using B's public exponent and following the Diffie-Hellman
key exchange protocol), and combines
m
with
K
ab
to obtain the ciphertext
c
.The
special case where
c
=
mK
ab
refers to the ElGamal asymmetric encryption system
addressed in Section 14.2.3.
Like any other protocol that employs public key cryptography, the Diffie-
Hellman key exchange protocol is vulnerable to the
man-in-the-middle attack
.Note
what happens if an adversary C is able to place himself or herself between A and B
and provide both with messages of his or her choice. In this case, C can provide A
and B with faked public exponents. More specifically, C can provide A with
y
b
(of
which he or she knows the private exponent
x
b
) and B with
y
a
(of which he or she
knows the private exponent
x
a
). In this case, A computes
K
ab
≡
≡
y
x
a
b
(mod
p
) and
y
x
a
(mod
p
)
and thinks that he or she shares this key with A. In reality, they both don't share any
key with each other, but they both share a key with C. If, for example, A wanted
to send a secret message to B, A would use the key he or she thinks is being
shared with B to encrypt the message, and send it to B accordingly. C would be
sitting in the line and grab the message. Equipped with
K
ab
, C would be able to
decrypt the message, eventually modify it, reencrypt it with
K
b
a
, and forward it to
B. B, in turn, would successfully decrypt the message using
K
b
a
and think that the
message is authentically coming from A. The only way to protect the communicating
entities against this type of attack is to make sure that the public exponents are
authentic. So, in practice, the native Diffie-Hellman key exchange protocol is usually
combined with a mutual authentication protocol to come up with an authenticated
key exchange protocol. Examples include the station-to-station (STS) protocol [8]
thinks that he or she shares this key with B, and B computes
K
b
a
≡
