Version 1.5
This article was posted in article <33A98A97.3FCDE446@mit.edu> to alt.security.pgp on June 19th 1997.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
> The "Faster Key Generation" option, for those who haven't scoured the
> help file looking for information about it, is the default method of
> key generation in the free and commercial versions of PGP 5.0. It
> decreases the time required for key generation from somewhere near an
> hour for a 4096-bit key on a P-166 with 64-MB memory down to a mere
> second or two. How does it do this, you may ask. It uses
> "precalculated prime numbers". Yeah, canned primes. If there were
> ever a scheme to weaken PGP, it would be that; include with PGP a
> fixed number of prime numbers from which users will be randomly
> assigned two at the time of key generation. Customers will be happy
> at their quickly generated keys, and the NSA will be happy with their
> newfound ability of cryptanalysis.
This isn't how it works. A DSS key has four components:
g -- Called the generator. This is the base that other work is done with.
p -- *The* prime field that is used in calculations. Can be 512-1024 bits.
(more then 1024 bits doesn't really yield additional security).
q -- A 160 bit number which is used to reduce the computation (q is
chosen to be the same length as the SHA-1 hash).
x -- Your private key, "x" is the only secret value.
y -- Your public key. It is g^x mod p.
So your public key is the combination of g,p,q and y.
You private key is the combination of g,p,q and x.
PGP 5.0 uses the Elgamal variation on Diffie-Hellman. It has a similar
set of parameters as DSS except there is no "q" value. A PGP 5.0 key
is actually two completely separate keys. A DSS key for signing and an
Elgamal key for encrypting.
PGP supports Elgamal primes of up to 4096 bits.
The time consuming part of key generation is selecting the large prime
"p" (for both DSS and Elgamal). However these are "public" values and
it doesn't really matter if a lot of people use the same p,g (and q
for DSS).
However. The Diffie-Hellman algorithm is "brittle." When you attack a
Diffie-Hellman (or DSS) key, you attack the prime. Specifically you
compute a table of logs that permits you to take a "y" value and lookup
the "x" value (x being the private key). It is also possible to specially
compute a weak "p" value, so it is important that people believe that
the "p" value they are using is secure.
Computing log tables for prime values of 1024 and larger are currently
computationally intractable.
So what does PGP 5.0 to provide for secure prime fields:
Well for starters all of the builtin primes for PGP 5.0 are at least
1536 bits long. In other words if you choose a value of 1024 bits for
your DSS key (recommended) it will be generated at random just for you.
So even if someone, with a *lot* of computer time, can solve the log
table for a 1024 bit prime, they only get one key's worth (this is
similar to a factoring attack on RSA).
However generating a random 2048 bit prime takes a while (not *that*
long), so PGP has a built in value. To ensure that the built in values
are not "trapped", the way they are created will be documented.
I won't go into all the details here, but the gist of it is that a
quote from Ghandi is run through a hash function to create a random
starting point for the search for the primes. One of the Ghandi quotes
used is "Whatever you do will be insignificant, but it is very
important that you do it!"
What this all means is that you can generate a DSS/DH key with a
1024 bit DSS prime and a shared (built in) 2048 bit DH prime in a
very reasonable amount of time.
The downside is that *if* someone can compute a table of logs for the
built in 2048 bit DH prime, they will be able to break everyone's
encryption key that is using that prime. However a 2048 bit prime is
a *very* *very* *very* hard prime to compute the log table of. It is
not likely to happen in my lifetime (or that of my grand kids, at
least not without a mathematical breakthrough that would make this all
moot anyway).
However, if you are concerned, you are welcome to generate your own
DH prime. All you have to do is uncheck the fastkeygen option.
Heck, if you wanted to build a backdoor into PGP there are much better
ways to do it then to use a bad prime (you can test if a prime is
trapped, so any such back door would be findable).
-Jeff
-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv
iQA/AwUBM6mKcPAgc1f0FJUrEQLoCACgqObiYpKf486H6dQWDdNWSsIjPuEAoLKk
wlsGQZf0DT6Vk/ud21vTfY+8
=fPo/
-----END PGP SIGNATURE-----
[ Table of Contents | About this FAQ | Glossary ]