9
$\begingroup$

Although this has been extensively discussed around here, I'm curious whether my approach makes sense, or I should just stick to "the standard version".

I'm implementing some homomorphic encryption primitives (Paillier, Okamoto–Uchiyama etc) and, at the moment, I'm using GMP as the big number library (this may change in the future). GMP has a function called mpz_nextprime and I generate random numbers, after which I call this function on them, to get prime numbers. Is this a good approach? The other alternative would be to just generate random numbers in a loop, until mpz_probab_prime_p(number, 10) says that they are prime. This latter approach seems rather wasteful though, from a programmer's point of view.

How do you generate prime numbers with GMP or OpenSSL (or other crypto libraries like cryptlib, crypto++, etc)? I am unsure how the mpz_nextprime function works or if other libraries provide such functionality... Ideally, I should be able to just swap various big number libraries in my implementation, without changing the prime generator wrapper.

$\endgroup$
17
$\begingroup$

mpz_nextprime states in the documentation and source (file: mpz/nextprime.c) that it simply finds the next prime larger than the provided input. There are various methods of doing so (depending on how efficient it tries to be), but they should all produce the same answer. Looking at the code, mpz_nextprime first tests a number against a large quantity of small primes to see if they are a factor. If not, mpz_nextprime uses a probabilistic Miller-Rabin test. If the number passes the MR test, it is output as prime; if it doesn't, it is incremented by 2 and tested again. (Like OpenSSL, as mikeazo linked to.)

mpz_nextprime used to use Miller-Rabin with 10 tests, a testing strength that could be argued to be weaker than desired. But looking at the source for the current version (5.0.4) they've changed to use 25 tests, which is sufficiently safe.

Now, regarding the method: A potential problem with generating a random number and then "walking" to the next largest prime is that primes are not evenly distributed, so neither are the gaps between them. If you have consecutive primes $p_i$ and $p_{i+1}$, any randomly generated number between $p_i$ and $p_{i+1}$ would get mapped to $p_{i+1}$. Primes that follow large gaps are more likely to be chosen, and primes that follow smaller gaps would be less likely to be chosen. You would be imposing a non-uniform distribution on your choice of primes. (Read a little more here.)

That isn't necessarily a problem, though, and I can't say I've ever seen serious concern raised over it. OpenSSL probably has sufficient confidence in their method. Although, of course, the "perfect" way to ensure your have a prime number distribution that is even is to just generate random numbers until one of them is prime. Although it is probably a little slower than "increment-and-test" on average, it can't be much slower. One advantage of the increment-and-test method that it is deterministic, since there is guaranteed to be a prime between $p$ and (approximatively) $p + \sqrt(p)$, but given the frequency of primes ($log(p)$), I would think that such weak work limit wouldn't be a concern.

$\endgroup$
  • 1
    $\begingroup$ Now this is a really good answer. Thanks for taking the time to provide such a detailed explanation. It really clarifies the issue. I will probably go with the heuristic method, since it saves me some headache. There shouldn't be any performance concern at the moment, since prime numbers are required only for key generation, which I don't have to perform many times. $\endgroup$ – Mihai Todor May 3 '12 at 21:22
  • 2
    $\begingroup$ Here is an approach to select a random prime nearly free of bias. Say that for some $a,b$ with $2≤a≪b$ we want a random prime $p$ with $a≤p<b$. Pick a random $s$ with $0<s<b-a$ until $\gcd(s,b-a)=1$. Pick a random $t$ with $0≤t<b-a$. Use for $p$ the first prime among the $p_i=(i⋅s+t)\bmod(b-a)+a$. Simple variants can be made to select prime $p$ such that $p-1$ has a big known prime factor $s$, or/and such that $p+1$ has another big known prime factor, see e.g. FIPS 186-4 section B.3.6. $\endgroup$ – fgrieu Mar 24 '14 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.