Cryptography Reference
In-Depth Information
The result is that Eve was successful and nowAlice and Bob share a key
k
which is
also known to Eve. Therefore, Eve can passively eavesdrop on all encryptedmessages
subsequently exchanged between Alice and Bob. What should Alice and Bob do to
prevent this attack? As we have mentioned, a good solution is to choose the modulus
p
to be a safe prime. Then
2 would be prime itself and trying to mount
the same attack as above would not work for then
q
would be the order of
g
and so
u
(
p
−
1
)/
2
(
p
−
1
)/
v
(
p
−
1
)/
2
1 and, when receiving these values from each other, Alice
and Bob would easily notice that something was going on. Indeed, in the next step
they would have to send
x
and
y
through the channel allowing an eavesdropper to
recover the key. But even with the prime
p
chosen by Alice and Bob, they could have
thwarted the attack by checking the order of the elements
u
2
and
v
2
they received
from each other. Alice had checked that the element
u
she sent to Bob had order
qr
and similarly Bob had checked that
v
had order
qr
so they should also check that the
elements they receive from each other have this property. Thus, upon receiving
u
2
supposedly from Alice, Bob should check that its order is not a divisor of
r
which is
equivalent to
=
=
r
(
u
2
)
=
1 by Proposition 2.4. To do that, he would compute:
> Power(u_2, r) mod p;
1
This would tell Bob that the order of
u
2
is a divisor of
r
and hence that
u
2
fails
this test. Thus Bob should reject
u
2
and, similarly, Alice should reject
v
2
. These
precautions are also effective against passive attackers who can find the key if the
elements exchanged have low order, but, of course, the most general and effective
method to counter active attacks like this one is, as already pointed out, to use an
authenticated channel.
Exercise 7.5
Looking at the code of the function
findqrgenerator
above,
explain in detail the reasons why
g
is indeed a generator of
QR
p
.
Exercise 7.6
In the previous example, suppose that an integer
z
is chosen uniformly
at random in the range 2
1 and calculate the probability that the order
o
of
g
z
..
qr
−
Z
p
satisfies:
(i)
o
in
=
qr
.
(ii)
o
≥
q
.
7.2.5 Concluding Remarks on the Diffie-Hellman Protocol
Despite being the very first public-key protocol defined, the Diffie-Hellman key
agreement remains widely used today as an important component of several protocols
such as, for example, the IPsec protocol suite for network communications. Thus the
DH protocol is not merely of historical importance but is also practically relevant.
Since the basic protocol is vulnerable to man-in-the-middle attacks, the versions that
are actually used rely on variants that are resistant to these attacks and whose nucleus
is the original DH protocol. The most important attacks against the protocol are based
