14

I am generating a 2048-bit safe prime for a Diffie-Hellman-type key, p such that p and (p-1)/2 are both prime.

How few iterations of Rabin-Miller can I use on both p and (p-1)/2 and still be confident of a cryptographically strong key? In the research I've done I've heard everything from 6 to 64 iterations for 1024-bit ordinary primes, so I'm a little confused at this point. And once that's established, does the number change if you are generating a safe prime rather than an ordinary one?

Computation time is at a premium, so this is a practical question - I'm basically wondering how to find out the lowest possible number of tests I can get away with while at the same time maintaining pretty much guaranteed security.

Improve this question
4
  • @avid, well, as Thomas explains, it is not so much a question of how much checking you need to thwart a clever human attacker, but rather how little you can get away with given other engineering considerations (like cosmic rays or bad memory). So while a broad view of security (including reliability) would include it, that theory could be used to subsume way more of SO than I think people would like.
    – nealmcb
    Jun 13, 2011 at 20:15
  • 1
    @nealmcb but that explanation (that its not a question of security concerns) is a security aspect, that is a crypto explanation and not an engineering one.
    – AviD ♦
    Jun 14, 2011 at 0:38
  • @avid I agree. I just think it also belongs on SO. It needs input from experts from both camps. Unfortunately that doesn't seem to be directly supported by the current SE codebase.
    – nealmcb
    Jun 14, 2011 at 19:58
  • 2
    @nealmcb if you think it should be possible for a question to "straddle" sites, please ask on meta. I think that's an interesting idea.
    – user185
    Jun 15, 2011 at 7:07

3 Answers 3

Reset to default
4

(t = 40) iterations of M-R with randomized bases is completely unnecessary for p(1024, t) < (2^-80). No more than 1/4 of composite odd values are SPRPs to a random base. The ((1/4)^t) is extremely pessimistic, and papers DLP, RBJ (the latter also proving the DLP conjecture: p(k, t) < (1/4)^t, for k >= 2, t >= 1), combine results proving that (t = 3) iterations are sufficient to yield: p(1024, t) < 2^-80. See also: Handbook of Applied Cryptography ch.4, table.4.4. This same (t = 3) value is used for 1024-bit values in the OpenSSL library.

20190202: I've decided to add a link to my own code based on these papers. While the mrtab utility is the key, the LUTs and assertion-testing programs it's built on are all part of the package. I'd always appreciate any feedback on the mrtab project.

Improve this answer
4
  • This has been proven to be wrong by security researchers. The benchmark statistics provided by the Handbook of Applied Cryptography are not a suitable substitution for the theoretical probability originally published for the Miller-Rabin. When the RNG is controlled by an adversary (which is a real world attack), they can choose random numbers that are strong pseudo-prime composites, which forces the theoretical maximum error rate to occur in practice. eprint.iacr.org/2018/749
    – Jared Deckard
    Aug 23, 2018 at 12:51
  • @JaredDeckard - If a RNG is controlled by an adversary! All bets are off in this case - you might as well assume an installed key logger, or 'rubber-hose' cryptanalysis. From a theoretical POV, you're no longer satisfying the cryptographic definition of an unobservable 'random' device with no side-channel leaks. I would not consider the prior results to be 'proven to be wrong' by any stretch - any more than handing your private key over to an adversary invalidates the security of a correctly managed cryptosystem.
    – Brett Hale
    Sep 5, 2018 at 10:32
  • Modern crypto systems minimize the amount of randomness required for common operations due to this very attack. It is practical for an attacker to target the RNG due to it's low chance of detection.
    – Jared Deckard
    Sep 6, 2018 at 13:38
  • @BrettHale That's incorrect. As long as the witness generation is not influenced by the adversary, then even candidate primes generated by a malicious actor can be effectively detected with the M-R tests.
    – forest
    Feb 21, 2019 at 7:02
16

I just answered to the same question on stackoverflow, so I will duplicate my answer here (I don't think duplication is the way to go; maybe the question should be migrated):

Let's assume that you select a prime p by selecting random values until you hit one for which Miller-Rabin says: that one looks like a prime. You use n rounds at most for the Miller-Rabin test. (For a so-called "safe prime", things are are not changed, except that you run two nested tests.)

The probability that a random 1024-bit integer is prime is about 1/900. Now, you do not want to do anything stupid so you generate only odd values (an even 1024-bit integer is guaranteed non-prime), and, more generally, you run the Miller-Rabin test only if the value is not "obviously" non-prime, i.e. can be divided by a small prime. So you end up with trying about 300 values with Miller-Rabin before hitting a prime (on average). When the value is non-prime, Miller-Rabin will detect it with probability 3/4 at each round, so the number of Miller-Rabin rounds you will run on average for a single non-prime value is 1+(1/4)+(1/16)+... = 4/3. For the 300 values, this means about 400 rounds of Miller-Rabin, regardless of what you choose for n.

(Edit: actually, for a randomly chosen non-prime, Miller-Rabin works better than that (see @Brett's answer) and the average number of rounds will be closer to 300 than 400. It does not substantially change my argument.)

So if you select n to be, e.g., 40, then the cost implied by n is less than 10% of the total computational cost. The random prime selection process is dominated by the test on non-primes, which are not impacted by the value of n you choose. I talked here about 1024-bit integers; for bigger numbers the choice of n is even less important since primes become sparser as size increases (for 2048-bit integers, the "10%" above become "5%").

Hence you can choose n=40 and be happy with it (or at least know that reducing n will not buy you much anyway). On the other hand, using a n greater than 40 is meaningless, because this would get you to probabilities lower than the risk of a simple miscomputation. Computers are hardware, they can have random failures. For instance, a primality test function could return "true" for a non-prime value because a cosmic ray (a high-energy particle hurtling through the Universe at high speed) happens to hit just the right transistor at the right time, flipping the return value from 0 ("false") to 1 ("true"). This is very unlikely -- but no less likely than probability 2-80. See this stackoverflow answer for a few more details. The bottom line is that regardless of how you make sure that an integer is prime, you still have an unavoidable probabilistic element, and 40 rounds of Miller-Rabin already give you the best that you can hope for.

To sum up, use 40 rounds.

Improve this answer
2
  • Someone suggested that I migrate it, but I guess I don't know how migration works; would you suggest deleting this copy?
    – jnm2
    Jun 13, 2011 at 12:12
  • Migrating is something moderators do -- the people with a diamond sign right to their name. If they migrate the question from stackoverflow to here, I suggest they scrap this one (which is a duplicate).
    – Thomas Pornin
    Jun 13, 2011 at 12:14
1

The most important factor in speeding up Miller-Rabin is using a simple divisibility test over a set of small primes first, and only resorting to Miller-Rabin if that passes.

If a random k-bit odd integer n is divisible by a small prime, it is less computationally expensive to rule out the candidate n by trial division than by using the Miller-Rabin test. Since the probability that a random integer n has a small prime divisor is relatively large, before applying the Miller-Rabin test, the candidate n should be tested for small divisors below a pre-determined bound B."

http://cacr.uwaterloo.ca/hac/about/chap4.pdf (4.1.1)

Improve this answer
2
  • @brett-hale I removed my comment about your solution. After further reading, the tables for computing (t) were actually independent of factoring by small primes. I don't believe testing divisibility by small primes is a "basic error" though. It is clearly promoted by the "Handbook of Applied Cryptography" and every implementation I have worked with does this first.
    – Jared Deckard
    Jan 18, 2018 at 16:16
  • You're not actually wrong, in that a GCD test with a product of 'small' primes is more computationally efficient to eliminate potential candidates than the M-R test. You can look at Merten's theorem in 4.4.1 - there are 54 primes less than 256, and a GCD test will factor almost 80% of all odd integers. While that's not pertinent to the original question, you are correct about efficiently discarding candidates. That does not address the original question of M-R iterations for candidates that pass however, which is a separate issue here.
    – Brett Hale
    Jan 18, 2018 at 17:05

You must log in to answer this question.

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