4

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

7
  • 1
    Normally, before calling the Rabin-Miller probabilistic primality test, one should test the GCD with the multiples of the first 1000 primes. GCD calculation is much faster than Rabin-Miller. Also, after the prime probabilistic generation, one can test it with AKS. AKS is very slow, however, you will need that at most one + negligible.
    – kelalaka
    Commented Aug 21, 2020 at 20:04
  • @kelalaka: One should test the GCD with the multiples of the first 1000 primes are you talking about verifying that a number is prime or attempting multiples of primes until you hit a prime?
    – Jim
    Commented Aug 21, 2020 at 21:23
  • I thought optimized Sieve would be used and if GCD is 1 why would one do also the Rabin-Miller test?
    – Jim
    Commented Aug 22, 2020 at 11:57
  • You should definitely study the number of primes, The Fundamental Theorem of Arithmetic, The limitation of classic Sieve.
    – kelalaka
    Commented Aug 22, 2020 at 20:21
  • 1
    I'd say that the possible lack of side channel protection is more of an issue. If anything, it is at least not specified in the API that it needs to be side channel resistant. There are plenty of hardware devices that explicitly require you to run RSA key pair generation in a secure environment (rather than being certified itself). It's yet one other reason why Elliptic Curves are often preferred in embedded devices. Commented Aug 25, 2020 at 8:14

2 Answers 2

5

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.

12
  • 1 bit flip per day for a machine from cosmic rays you take this is a given while there is a a (low) probability assigned to it (based on the link) that you shared. May be I am not properly getting some parts of the derivation but then wouldn't this imply that TCP would spend all its time just resending packets due to bad checksum?
    – Jim
    Commented Aug 21, 2020 at 15:17
  • You are right - there is a range given by the different links, but it seemed like an easy number to use. It doesn't change much to assume 1 bit flip per year per computer. (about 2^8). One instruction is maybe 2^-20 seconds, so there's plenty of room in my estimates. Commented Aug 21, 2020 at 15:23
  • Wouldn't using a definitePrime function and immediate primality test solve this?
    – Jim
    Commented Aug 21, 2020 at 16:04
  • Excellent answer. Security’s greatest challenge is helping people to understand when “good enough” is better than “impenetrable”, especially when impenetrable is an impossible to achieve goal. Security, like science, asymptomatically approaches perfection/truth, it doesn’t ensure perfection or truth. Whether it’s securing a stored credit card, stopping a car thief, or guaranteeing primality, it’s always a question of “does the cost outweigh the value of the goods protected?” Too many people miss that cost side of the equation believing they have infinite resources to protect a finite thing. Commented Aug 21, 2020 at 17:23
  • The answer is interesting, I am trying to understand it a bit better. 1) 2^10 bits that flipping would invalidate the "definitely prime function" where is this based on? 2) Would it be possible to elaborate a bit on how the probabilities are derived? I think 2^-38 chance for a bit to flip per day is just 1 out of 2^38 bits (16GiB) mentioned but I am not sure I follow the rest (bit rusty on probs). 3) If I get you correctly probablePrime runs so faster that it eliminates the possibility of corruption due to memory flip? But it still has a degree of error regardless no?
    – Jim
    Commented Aug 21, 2020 at 21:20
4

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 tinytinytinytinytinytiny

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.

0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .