Is Java's probablePrime used in production?

Question

Prime numbers are core in security.
I saw this question about Java's probablePrime and was wondering if that API/approach is indeed used for real production-ready security code or other approaches are preferred to ensure there is 0 possibility of using a non-prime number

Answer 1

The important part is "The probability that a BigInteger returned by this method is composite does not exceed 2e-100"

Hardware isn't perfectly reliable: https://community.hiveeyes.org/t/soft-errors-caused-by-single-event-upsets-seus/1891

Lets make some assumptions:

• 1 bit flip per day for a machine from cosmic rays
• • You could assume 1 bit flip per year per machine if you prefer - that is a factor of 2^8 in the answer.
• 2^38 bits (16GiB) memory in the machine
• 2^10 bits that flipping would invalidate the "definitely prime function"
• • The result itself (1 bit, but maybe 8 bits if a boolean is returned in a byte, or 32 bits if a boolean is returned in an int32_t) - after running the test, there's likely to be a loop to try another number is the result is composite - but what if the function returns 'composite', but the cosmic ray flips that to 'prime'?
• • The number in memory (2^10 == 1024 == size of the prime used for 2048 bit RSA keys)
• • • I'm assuming the definitely-prime function takes a copy of the number (into registers), so after starting, the original number in main memory could be changed by a bit flip. If this happens the result of the function will be for a different number than is in memory - and since primes are rare in the 2^1024 range, the new number will probably be composite.
• • The code that branches on the result - there is a branch instruction after running after the function (to decide if to try again) - but what if a branch-if-false is changed to a branch-if-true? Or a branch-never? Or changed to look at a different address or register?
• 86400 seconds in a day ~ 2^16 seconds/day

= 2^-38 chance for a bit to flip per day

= 2^-54 chance for a bit to flip per second (divide 2^-38 by 2^16)

= 2^-44 chance for a interesting bit to flip per second (multiply 2^-54 by number of interesting bits)

Therefore a definitely prime algorithm would need to run in 2^-54 seconds (longer than probablePrime) to be as certain as the probablePrime function. That's much less than an instruction (2^-20 seconds?). Otherwise the P(error(probablePrime)) < P(error(definitePrime + bit flips))

We use probablePrime because it's so much faster than definitelyPrime functions, and that makes it more reliable on real computers.

The numbers are far enough apart, that even if we say 1 bit flip in 2^25 seconds (about a year), it's still much less than 1 instruction that we can allow, before the risk of bit-flip is more than the uncertainty from probablePrime.

Answer 2

Java 8's BitInteger Class's

• probablePrime calls
  • largePrime if requested prime has more than SMALL_PRIME_THRESHOLD = 95 bits that calls
    • searchSieve.retrieve, in which a BitSieve (Sieving) is performed before the costly call of
      • primeToCertainty (Rabin-Miller Test with 50 rounds), the probabilistic calculation of the Rabin Miller is given by 4^-k, so the probability is 4^-50=2^-100. In other words, a composite number passes the test with 2^-100 probability.

This probability is very tiny_{tinytinytinytinytiny}

If you want to get a prime with 100% than

1. You can assume that it is prime and use it in the RSA or similar encryption systems so that if the results are not correct, it can indicate there is a problem. Actually, this is still not 100%, see Is there a pseudo message that will encrypt and decrypt correctly if one of the primes is a pseudo prime in RSA. The better one;
2. Use the AKS primality test which is a deterministic primality-proving algorithm. There are improvements over time, however, it is still compared to Rabin Miller.

If 100% is required AKS and its variants are the sole choice.