[sowbug]

Not that I worry about this much, but if the fast prime generation methods we use are imperfect, then how bad is it when someone's PGP key or TLS certificate is based on nonprimes? Do black-hats ever strike gold and find out that someone's key is easily factorable? Or is there an additional property of common primality tests that their errors tend to be insignificant? (e.g., yes, this number isn't really prime, but its factors are very likely to be so large that they are also impractical to find, rather than, say, divisible by 7.)

[Someone]

Yes, but not because of the use of non-primes, AFAIK. There also are ‘bad choices’ for the primes that one should avoid.

See https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Faulty_key_..., https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Importance_...

Also, for those that are concerned about doing statistical primality tests, there are fast deterministic tests (https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...). Read https://en.wikipedia.org/wiki/AKS_primality_test for pointers to the algorithms to use in practice.

[schoen]

I think there was some research about this that did find some flawed implementations leading to semiprime p or q, but basically you can choose the probability that a probable prime is actually composite to be low enough that the expected number of weak keys ever generated for this reason is still less than one.

(I haven't personally understood the probabilistic primality tests well enough to understand how they guarantee that the probability of error contributed by each round of the test is completely independent of every other round.)