1

Can you use BigInteger.isProbablePrime() to generate cryptographically secure primes? What certainty is necessary for them to be "secure"?

Puzzler3141
  • 1,682
  • 2
  • 14
  • 21

3 Answers3

5

I do not hold a degree in crypto, so take this with a grain of salt.

You have two major areas of concern here:

  1. Your primes need to be unpredictably random. This means that you need to use a source such as SecureRandom to generate your primes. No matter how sure of your primality, if they are predictable, the entire cryptosystem fails to meet its goal. If you are using the BigInteger(int bitLength, int certainty, Random rnd) constructor, you can pass in your SecureRandom as it subclasses Random.

  2. Your potential primes need to be reasonably certain of being primes (I'm assuming that you are using an algorithm that relies on the hardness of factoring). If you get a probable prime, but an attacker can, with a good probability, factor it within 5 minutes because it had a factor that never got noticed by the primality test you ran, you are somewhat out of luck with your algorithm. Rabin-Miller is generally used, and this answer states that a certainty of 15 is sufficient for 32-bit integers. A value up to 40 is recommended, and anything beyond that is meaningless.

Community
  • 1
  • 1
nanofarad
  • 40,330
  • 4
  • 86
  • 117
  • 1
    The Rabin-Miller test is generally considered outdated. Most applications now use some sort of Lucas pseudoprime test, for instance a Baillie-Wagstaff test or a BPSW test using the Frobenius variant of Lucas pseudoprimes. Besides being faster than a Miller-Rabin test to a large number of bases, these tests are also less likely to err; in fact, there are no known counterexamples even to the simple Baillie-Wagstaff test, much less the stronger variants. Mathematica, for instance, does trial division to a thousand, strong pseudoprime tests to bases 2 and 3, and a strong Lucas pseudoprime test. – user448810 Apr 18 '14 at 00:51
  • @user448810 Thanks for the heads-up, the OP will appreciate that added tid-bit. – nanofarad Apr 18 '14 at 01:01
  • @user448810 - The MR test is not considered 'outdated', and in fact very few applications use the Lucas and/or BPSW test. Most cryptographic packages still use the MR test, as it's relatively simple to implement, well-understood, and doesn't require the complexity of a recursive Jacobi symbol evaluation. An overwhelming majority of composites will fail a single MR test, so it is typically faster for randomized or incremental prime searches, as the frequency of primes decreases. – Brett Hale Apr 24 '14 at 08:48
  • 1
    @BrettHale: Yes, some cryptographic packages still use MR, because it is sufficient for their needs, and because MR is built-in if you're using GMP or BigInteger for the arithmetic. But some sort of BPSW is now standard among mathematicians. Note that BPSW shares with MR the quick return on composites, since it starts with a strong pseudoprime test. Note also that a single strong-pseudoprime test followed by some kind of Lucas test is faster than 15 strong-pseudoprime tests, so BPSW is faster than MR for primes. And I've never heard anyone say that calculating a Jacobi symbol is complex. ;) – user448810 Apr 24 '14 at 13:10
  • @user448810 - and this highlights the difference between mathematical theory, and cryptographic requirements, with due consideration for complexity, footprint, side-channel analysis, etc. It's possible you know more about this than the authors of GMP, or the various SSL / crypto libraries - but it's also possible they have good reasons for their decisions. – Brett Hale Apr 25 '14 at 03:28
  • @user448810 One important property of MR is that it guarantees to detect non primes with a probability of at least 3/4 for each base you test. So for 64 tests, you're guaranteed that the probability of looking at a prime is at most 2^{-128}. In particular this works even for adversarially selected composites. For primes used in RSA this isn't an issue, but in other contexts it might matter. – CodesInChaos Apr 27 '14 at 16:45
4

this is the way i generated a secure BigInteger for my cryptographic application.

Here's my code:

        BigInteger b = new BigInteger(25, new SecureRandom());

Since you also need it for a crypto application, in my opinion, getting a BigInteger is this way is right. Note: Remember that SecureRandom objects are preformance-wise costly. So You should not initialize them many times.

After reading comments, it worked out further Here's a way which assures you more certainity of getting a prime number.

 BigInteger b =BigInteger.probablePrime(25, new SecureRandom(););
maxx777
  • 1,320
  • 1
  • 20
  • 37
  • 2
    This is *not* a prime. I would add how you address the probabilistic behavior of the BigInteger primality test. – nanofarad Apr 17 '14 at 22:15
  • @hexafraction well, i have edited my response. This code gives much more probability of getting a prime number. If it is good enough, you may remove your downvote. – maxx777 Apr 17 '14 at 22:27
  • What downvote? Your post has 3 up and 0 down. I gave an upvote for that, though. – nanofarad Apr 17 '14 at 22:35
  • 1
    @hexafraction lol.. tahnks for the upvote. When i saw there were only two upvotes instead of three and my repo points were less. So ithought, you being more experinced and with a better answer had downvoted me. Thanks for the knowledge as well – maxx777 Apr 17 '14 at 22:37
1

As @hexafraction says, you need to use SecureRandom() to generate a cryptographic quality random number. The Javadoc says that the generated prime is 2^-100 secure. If you want more security (say to 2^-128 for AES equivalent security) then run more iterations of the Miller-Rabin test on it. Each iteration gives you an extra 2^-2 security, so fourteen iterations would get you to 2^-128.

rossum
  • 15,344
  • 1
  • 24
  • 38