Looking for Elgamal sign+encrypt key information

[David Shaw]

On Mon, Mar 15, 2004 at 02:51:54PM -0700, Kurt Fitzner wrote:
> >I wouldn't say that.  I think it's more accurate to say
> >that RSA signatures obsoleted Elgamal signatures.  At the
> >time that Elgamal signatures were added to the OpenPGP
> >standard (and to GnuPG), RSA was patented and could not
> >be freely used.  Now that the RSA patent has expired, there
> >is very little point to Elgamal signatures.
> 
> I had forgotten the RSA patent issue.  Looking at the historical
> perspective, I can better understand why ElGamal was included, even with
> it being a crptographically inferior choice.  My main concern wasn't so
> much to keep the ElGamal signatures in, per se.  As I mentioned in an
> earlier post, I myself use RSA sign+encrypt keys.  My point, though, is
> that I don't consider DSA to have sufficient key sizes.  Quite a few of
> the negative arguments against ElGamal (larger signatures than DSA,
> slower than DSA, etc) also work against RSA.  

Not completely.  DSA isn't always faster than RSA.  In fact, RSA is
considerably faster verifying signatures compared to DSA.  DSA is
only faster generating signatures than RSA.  Since signatures are
usually verified more frequently than they are generated, this is a
net win for RSA.

Still, most of the time this doesn't matter - they're both fast enough
that you'll rarely notice anything in regular use.  Elgamal
signatures, however, are slow enough that even on a fast computer,
you'll see a visible pause as the signature is processed.  That's
slow.

> >I think that while lots of choice is a laudable goal, it has
> >to be balanced - especially in security related programs -
> >with some conservatism as to algorithms.
> 
> I agree.  I suppose I started to see a trend that confused and troubled
> me a little.  First, the ElGamal and RSA sign+encrypt key generation
> options are hidden unless you issue the "--expert" switch.  Then, when
> an implementation flaw is discovered in ElGamal key generation, the
> whole algorithm is disabled.  It's a progression that, to me, seemed to
> be leading to having DSA as the only signing alternative left.  I hope
> (assume) that there are no plans to move away from RSA signing or RSA
> sign+encrypt keys?

No plans.  RSA gives us something that Elgamal doesn't.  It's just
that Elgamal didn't give us something that RSA didn't already give us.
(Plus there was the bug, plus there was the terrible speed issue.)

Note, though, that there is no rule that says that an OpenPGP program
has to support RSA.  The only algorithms that are required are DSA for
signing, Elgamal for public key encryption, SHA1 for hashing, and 3DES
for symmetric encryption.  Everything else, including RSA, is
optional.

> >Note that the upcoming revision to the OpenPGP standard does
> >not include Elgamal signatures.
> 
> That's a very telling point that I wasn't aware of.

Well, to be honest, the standard dropped it after GnuPG dropped it.
Since nobody other than GnuPG supported it in the first place, it was
a pretty clear indication that it wasn't going to be used.

> I still don't know the nuts and bolts of what makes ElGamal signatures
> dangerous to implement.  I can't see how it would be any different than
> RSA.  Hash the message, encrypt the hash with the sender's private key,
> ASCII-fy the result.  How is ElGamal signing any more dangerous than
> ElGamal encrypting?  Like Atom Smasher, I would love if someone could
> offer (or point me to) a dumbed down version for the cryptographically
> challenged.  Simply out of curiosity.

Take a look at some of the links at the end of
http://www.samsimpson.com/cryptography/pgp/pgpfaqnew.html

David