Questions about generating keys

[David Shaw]

On Thu, Aug 23, 2007 at 05:11:35AM +0300, Oskar L. wrote:

> Ok, so RSA isn't always significantly faster, as I thought it was. I had
> read somewhere that it was, (probably on this list) and my own testing
> with my 4GB backup files showed RSA to be notably faster.

Make sure you're comparing apples to apples here.  If you're comparing
RSA to DSA, you need to measure signature speed.  If you want to
compare RSA encryption speed, you need to compare it against an
encryption algorithm like Elgamal.  DSA doesn't encrypt.

> So would it be fair to sum up the differences like this:
> - for signing DSA is faster, for verification RSA is faster,
>   but there's not much of a difference.

There is a substantial difference, but no real difference in practice
for most uses of OpenPGP.  (I could make up a case where it might make
a difference, but it would be an odd, clearly invented, case).

> - OpenPGP implementations must support DSA, but supporting RSA
>   is optional, but both gpg and PGP support RSA, so there's
>   not much of a differance.

Yes.

> - original DSA limited to 1024 bit keys and 160 bit hashes.

Yes.

> - DSA signatures are smaller.

Yes.  DSA signatures are relative to the size of the hash used.  RSA
signatures are relative to the size of the key.

> - updated DSA, aka "DSA2", equal to RSA when it comes to the
>   lenghts of keys and hashes.

Not exactly equal, but roughly equal.  The largest DSA2 key that GPG
will generate is a 3072 bit key that uses a 256-bit hash.  The largest
RSA key that GPG will generate is 4092 bits long.  3072/256 is roughly
balanced in strength (that is, the key and the hash are about the same
strength).  4096, the RSA limit, isn't felt to be significantly
stronger than 3072 (the next step after 3072 is actually 7680 in the
NIST key management publication 800-57).

> - RSA has a hash firewall

Yes.

> If there are no other significant differences that I have missed, since I
> want a key larger that 1024 bits, it must be a DSA2 or RSA key. RSA gets a
> minus for not being required by OpenPGP, but only a small one since it is
> supported anyway. DSA2 gets minus points both for lack of support in older
> versions of PGP, and for lack of a hash firewall. RSA still seems better
> to me, but not by as much as I previously thought.

It's important to note that we're talking about tiny fiddling details
here.  Either path is so vastly stronger than is usually needed that
this is rather like discussing whether a 1001-foot fence is better
than a 1000-foot fence: sure, 1001 sounds better, but if you have an
attacker that could get over a 1000 foot fence, it's safe to assume
they can make a pretty good crack at the remaining foot.

If you're really worried about people with older software not being
able to use your key, that's a strong reason to not choose DSA2.  In
that case, I'd make a RSA primary key, an encryption subkey of
whatever algorithm you like, and then a DSA subkey that you actually
use to sign with.  Do avoid signing documents with a big RSA key.
It's really annoying to the recipient.

> So they accepted RSA into the standard, while it was still restricted by
> patents, as long as it wasn't made the default? I took for granted that an
> open standard like OpenPGP would not have accepted any patented stuff into
> the standard, and that RSA was added later, after the patents ran out. I'm
> a bit sad to find out I was wrong, I was under the impression that OpenPGP
> only allowed completely free and open algorithms.

It's way more complex than that (both for OpenPGP and other IETF
specs).  Check out the significant number of patent-related documents
on the IETF website.  There are (at least) two full RFCs on this topic
alone.

Remember also that before OpenPGP was OpenPGP, it was just PGP: a good
bit of the OpenPGP standard was "standardized" before the IETF was
brought in.  Again, historical and occasional legal issues that aren't
really relevant any longer.

David