[Top] [All Lists]

Diffie-Hellman vs. ElGamal

1998-04-06 16:57:02
At 7:00 PM -0400 4/3/98, Russ Housley wrote:

1) I know this is a stupid question because this has been accepted as a
given by the WG for quite a bit of time, but why is S/MIME using the
Diffie-Hellman algorithm, which requires a bit of wedging to work as a
store-and-forward key transport algorithm, rather than ElGamal? Note that
this proposal is basically identical to ElGamal, only it uses 3DES and a
checksum instead of modular multiplication and PKCS#1-style padding.

With ElGamal, I do not think that the originator has a static public value
that can be placed in a certificate.  With the proposed variant of
Diffie-Hellman, the originator uses a static component that is included in
a certificate, and therefore, the recipient knows who the other party is
that holds the pariwise key.

Knowing who the other party is does not ensure the entegrity of the
message. If the pairwise key can be validated as correct, all it means is
that the sender sent the recipient a message at some point.

Here's my understanding of the current Diffie-Hellman proposal. Note that
this is all a giant guess based on comments, because I can't find any
description of this in the current CMS draft or the message specification.
Maybe I am actually the first to write this all down in detail.

        Originator (Alice) has a certified Diffie-Hellman public key:
                (p, g, g^x) [the private key is x]

        Recipient 1 (Bob) has a certified Diffie-Hellman key in the same group:
                (p, g, g^y1) [the private key is y1]
        Recipient 2 (Chuck) has a certified Diffie-Hellman key in the same 
                (p, g, g^y2) [the private key is y2]

        Alice generates a random symmetric key K and uses it to encrypt the body
        of the message, m, with a symmetric key, yielding M, the encrypted 
                M = E(m, K)

        Alice generates the following Diffie-Hellman results:
                r1 = (g^y1)^x
                r2 = (g^y2)^x

        Alice uses r1 and r2 to wrap K for the individual recipients using some
        wrapping algorithm W() (Russ's proposal for W involves 3DES):
                w1 = W(K, r1)
                w2 = W(K, r2)

        The message is composed of:
                M, w1, w2
        and appropriate headers and other information for decoding purposes.

        Bob can receive the message by calculating:
                r1 = (g^x)^y1
        (Bob will need Alice's certificate; it can either be sent with the 
        or acquired elsewhere).
        and unwrapping K from w1 using this result:
                K = UW(w1, r1)
        K can then be used to decrypt M.

        Chuck can receive the message in the same fashion.

Here's classic ElGamal:

        Instead of needing a certified public key in the same group as Bob
        and Chuck, Alice generates a temporary public key in the same group
        as the recipient's certified keys:
                (p, g, g^t) [the private key is t]

        Alice then generates K and uses it to encrypt the message as above,
        then generates the r1 and r2 values, only using t instead of x as her
        private key. She then wraps r1 and r2 as above, only modular 
        is used as a wrapping mechanism rather than 3DES.

        The message is composed of:
                M, g^t, w1, w2

        Bob and Chuck can unwrap K and decrypt the message in the same fashion 
        above. Instead of using Alice's certified public key, they use the
        temporary public value sent with the message.

        If Bob and Chuck have certified keys in different groups, Alice need 
        generate a temporary key pair for each recipient group; the rest of the
        algorithm is the same. (They can share the same value of K and thus
        receive the same message, even if they are in different groups).

What are the differences?

        - The only substantial difference is that in ElGamal, the sender uses a
                temporary key, while in my description of Diffie-Hellman, that 
                must be authenticated.
        - In Diffie-Hellman, the sender and all recipients must have keys in the
                same group in order to communicate. In ElGamal, the keys can be 
                any group and the sender need not have a certificate.
        - In Diffie-Hellman, the identity of the sender must be known and 
                in order to correctly unwrap the key K. Let us assume that K 
can be
                validated as correct. However, this does not mean that the 
                encrypted with K, is intact; it could be modified in any number 
                ways. Thus, this cannot serve in place of a signature.
          Because the sending key is temporary in ElGamal, it neither gives this
                benefit nor suffers from this restriction.

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

 - Tim

Tim Dierks - Software Haruspex - tim(_at_)dierks(_dot_)org
 "Well, cyberterrorists may be difficult to capture in the act, but from what I
  know about people who are highly skilled with computers, they should be easy
  to beat up." - Ernest Cey, quoted in The Onion, <>

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