Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
June 13th, 2011, 10:44 AM
 gil_mo
Registered User

Join Date: Jun 2011
Posts: 3
Time spent in forums: 1 h 2 m 18 sec
Reputation 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
June 14th, 2011, 07:10 AM
 OmegaZero
Contributing User

Join Date: May 2007
Posts: 756
Time spent in forums: 3 Weeks 6 Days 9 h 49 sec
Reputation Power: 928
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
__________________
sub{*{\$::{\$_}}{CODE}==\$_[0]&& print for(%:: )}->(\&Meh);

#3
June 14th, 2011, 11:55 AM
 mah\$us
Contributing User

Join Date: Feb 2009
Posts: 188
Time spent in forums: 3 Days 5 h 46 m 15 sec
Reputation Power: 49
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
June 14th, 2011, 03:18 PM
 gil_mo
Registered User

Join Date: Jun 2011
Posts: 3
Time spent in forums: 1 h 2 m 18 sec
Reputation Power: 0
Thanks very much!

#5
June 14th, 2011, 03:30 PM
 rdunne
Registered User

Join Date: Dec 2007
Posts: 529
Time spent in forums: 5 Days 21 h 49 m 50 sec
Reputation 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
June 15th, 2011, 12:33 AM
 mah\$us
Contributing User

Join Date: Feb 2009
Posts: 188
Time spent in forums: 3 Days 5 h 46 m 15 sec
Reputation Power: 49
@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.

Quote:
 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.

 Viewing: Dev Shed Forums > System Administration > Security and Cryptography > Prime numbers generation algorithm