### Thread: Prime numbers generation algorithm

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2011
Posts
3
Rep Power
0

#### 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.
2. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
May 2007
Posts
765
Rep Power
932
If you want to know about openSSL specifically, look at the source (the prime-number 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 N-bit 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
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
191
Rep Power
54
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 Miller-Rabin (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.

• salem agrees
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2011
Posts
3
Rep Power
0
Thanks very much!
5. No Profile Picture
Registered User
Devshed Novice (500 - 999 posts)

Join Date
Dec 2007
Posts
541
Rep Power
0
Let P be the set of prime numbers from 2 to 201. This is trivial to produce, and you can just hard-code 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
6. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
191
Rep Power
54
@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^p-1 (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.