2
$\begingroup$

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

|improve this question|||||
$\endgroup$
4
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Jul 2 '12 at 0:36
  • $\begingroup$ 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." $\endgroup$ – fgrieu Jul 2 '12 at 7:37
  • $\begingroup$ Anybody, please, in English? $\endgroup$ – Jin Kwon Sep 7 '16 at 12:36
  • $\begingroup$ @JinKwon I think we wrote this in English, could you please tell us more exactly about your problem? $\endgroup$ – Paŭlo Ebermann Sep 8 '16 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.