Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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