I was reading this question about generating primes for RSA keys. The answers point out that most implementations of of the algorithm use probabilistic prime-ness checking algorithms. The answer by @tylerl made the most sense to me:
That is, if the test uses a randomly-chosen value (the "witness") which serves as the basis for the test. If the test passes, then the number is probably prime, but possibly not. We can repeat the same test with a new "witness", and if the test passes again then we have increased our certainty. We can continue to re-test as many times as we want until we've reached the level of certainty that we need.
This (and the other answers) heavily imply that we're never actually 100% certain that the numbers we've chosen for a key are actually prime.
Do any implementations follow up the probabilistic prime checks with exhaustive checks? I'm guessing not, because RSA key generation has to be pretty fast (compared to the heat death of the universe) to be useful.
What "level of certainty" do we "need" for RSA keys?
Is this an actual downside? If a non-prime number is used in an RSA key, to what degree would the search space of a brute force attack be decreased?
I'm torn on this, because as I understand it, a brute force attack relies on factoring the key, which is difficult for the length of numbers we've chosen. If we're 99.99...% certain a number is prime, then the most likely thing we've done is selected a number that's a product of two or more reasonably large primes. That would imply that the brute force attack is only a few orders of magnitude easier to conduct; according to some fancy math, the RSA algorithm has orders of magnitude to spare.
Are there better attacks that will succeed in much less time that could work by assuming one or both of the secret numbers are non-prime? Even if this is one-in-a-billion chance, if the attack is fast enough, it seems like its worth it.