June 13th, 2011, 09:44 AM

Prime numbers generation algorithm
Hi,
What is the algorithm / formula used to generate large primes in OpenSSL (or in any other PKI package)?
Thanks,
Gil.
June 14th, 2011, 06:10 AM

If you want to know about openSSL specifically, look at the source (the primenumber generation example is probably a good place to start).
In general, a common method is:
* Generate a chunk of random bits
* Set the most and least significant bits to one (forcing the value to be an Nbit odd number)
* Perform any easy prime tests (e.g. you can test for a multiple of 3 just by adding up the bytes)
* Perform probabilistic primality tests
sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}>(\&Meh);
June 14th, 2011, 10:55 AM

This OpenSSL man page: BN_generate_prime (3) is surprisingly informative.
Most public key software packages will do the following steps:
1) Generate a "random" odd integer of the required size (number of bits). The randomness (unpredictability) must be quite good, for the result to be cryptographically secure. The generation of cryptographically strong randoms is a quite complex problem of its own.
2) Perform trial divisions by a list of primes, in order to throw away odd numbers that have very small factors.
3) If the previous step is passed, run a probabilistic test for primality. The usual test is MillerRabin (you can find plenty about this online), because there are no composite numbers that will always pass this test.
4) If the odd number fails the probabilistic test, either go back to step 1, or increase the number by 2 and go back to step 2. For the size of numbers typically used in PKC, a few hundred iterations are usually necessary.
5) When the test has passed, the resulting number might be called a prime, but is technically pseudoprime. Because the test is probabilistic, the number is probably prime, and the probability is usually very close to 1  but the possibility remains it may be composite.
For cryptosystems based on the Discrete Logarithm Problem, it is usually preferred to use a "safe prime" of the form 2p+1 where p is also prime (in math parlance, Sophie Germaine prime). The generation procedure must of course be altered to ensure this condition.
Comments on this post
June 14th, 2011, 02:18 PM

June 14th, 2011, 02:30 PM

Let P be the set of prime numbers from 2 to 201. This is trivial to produce, and you can just hardcode it.
Since x is prime for any 2^x  1 which is also prime, it also follows that 2^x  1 is prime for a prime x. Simply choose randomly from P and compute 2^x  1 and you got a prime number. This produces really large prime numbers, but not all prime numbers that there are.
This is the simplest method, but is limited. I assume you're not programming something where security is an issue of national security
June 14th, 2011, 11:33 PM

@rdunne:
You seem to be interested in math, so I hope you will welcome some correction.
1. Knowing that p > q (if p is true, then q must also be true) does not tell us whether q > p. Sometimes it works both ways, but usually not. In mathematics, to prove p <> q (in other words, p > q AND q > p), the two propositions MUST be proved separately.
Since x is prime for any 2^x  1 which is also prime, it also follows that 2^x  1 is prime for a prime x.
In fact, no: it doesn't follow. By way of proof, 2^11 − 1 = 2047 = 23 X 89
2. Primes of the form 2^p1 (where p is a prime) are called Mersenne primes, and are an interesting study  in fact, their study goes back to ancient Greece. But for cryptographic systems like RSA in which primes are secrets, Mersenne primes are useless: less than 50 are known, and only 6 of those are near the sizes usually needed in crypto. Mighty easy to guess! (But sometimes, crypto needs primes that aren't secret, where this is not a consideration.)
Where secret primes are needed, it is necessary to start with randomly chosen integers of the required size, and then test them (as described above). There are more than 10^150 primes whose length is 512 bits (a common size for primes in cryptography). When one of these is selected at random, guessing which one (of the 10^150) is of course not feasible.