Cryptography Reference
In-Depth Information
A
B
X
−−−−−−−−−−−−−−−−−−−→
Y
←−−−−−−−−−−−−−−−−−−−
pick
x
at random,
X
←
g
x
g
y
pick
y
at random,
Y
←
Y
x
g
xy
X
y
K
←
(
K
=
)
K
←
Figure 9.3.
The Diffie-Hellman Key Agreement Protocol.
We assume that we have a communication channel between A and B which provides
authentication and integrity protection. If A and B want to communicate confidentially
over an insecure channel, they must agree on a secret key
K
in order to use conventional
cryptography. For this, we assume that we are given a (multiplicatively denoted) group
G
equipped with an efficiently computable group law, but some particular other problem
which will be defined later is hard. In particular, computing discrete logarithms must be
hard. We also assume that we are given an element
g
be an approximation
of log
2
#
G
(for instance, the integer part). Although #
G
(or more precisely the order of
the cyclic subgroup of
G
spanned by
g
) is not necessarily known,
∈
G
. Let
should be public.
The protocol works as follows (see Fig. 9.3).
=
g
x
1. A picks a random integer
x
of
bits, computes
X
in
G
(by using the
square-and-multiply algorithm), and sends
X
to
B
.
2. B picks a random integer
y
of
bits, computes
Y
=
g
y
in
G
(by using the
square-and-multiply algorithm), and sends
Y
to
A
.
3. A computes
K
Y
x
, while B computes
K
X
y
=
=
in
G
.
Note that when a multiple
q
of the order of
g
in
G
is provided, then we can pick
x
and
y
in
. Obviously, if A and B follow the protocol correctly, they end up with
the same key
K
which is
K
{
0
,...,
q
−
1
}
g
xy
. This protocol must also protect the confidentiality
of
K
, and so it should be hard, given
X
and
Y
, to compute
K
=
X
log
g
Y
. This notably
=
implies that computing the discrete logarithm must be hard.
21489151 (although
p
is not large enough
to make the computation of the discrete logarithm hard in
Z
p
). We can pick an arbitrary
g
like
g
As an example, we can take prime
p
=
g
x
=
1609879. Then A picks
x
=
3916708 at random and computes
X
=
mod
p
=
13164781 and sends it to A. Then B picks
y
=
16766518 at random and computes
g
y
X
y
Y
=
mod
p
=
4109137 and sends it to B. In parallel, B computes
K
=
mod
p
=
Y
x
13275737. A can also compute
K
=
mod
p
=
13275737.
We notice that it is important to generate a
g
with a large order. It is quite hard,
in general, to compute the order of an element. (In our example, we can see that
p
−
=
·
·
5
2
·
·
1
2
3
143261 and that
g
has the order 3
143261 “only”.) We can however
,
,
generate an appropriate (
g
q
p
) triplet with a large prime
q
such that
g
has an order
of
q
in
Z
p
by
1. generating a prime
q
,
2. picking
k
at random and
p
=
1
+
kq
until it is prime,
p
−
1
3. picking
g
0
at random and
g
=
g
q
mod
p
until it is not 1.
Search WWH ::
Custom Search