ietf-openpgp
[Top] [All Lists]

Re: Elgamal != DH

1997-09-13 08:39:46
Hal Finney <hal(_at_)rain(_dot_)org>:

In the past, Adam and I have discussed the question of how proper it is
to refer to ElGamal as a variant of Diffie-Hellman.  This is an issue of
terminology and people may differ in their preferred usage.

In my opinion, DH strictly refers to a key exchange algorithm which
requires messages to flow both ways,

In the scheme presented in the Diffie-Hellman journal paper, _all_ the
public parameters  y_user (= g^x_user MOD p)  are stored in a public
directory (and everybody uses the same prime and generator).  The
secret value  y_Alice ^ x_Bob = y_Bob ^ x_Alice  (mod p), which is
known only to Alice and Bob and can be used as a symmetric key, is
thus fixed, and no messages at all (not counting access to the public
directory) have to flow to compute it.

The patent (R.I.P.), which lists Diffie, Hellman and Merkle as
inventors, describes the exchange algorithm where all x's and y's are
ephemeral.  I think the text also mentions the variant where the
recipient's parameters are fixed and only the sender creates new
values (like in ElGamal-encryption), but this is described as a means
to obtain "authentication": The sender can be sure that only the
intended recipient, and no "man in the middle", can compute the
symmetric key y^x.  (This use of the word "authentication" may appear
a little strange today, but of course all the literature about public
key cryptography, digital signatures etc. did not yet exist then, so
Diffie et al. can't be blamed.)

ElGamal added the idea to use the symmetric key  k = y^x MOD p
directly for Vernam encryption.  (Vernam encryption can be done in any
finite group, not just in ({0,1}^n, XOR).  ElGamal's paper proposes
the groups ((Z/pZ)*, *) and (Z/pZ, +).)

Collecting all those names, ElGamal's encryption algorithm could be
called the Diffie-Hellman-Merkle-Vernam-ElGamal algorithm.
If that appears too long, "ElGamal encryption" is probably most
appropriate.  This naming, however, leads to a new risk: It might
suggest that ElGamal _encryption_ and the ElGamal _signature_ scheme
are basically the same thing (like RSA encryption and RSA signatures
are), while in fact they are two different algorithms.  E.g.,
PGP Inc.'s "Cryptography Reference Chart" (August 1997) claims that
the ElGamal scheme can be "used both for digital signatures and
encryption". But that's not true: ElGamal published _two_ schemes
(both of which use Diffie-Hellman parameters): one for encryption (the
"Diffie-Hellman-Merkle-Vernam-ElGamal" algorithm), and one for
signatures; the latter being the major contribution of his paper.


Bodo Moeller
<Bodo_Moeller(_at_)public(_dot_)uni-hamburg(_dot_)de>

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