Cryptography Reference
In-Depth Information
3.
A
computes the secret key
s
A
:=
y
x
B
mod
p
.
4.
B
computes the secret key
s
B
:=
y
x
A
mod
p
.
Since
s
A
≡ y
x
A
≡ a
x
B
x
A
≡ y
x
B
≡ s
B
mod
p,
B
A
after step 4,
A
and
B
are dealing with a common key. The values
p
and
a
do not
have to be kept secret, nor the values
y
A
and
y
B
exchanged in steps 1 and 2.
The security of the procedure depends on the difficulty in calculating discrete
logarithms in finite fields, and the difficulty of breaking the system is equivalent
to that of calculating values
x
A
or
x
B
from values
y
A
or
y
B
in
p
.
4
That the
calculation of
a
xy
from
a
x
and
a
y
in a finite cyclic group (the
Diffie-Hellman
problem
) is just as difficult as the calculation of discrete logarithms and thus
equivalent to this problem is, in fact, conjectured but has not been proved.
To ensure the security of the procedure under these conditions the modulus
p
must be chosen sufficiently large (at least 1024 bits, better 2048 or more; see
Table 17-1), and one should ensure that
p −
1
contains a large prime divisor
close to
(
p −
1)
/
2
to exclude particular calculational procedures for discrete
logarithms (a constructive procedure for such prime numbers will be presented
in Chapter 17 in connection with the generation of
strong
primes, for example for
the RSA procedure).
The procedure has the advantage that secret keys can be generated as needed
on an ad hoc basis, without the need for secret information to be held for a long
time. Furthermore, for the procedure to be used there are no further infrastructure
elements necessary for agreeing on the parameters
a
and
b
. Nonetheless, this
protocol possesses some negative characteristics, the gravest of which is the lack
of authentication proofs for the exchanged parameters
y
A
and
y
B
. This makes
the procedure susceptible to
man-in-the-middle
attacks, whereby attacker
X
intercepts the messages of
A
and
B
with their public keys
y
A
and
y
B
and replaces
them with falsified messages to
A
and
B
containing his own public key
y
X
.
Then
A
and
B
calculate “secret” keys
s
A
:=
y
x
X
mod
p
and
s
B
:=
y
x
X
mod
p
,
while
X
on his or her part calculates
s
A
from
y
x
X
Z
≡ a
x
A
x
X
≡ a
x
X
x
A
≡ y
x
A
X
≡
A
s
A
mod
p
and
s
B
analogously. The Diffie-Hellman protocol has now been
executed not between
A
and
B
, but between
X
and
A
as well as between
X
and
B
.
Now
X
is in a position to decode messages from
A
or
B
and to replace them by
falsified messages to
A
or
B
. What is fatal is that from a cryptographic point of
view the participants
A
and
B
are clueless as to what has happened.
To compensate for these defects without giving up the advantages, several
variants and extensions have been developed for use in the Internet. They all take
into account the necessity that key information be exchanged in such a way that
4
For the problem of calculating discrete logarithms see [Schn], Section 11.6, as well as [Odly].
