Bouncy Castle RSA keypair generation using Lightweight API

Question

Surprisingly enough there's very little information on the Web about using Bouncy Castle's lightweight API. After looking around for a while I was able to put together a basic example:

RSAKeyPairGenerator generator = new RSAKeyPairGenerator();
generator.init(new RSAKeyGenerationParameters
    (
        new BigInteger("10001", 16),//publicExponent
        SecureRandom.getInstance("SHA1PRNG"),//prng
        1024,//strength
        80//certainty
    ));

AsymmetricCipherKeyPair keyPair = generator.generateKeyPair();

I have a basic understanding of RSA and the math that happens behind the scenes, so I understand what publicExponent and strength are. I presume publicExponent refers to a coprime of phi(pq) and from what I gather it can be small (like 3) as long as appropriate padding is used. However, I have no idea what certainty refers to (some place mentioned that it might refer to a percentage but I want to be sure). The use of SecureRandom is self-explanatory. The documentation of RSAKeyGenerationParameters is completely worthless (no surprise there). My only guess is that it has something to do with the accuracy of the generated keys, but again I want to be sure. So my question is what are appropriate values for certainty and publicExponent?

P.S. Please don't reply with "it depends on the context - how secure you want the information to be". It's pretty safe to assume highest degree of security (i.e. 4096-bit RSA key or greater) unless otherwise specified... I would also appreciate links to sources that give good example of the use of Bouncy Castle's Lightweight API (I'm not at all interested in the JCA implementation or any examples pertaining to it).

Answer 1

You are using correct values for both.

The publicExponent should be a Fermat Number. 0x10001 (F4) is current recommended value. 3 (F1) is known to be safe also.

The RSA key generation requires prime numbers. However, it's impossible to generate absolute prime numbers. Like any other crypto libraries, BC uses probable prime numbers. The certainty indicate how certain you want the number to be prime. Anything above 80 will slow down key generation considerably.

Please note that RSA algorithm still works in the unlikely event that the prime number is not true prime because BC checks for relative primeness.

Answer 2

I'd have to delve into their source code to be "certain", but I believe that the certainty parameter is passed straight to the BigInteger constructor, which says, "The probability that the new BigInteger represents a prime number will exceed (1 - 1/2^certainty). The execution time of this constructor is proportional to the value of this parameter."

So, with a value of 80, there is less than 1 chance in 2⁸⁰ that the number will not be prime. The comment suggests that the prime number generation time is linear with respect to this parameter, but you should test that to be sure if you choose to increase it. It might make sense to use a value that is consistent with the key size you are using. For example, NIST says that a 1024-bit RSA key is as strong as an 80-bit symmetric key. For a 2048-bit RSA key, you might want to use a certainty of 112 bits (the equivalent strength symmetric key size), and so on.

It sounds like you are aware of the vulnerability of using 3 as the public exponent in special cases. The value 65537 is used almost universally now.

Answer 3

A good reference is FIPS PUB 186-3. In particular, appendix B section 3 has many security parameters, as well as prime generation algorithms.certainty is the number of iterations of the Miller-Rabin primality test.

Answer 4

See this answer on crypto.stackexchange.com for more information on how your value of certainty should be calculated.

Preview of Paŭlo Ebermann's answer:

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. http://www.keylength.com/ Pick the same prime certainty as you would pick an symmetric key size accompanying your public key usage.