How exactly are GPG keys mathematically related, and prime numbers inside of GPG general

Question

Before anyone suggest it, I've yet to pick up "Applied Cryptography" I'm planning on picking it up the next time I visit amazon.

I know that the keys are somehow mathematically related, and I know that they're somehow generated via prime numbers, but how exactly are they related? I realize that it'd probably be best for me to go read about it inside of the book, if it has it, but this is something that I've been wondering about for a little while and I figure that this is the perfect site to ask it on.

Also the final keysize, is that the size of the prime number? For example, if I set it to 8192bits does that mean that the prime numbers are that long?

Answer 1

There are several kinds of asymmetric cryptographic algorithms. All use some sort of mathematical structure, but not the same, and not all involve prime integers.

RSA is the most well-known asymmetric algorithm, which includes several variants (e.g. for asymmetric encryption or for digital signature). In a RSA public key, there is a big integer called the modulus, which is the product of two (or more) prime integers; the key size is traditionally the size, in bits, of that modulus. Usually, two prime integers of the same size are used, so for a 8192-bit RSA key, the two primes should have size 4096 or 4097 bits each. (A RSA public key contains more information than just the modulus.)

For the ElGamal asymmetric encryption, there is again a modulus, but this time it is a prime integer, not a product of several primes; the traditional "size" of an ElGamal public key is the size of that prime.

For anything with elliptic curves, there are prime integers at some point, but quite some additional mathematics on top of that.

For the whole mathematical details, have a look at the Handbook of Applied Cryptography, which is downloadable for free. This book contains less smooth talk than Schneier's "Applied Cryptography", but it is also more precise and thorough.

Answer 2

OpenPGP is a protocol that uses various encryption algorithms in it.

For public keys, they're either RSA, DSA, or Elgamal. Note that DSA is signing-only and Elgamal is encryption-only. DSA and Elgamal are variants of Diffie-Hellman and thus their relationship to prime numbers is slightly tangential.

RSA keys are made of (typically) two prime numbers multiplied together. There are three-key variants, and more, but hardly anyone does that.

Typically, each of the primes is half the size of total key. So a 2K-bit key has two 1K-bit numbers multiplied together. Obviously, if you were doing a three-key variant that had three primes each 1K big, then the total thing would be 3K-bits long.

The security of RSA rests on the difficulty of factoring, and I'm sure you will note that a number made of three 1K-bit numbers is not substantially differently secure than one made of two. There are plenty of details to debate on that, but since that wasn't your question, I'm not going to go into that long debate. The major point is that we generally assume that an N-bit RSA key is made up of two primes each N/2 bits long.

By the way, don't make RSA keys over 4K (4096). It's obnoxious. They're big, they're slow. Any signatures you make with them will also be big. A number of implementations won't support them, and people will get irritated with you if your key breaks their software. They'll just not encrypt to you.

RFC 4880 says:

 * OpenPGP does not put limits on the size of public keys.  However,
   larger keys are not necessarily better keys.  Larger keys take
   more computation time to use, and this can quickly become
   impractical.  Different OpenPGP implementations may also use
   different upper bounds for public key sizes, and so care should
   be taken when choosing sizes to maintain interoperability.  As of
   2007 most implementations have an upper bound of 4096 bits.

If you need more security than you'd get from a 3K-bit key, you should strongly consider using elliptic curve keys. A 3K-bit integer key is equivalent to a 256-bit ECC key. If you use the NIST P-384 curve (which has 384-bit keys), then you'll have more security than that 8K-bit RSA key and people will be much happier.

Yeah, I know that as of this writing (summer 2012), that's easier said than done.

Jon