Cryptography Reference
In-Depth Information
Example 4.3
Suppose that the parameters are
p
= 1187
,
α
=2
,
x
= 285
, and
y
= 781
.Then
X
2
285
2
781
7 (mod
p
)
;
Y
x
7
285
≡
≡
1013 (mod
p
)
;
Y
≡
≡
≡
≡
870 (mod
p
)
; and
X
y
1013
781
≡
≡
870 (mod
p
)
.Hence,
k
= 870
is the shared
secret key.
Analysis
In the Di8e-Hellman protocol,
k
is the shared secret key independently
generated by both Alice and Bob. The key exchange is complete, since Alice
and Bob are in agreement on
k
. The Di8e-Hellman Protocol differs from the
Pohlig-Hellman cipher in that the latter requires that both
p
and
e
be kept
secret since
d
could be deduced from them, whereas in the former
p
and
α
may
be made public due to the intractability of the DLP. However, there is a subtler
problem here that we need to discuss, not only in reference to the above, but
also for later use (see page 186).
A cryptanalyst, Eve, listening to the channel would know
p
,
α
,
X
, and
Y
,
but neither
x
nor
y
. Thus, Eve faces what is called the
Di$e-Hellman Problem (DHP)
:
find
α
xy
(mod
p
) given
α, α
x
(mod
p
) and,
α
y
(mod
p
) (but not
x
or
y
)
.
If Eve can solve the DLP, then she can clearly solve the DHP. Whether the
converse is true or not is unknown. In other words, it is not known if it is possible
for a cryptanalyst to solve the DHP without solving the DLP. Nevertheless, the
consensus is that the two problems are equivalent. Thus, for practical purposes,
one may assume that the Di8e-Hellman Key Exchange Protocol is secure as
long as the DLP is intractable.
Given that we have discussed the achievements of one of the developers of
this algorithm, it is now time to talk about the other.
Bailey Whitfield Di
8
e was born on June 5, 1944. Di
8
e, by his own admis-
sion, was not a good student in high school, but it was not for lack of ability,
rather lack of focus. His ability did shine brightly when his less-than-stellar high
school performance was overshadowed by his strikingly high marks on entrance
examinations for MIT. He entered MIT in 1961 and graduated in 1965, later
accepting a job at Mitre Corporation. There he worked under the tutelage of
Ronald Silver, (one of the authors of the algorithm we describe on page 530).
He worked on development of the mathematical symbolic manipulation package
Mathlab
, which later developed into the powerful symbolic mathematical soft-
ware package called
MACSYMA
. Silver taught Di8e a great deal and inspired
him to look further into cryptographic issues. In 1969, Di8e left Mitre and
joined John McCarthy's Artificial Intelligence Lab at Stanford. By 1975, as
described on page 99, the collaboration with Hellman, with input from Merkle,
created the breakthrough. For his involvement, along with Hellman and Merkle,
Search WWH ::
Custom Search