confused about public key strength

[Robert J. Hansen]

Matt Kinni wrote:
> Hello, I can't seam to figure out how the different bitstrengh of my
> public key effects anything.  If someone encrypts something to my
> private key, isn't the strength of the private key that matters?

No.  Asymmetric cryptography has keys that come in public and private
parts, but that doesn't mean the parts can be evaluated in isolation.
It's a system.

> So I have a 1024bit DSA pub and 4096 elgamal key.  Isn't the lengh of
> the elgamal key what determines how strong the file is encrypted?

No.  The file is encrypted with a symmetric cipher depending on the
preferences of you and your respondent.  This is anywhere between an
effective keystrength of 112 bits (3DES, under a ridiculously
pessimistic set of assumptions) all the way up to 256 bits.

This is, by the way, a _lot_ of protection against cryptanalysis.  Any
talk about breaking this by brute force is deluded fantasy.  It's not
happening, not even with quantum computers and every other staple of the
science fiction literature that people assume the NSA has access to.

The key used to encrypt the file is chosen at random.  You could sit
there with a quarter, toss it 256 times, and have a perfectly good AES
key.  The computer does basically this process.  This random,
one-time-use key is then encrypted with your recipient's public key.

The recipient's public key may be anywhere from 1024 bits up to 4096
bits.  Don't be confused by comparing this to the 112- to 256-bit
symmetric encryption of the file.  It's an apples to oranges comparison:
you cannot say "well, one has 1024-bit encryption and one uses 256-bit,
so clearly one is four times better than the other."

> What does the size of the public key even matter?

For 99% of users, it doesn't.  Use the defaults GnuPG gives you --
they're good defaults.