Prime Generation

[Werner Koch]

Pete Chown <Pete.Chown at skygate.co.uk> writes:

> Currently gpg seems to have a problem getting enough entropy to
> generate a key; this was my reason for looking into it in the first
> place.  When I generated a 2048-bit key, it ran out of entropy several
> times and needed to be restarted by typing on the keyboard.

The prime generation is not the real problem.  For the default
DSA/ElGamal key we don't need at secret prime at all - however we use 
use the random number generator anyway but in a mode which mainly uses
/dev/urandom.  And here is the problem:  When it is time to generate
the secret x, /dev/random cannot deliver entropy because /dev/urandom
has sucked it away. 

So the improvement would be to use a PRNG which does not use so much
stuff from /dev/urandom.  Currently we have 3 grades of random
numbers:

   WEAK   - not cryptograpically secure (I have to check how it is done)
   STRONG - After the inital seed it gets seeded by /dev/urandom, so 
	    that it practically my be a pure PRNG if there is not
            enough entropy in the system.  This is used for session
            keys and k.
   VERY STRONG - Always needs entropy from /dev/random, so it may take
          a while.  It is used for the x of DLP algorithms.

I am currently in the progess of changing the internal API and I may
do some test with the prime generation later.


-- 
Werner Koch at guug.de           www.gnupg.org           keyid 621CC013