🚀 go-pugleaf

  I have been reading this group for a few days now, and I have seen a lot
of stuff about this PGP program. One very important question comes to mind:

How does PGP generate its prime numbers?

I agree that the pseudoprime tests are probably adequate for most use.
However, it is VERY BAD to just choose a large random number and check
that it is prime when using RSA. There are algorithms which can factor
numbers containing certain kinds of primes very quickly. If n=p*q and
either p-1 or q-1 contain no large factors, then n can be factored quickly.
For example, I found primes p=2*29^23+1 and q=some other big prime, and
calculated n=p*q with them. This gave me a number with something like
60 digits or so. I then used the Pollard P-1 algorithm to factor n.
This took less than 10 minutes on my old ATARI 800 !!!!
  Now I know that in practice, p-1 and q-1 will have a factors much bigger
than 29 (I was just testing the algorithm). But if they have no factors
bigger than say 1-100 million, someone with a REAL computer could still
factor n. This will not be the case most of the time, for random primes
of the size being used, but I think it may happen often enough to be
concerned about it. After all we are concerned enough to use RSA, so
we should at least be doing it right. So again: How does PGP get its
prime numbers?

  Paul H. K.
  phkahler@vela.acs.oakland.edu