Bouncy Castle RSA keypair generation using Lightweight API?

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.

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.

– Jherico Jun 21 '10 at 18:50 Relative primeness can be checked easily by calculating GCD. If it's 1, 2 numbers are relative prime. – ZZ Coder Jun 21 '10 at 19:10 It is not impossible to generate provably prime integers, but it is more expensive and considered unnecessary for RSA.

Ueli Maurer gave a fast algorithm for this many years ago. – GregS Jun 22 '10 at 0:33 Also, are you sure the algorithm still works in case a non-prime 'prime' is generated? I've not checked it myself.

BC checks for relative primeness to (p-1)(q-1), but if, say, p is not prime then (p-1)(q-1) is not the correct value for phi(n), so the math breaks down. – GregS Jun 22 '10 at 0:36 Running RSA is a kind of convoluted probalistic primality testing on the involved numbers. If p is non-prime then RSA will fail on many inputs -- but we are talking about a p which just passed a test designed to make non-prime fail with high probability.

– Thomas Pornin Jun 22 '10 at 11:22.

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/2certainty). 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 280 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.

The "vulnerabilities" of 3 as public exponent are mostly a big, historical misunderstanding. 65537 is a prime example of cargo cult in computer science. 65537 is not bad, but 3 is not worse either; if 3 leads to weaknesses then you are doing something else wrong, and using 65537 instead would probably not save you.

– Thomas Pornin Jun 22 '10 at 11:20 @Thomas: In regard to setting the value of the public exponent to 65537, I suspected as much. It could also be greater then 65537, right? Any prime will do?

– Andrey Jun 22 '10 at 14:43 1 @yamsha: the public exponent can be any value which is relatively prime to p-1 and q-1 (where p and q are the prime factors of the RSA modulus). The RSA key generator uses the provided public exponent as parameter, and selects appropriate p and q. This rules out even values.

Any odd integer (except 1) can be used as public exponent; using a prime only makes it slightly simpler for the key generator. The cost of public key operations raises with the size of the public exponent, so you probably want to keep it small. – Thomas Pornin Jun 22 '10 at 18:15 1 @yamsha: also, some widely deployed RSA implementations have trouble with large public exponent.

For instance, the standard RSA implementation in Windows (used when Internet Explorer connects to a HTTPS Web site) does not tolerate public exponents which do not fit in a 32-bit unsigned integer. Using e=3 or e=65537 works "everywhere". – Thomas Pornin Jun 22 '10 at 18:17.

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.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.