Introduction to Public-Key Cryptography:The Diffie–Hellman Protocol - Introduction to Cryptography with Maple - page 399

7.2 The Diffie-Hellman Key Agreement

In this section we study the Diffie-Hellman key agreement or Diffie-Hellman pro-
tocol (we will often write DH protocol for short) and its security properties.

7.2.1 The DH Protocol and the DH Problems

The DH protocol may be described as follows. We assume that the parties, Alice and
Bob, have no prior shared information and have access to a channel that provides
authentication and integrity but may otherwise be insecure.

Definition 7.3 Diffie-Hellman key agreement.
As a first step, Alice and Bob agree on a cyclic group G of order t , equipped with
an efficiently computable group law, and also agree on a generator g of G . These
parameters are public and may be generated by one of the parties and sent to the
other through the public channel. Then the protocol runs as follows:
1. Alice chooses x g x ← Z t uniformly at random, computes u = ∈ G and sends

u to Bob.
2. Bob chooses y g y

← Z t uniformly at random, computes v = ∈ G and sends v

to Alice.
3. Alice computes k

v x

= ∈ G .

u y 4. Bob computes k = ∈ G .

After the protocol is run, Alice and Bob agree on using the common key k .The
protocol is correct because v x

g y

x

g xy g x

y

u y and this common value

= ( ) = = ( ) =

is the key k .
The most important question now is whether this protocol is secure. The goal,
according to Definition 7.2 is that an eavesdropper, Eve, cannot distinguish the key
from a random string of the same length. The natural attack that Eve may use to
trytorecover k is to find x (or, alternatively, y ) for then, since v is known, she
just computes k

v x . But computing x given u is just an instance of the discrete
logarithm problem on the group G , so this leads to the requirement that computing
discrete logarithms (see Example 3.2 and the discussion of the algorithms for the DL
problem in Sect. 6.5 ) should be hard for the family of groups considered. In other
words, the family of discrete exponential functions corresponding to these groups
should be one-way in the sense of Definition 3.10 and Example 3.2. Solving the
discrete logarithm problem in G will break the protocol but this is by no means the
only attack conceivable and it is possible that there may be other ways of obtaining
information about the key, or even of recovering k , without finding first x or y . Thus
hardness of the discrete logarithm problem is only a necessary condition for the
security of the protocol.
The possibility of recovering the key without computing discrete logarithms leads
by abstraction to the following problem:

=