How many iterations of Rabin-Miller should I use for cryptographic safe primes?

user_521757 0
Viewed 12862

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.

primes cryptography
8 Answers

I would run two or three iterations of Miller-Rabin (i.e., strong Fermat probable prime) tests, making sure that one of the bases is 2.

Then I would run a strong Lucas probable prime test, choosing D, P, and Q with the method described here: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test

There are no known composites that pass this combination of Fermat and Lucas tests.

This is much faster than doing 40 Rabin-Miller iterations. In addition, as was pointed out by Pomerance, Selfridge, and Wagstaff in https://math.dartmouth.edu/~carlp/PDF/paper25.pdf, there are diminishing returns with multiple Fermat tests: if N is a pseudoprime to one base, then it is more likely than the average number to be a pseudoprime to other bases. That's why, for example, we see so many psp's base 2 are also psp's base 3.

user_112449470

A smaller probability is usually better, but I would take the actual probability value with a grain of salt. Albrecht et al Prime and Prejudice: Primality Testing Under Adversarial Conditions break a number of prime-testing routines in cryptographic libraries. In one example, the published probability is 1/2^80, but the number they construct is declared prime 1 time out of 16.

In several other examples, their number passes 100% of the time.

user_112449470

Only 2 iterations, assuming 2^-80 as a negligibly probability.

From (Alfred. J. Menezes. et al. 1996) §4.4 p.148:

enter image description here

user_40868710
Related