Cryptography Reference
In-Depth Information
The Diffie-Hellman key exchange protocol using
Z
p
.
Protocol 16.4
A
B
(
p, g
)
(
p, g
)
x
a
∈
R
{
0
,...,p−
2
}
x
b
∈
R
{
0
,...,p−
2
}
y
a
≡ g
x
a
(mod
p
)
y
b
≡ g
x
b
(mod
p
)
y
a
−
y
b
←−
K
ab
≡ y
x
a
b
K
ba
≡ y
x
a
(mod
p
)
(mod
p
)
(
K
ab
)
(
K
ba
)
using this group is illustrated in Protocol 16.4. Let
p
be a large prime and
g
be
a generator of
Z
p
. A and B know
p
and
q
, and want to use the Diffie-Hellman
key exchange protocol to agree on a shared secret key
K
. A randomly selects
a private exponent
x
a
∈{
0
,...,p
−
2
}
, computes the corresponding public
g
x
a
(mod
p
), and sends
y
a
to B. B, in turn, randomly selects a
private exponent
x
b
∈{
exponent
y
a
≡
0
,...,p
−
2
}
, computes the corresponding public exponent
g
x
b
(mod
p
), and sends
y
b
to A. A then computes
y
b
≡
y
x
a
b
g
x
b
x
a
(mod
p
)
K
ab
≡
≡
and B computes
y
x
a
≡
g
x
a
x
b
(mod
p
)
.
K
ba
≡
Because the exponents commute,
K
ab
is equal to
K
ba
. It is the output of the
Diffie-Hellman key exchange protocol and can be used as a secret key
K
.
Let us consider two toy examples to illustrate the working principle of the
Diffie-Hellman key exchange protocol:
Z
17
). A randomly selects
x
a
=7,
•
Let
p
=17and
g
=3(i.e.,
g
=3generates
3
7
(mod 17) = 11, and sends the resulting value 11 to B.
B, in turn, randomly selects
x
b
=4, computes
y
b
≡
computes
y
a
≡
3
4
(mod 17) = 13,and
sends the resulting value 13 to A. A now computes
y
x
a
b
13
7
(mod 17) =
≡
4, and B computes
y
x
b
a
11
4
(mod 17) = 4. Consequently,
K
=4is the
shared secret that can be used as a session key.
≡
Z
347
). A randomly
•
Let
p
= 347 and
g
=11(i.e.,
g
=11generates
11
240
selects
x
a
= 240, computes
y
a
≡
(mod 347) = 49, and sends the
