Cryptography Reference
In-Depth Information
Value
s
serves Alice and Bob as their shared session key. Though Mallory can
learn the values of
p
,
g
,
X
, and
Y
, to obtain key
s
, however, he has to compute
the discrete logarithm, i.e., he has to determine
x
from remainder
g
x
mod
p
.
As we know from Section 4.5.4, this is a hard mathematical problem and at
least as difficult as factoring. To ensure that the Diffie - Hellman key exchange
is secure, (
p
−
1)/2 should also be a prime number.
This method is related to the asymmetric ciphering method of ElGamal. It is
special because there is no secret key that has to be permanently protected
against unauthorized access. Only when the keys are passed on are
x
and
y
secret; once Alice and Bob have obtained
s
from
x
and
y
, they can delete
x
and
y
. At the end of their ciphered communication,
s
is also destroyed.
This is an interesting advantage over asymmetric encryption. An attacker can
only try to compute discrete logarithms in arrears, i.e., frontally approach the
mathematical problem — and that's beyond his means for the time being. He
cannot steal a private key in arrears.
The drawback of the Diffie - Hellman key exchange in the form introduced
is that session keys have to be exchanged in pairs. With encrypted messages
to be broadcast to, say, 100 people, this can become pretty costly! Moreover,
Alice and Bob both have to become active before they can communicate. Alice
cannot leave an encrypted mail for Bob while he happens to be on vacation
(and then go on a trip herself).
This drawback can be removed as follows: Bob can send his value
Y
to Alice
and then go on his trip. Alice would choose a different
x
for every message
sent to Bob and send the public key
X
together with her message. This method
is more elegant.
Finally, a small modification helps to enable communication between many
conversers without the need for prior interaction. To this end, the public keys
(
X, Y, . . .
) are stored in a generally available database. The protocol then looks
like this:
1. Every participant chooses a random
w<p
and deposits the remainder,
g
w
mod
p
, in a public database. They each keep number
w
to themselves
and protect it against unauthorized access.
2. Alice fetches Bob's key
Y
from the database.
3. Alice selects a random
x<p
and uses it to compute
X
g
x
mod
p
.
(She could take her
X
from the public database, but our variant is more
secure.) She then computes the session key,
s
=
Y
x
=
mod
p
.
