Take the 2-minute tour ×

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.


  • 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?)

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
Also, your algorithmic probability of failure is physically bounded by the failure probability of your hardware, so for instance, a $2^{-512}$ probability of failure is quite overkill. –  Thomas Jul 2 '12 at 0:36
As a confirmation, the certainty in the question is traceable to that in a paragraph just above this, reading: "$\mathtt{certainty }$ - a measure of the uncertainty that the caller is willing to tolerate. The probability that the new BigInteger represents a prime number will exceed $(1-1/{2^{\mathtt{certainty}}})$. The execution time of this constructor is proportional to the value of this parameter." –  fgrieu Jul 2 '12 at 7:37

Your Answer


