Cryptography Reference
In-Depth Information
Alice
Bob
a
b
g
a
(mod
p
)
g
b
(mod
p
)
(
g
b
)
a
=
g
ab
(
g
a
)
b
=
g
ab
Figure 9.10.
Diffie-Hellman protocol
any new public-key cryptosystems to describe the most common instantiation
of the Diffie-Hellman protocol. This is because the ElGamal cryptosystem (see
Section 5.3) has precisely the property that we need. Equally fortunately, the
required function
F
is very simple.
Just as explained in Section 5.3.4 for ElGamal, we can choose two public system-
wide parameters:
• a large prime
p
, typically 1024 bits in length;
• a special number
g
(a primitive element).
The Diffie-Hellman protocol is shown in Figure 9.10 and proceeds as follows.
Note that all calculations are performedmodulo
p
and thus we omit mod
p
in each
computation for convenience. For a reminder of the basic rules of exponentiation,
see Section 1.6.1.
1. Alice randomly generates a positive integer
a
and calculates
g
a
. This is,
effectively, a temporary ElGamal key pair. Alice sends her public key
g
a
to Bob.
2. Bob randomly generates a positive integer
b
and calculates
g
b
. Bob sends his
public key
g
b
to Alice.
3. Alice uses
g
b
and her private key
a
to compute (
g
b
)
a
.
4. Bob uses
g
a
and his private key
b
to compute (
g
a
)
b
.
5. The special combination function property that we need is that raising a number
to the power
a
and then raising the result to the power
b
is the same as raising
the number to the power
b
and then raising the result to the power
a
, which
means that:
(
g
a
)
b
(
g
b
)
a
g
ab
=
=
.
So Alice and Bob have ended upwith the same value at the end of this protocol.
There are several important issues to note:
1. It is widely believed that the shared value
Z
AB
=
g
ab
cannot be computed by
anyone who does not know either
a
or
b
. An attacker who is monitoring the
communication channel only sees
g
a
and
g
b
. Recall from Section 5.3.3 that
