🚀 go-pugleaf

Ari Huttunen (Ari.Huttunen@hut.fi) wrote:
: I am concerned about the primeness of the prime numbers
: that PGP generates. This is how they are done:
: 	- first throw away numbers that are divisible
: 	  by small primes
: 	- then use Fermat's theorem 4 times
: 	  (Fermat's theorem:  if  b**(n-1) != 1 (mod n), then
: 	  'n' cannot be a prime. This requires that 'b' and 'n'
: 	  are relatively prime.)
: 
: My concern is the number of rounds of the Fermat test. It's only 4.
: I would not trust this level of primeness. Also, the resulting
: number might be a Carmichael number. (So it would pass any number
: of such tests.) 

Large pseudoprimes (of any base) are very rare indeed.  RSADSI did
some experiments a couple of years ago to search for such numbers, and
found none (this is written up in one of the CRYPTO proceedings).

It is conjectured that the density of base 2 pseudoprimes of this size
is less than 10^-10 (this is from memory, so that figure might be
wrong.)  In any case, it is likely that a composite p or q would cause
messages to not decrypt correctly, a fact that you'd soon notice.

It might be worth using the Miller-Rabin test, in which no analogues
of Carmichael numbers exist, as a backup.  This would be easy to add
to the search procedure, but I don't think that it's really necessary.

Andrew.