[Top] [All Lists]

Re: Diffie-Hellman vs. ElGamal

1998-04-07 17:30:51
Tim Dierks <tim(_at_)dierks(_dot_)org>:

- The only substantial difference is that in ElGamal, the sender
  uses a temporary key, while in my description of Diffie-Hellman,
  that key must be authenticated.

The mechanism which Diffie-Hellman described in their famous published
_paper_ involves a "public directory" which contains everyone's
parameters. All users share the same prime and generator.

The _patent_ (which actually lists Diffie, Hellman and Merkle as
inventors; so a more correct name for the cryptographic operation
appears to be Diffie-Hellman-Merkle) does not mention this variant.
It describes Diffie-Hellman exchange (where each side create a
_fresh_ exponent  x_i  and sends  g^x_i  to the other one) and also
includes the scheme which ElGamal encryption is based on: The
recipient's key  y_R = g ^ x_R  is known and fixed, and only the
sender's exponent  x_S  (and thus also the transmitted value  g ^ x_S)
is ephemeral.  The resulting value  K = y_R ^ x_S = (g ^ x_S) ^ x_R
can then be used as a key for some symmetric encryption algorithm
(which, according to the Diffie-Hellman-Merkle patent's text, results
in "authentication" of the recipient -- today we'd call this whole
process "public key encryption").  Typically, you'd select the
lowest 56, 64, 128 or ... bits (as needed) and use them as symmetric
key or -- better -- use a hash of  K.

ElGamal's idea amounts in doing Vernam encryption with key  K
(one might prefer the name "pseudo-Vernam", because  K  is not really
random when all the transmitted values become known; also, possible
valuse for  K  are usually restricted to a _sub_group of  (Z/pZ)*).
Typically Vernam encryption -- the "one-time pad" -- is associated
with XOR, but any finite group works just as well; in the case of
ElGamal, the group is either (Z/pZ)*  or  (Z/pZ),  the former being
more common.

Based on this, I believe ElGamal to be a better alternative than

ElGamal encryption is just a certain application of Diffie-Hellman.
The name "Diffie-Hellman" alone does not reveal how key  K  will
be used later in the protocol. 

<Prev in Thread] Current Thread [Next in Thread>