What is the correct value for “certainty” in RSA key pair generation?

Question

I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty. This Stack Overflow answer says it is a relative test for how prime the values are.

There is another answer that says this value should be adjusted relative to the key length.

Question

• What are the correct values for certainty relative to key length (how did you determine this?)

• What does it mean to say "certainty of x bits" of a number? (If it's possible to sub-divide a number and certify bits, which bits are being certified?)

Answer 1

Certainty of $x$ bits means that the probability that something (in this case $p$ being prime) not being true is smaller than $2^{-x}$. This is the same probability as guessing a random $x$-bit value correctly on the first try, hence the name.

How to select $x$? We want the probability of $p$ (and $q$) not being prime to be small enough that a failure probability in this point is not larger than other ways the system could be broken - like guessing a symmetric key, factoring the modulus etc.

So here a correspondence table of symmetric and asymmetric key sizes should help. Pick the same prime certainty as you would pick an symmetric key size accompanying your public key usage.