# Why does openssl BN_generate_prime return only a fraction of the safe primes within the given bit range?

I went into prime generation issues the last week and eventually calculated 10^7 primes using erik tews safeprimegen python wrapper for openssl. (https://github.com/eriktews/gensafeprime) (System: MacOS 10.8.4 / openSSL 0.9.8x)

10^7 openssl BN_generate_prime(32) -> 32bit safe primes -> safeprimes.txt

Then i used R to get some information on this data:

1343370 (13.4%) unique primes (within the 10^7 gathered numbers)

2^32 < 3221226167 < 1343370 safe primes < 4294967087 < 2^32

(range of p is roughly : 2^31 *1.5 < s-p < 2^32 -209 (second half of the 32bit range)

For comparison i did generate all 32bit primes using a prime sieve algorithm.

2*31 < p < 2*32

total 98182656 primes thereof 3059799 safe primes

safe primes in range of openssl output:
3221226167 < 1506677 safe primes < 4294967087

openssl safe primes / safe primes in range: 1343370 / 1506677 -> ~ 89.1 % of safe primes in range

(I did repeat this for 31bit safe prime generation and got almost the same proportions.)

Findings:

1. the openSSL output covered only about half of all safe primes in the given range (2^32 -> 3059799)
2. also within the range of the returns only 90% of the safe primes available where reported

I would be interested to understand why openSSL safe prime return is restricted in such way and if this is considered an optimal result having in mind the crypto functions included in the library that rely on the safe prime generator.

Oh, why 96.2%, you ask? It has to do with the coupon collector's problem. If you have $n$ different objects, and you randomly draw $n$ times (sampling with replacement), you don't expect to observe all possible objects. Instead, some objects will have been chosen multiple times, and some will have been chosen only a few times. In your case, there are apparently 3059799 different safe primes (objects). You draw $10^7$ times (with replacement). What fraction of safe primes will be missed? Well, let's fix a single safe prime. The probability that it is missed on any one draw is $1-1/3059799$. The draws are independent, so the probability that it is missed on all of the draws is $(1-1/3059799)^{10^7}$, which is approximately $0.038$. In other words, we'd expect that a $0.038$ fraction of safe primes will never have been output by OpenSSL, in your experiment, assuming OpenSSL samples uniformly at random from all possible safe primes. This corresponds to covering 96.2% of the safe primes during the $10^7$ draws you did.
Another possible explanation for your observed data is that maybe OpenSSL does not choose uniformly at random from all possible safe primes in that range; maybe some safe primes are slightly more likely to be chosen than others. For instance, one possible method for generating a prime number at random is to select an integer $m$ at random, test if it is prime; if not, test $m+1$ for primality; if that's not prime, test $m+2$; and so on, continuing until you find a number that is prime. This procedure does not generate the uniform distribution on primes of a certain size: primes that are preceeded by a large gap (a long stretch of composite numbers) will be more likely to be drawn than others, and primes $p$ where $p-2$ is also prime will be less likely to be chosen. It is possible that OpenSSL is using some sort of random prime generation strategy like this. If it is, then this affects the coupon collector's calculation, and we'd expect to see somewhat more repeats. So, your observed numbers are consistent with this hypothesis. If this is how OpenSSL is generating primes, it is a deviation from the uniform distribution on safe primes, but this deviation is not believed to cause any security problems. The number of possible safe primes is still ginormous (the entropy of the distribution is still plenty large), so there's no known way to take advantage of any non-uniformity that results.