13.5 Prime-Number-Generator Subsystem Architecture

Libgcrypt provides an interface to its prime number generator. These functions make use of the internal prime number generator which is required for the generation for public key key pairs. The plain prime checking function is exported as well.

The generation of random prime numbers is based on the Lim and Lee algorithm to create practically save primes.¹ This algorithm creates a pool of smaller primes, select a few of them to create candidate primes of the form 2 * p_0 * p_1 * ... * p_n + 1, tests the candidate for primality and permutates the pool until a prime has been found. It is possible to clamp one of the small primes to a certain size to help DSA style algorithms. Because most of the small primes in the pool are not used for the resulting prime number, they are saved for later use (see save_pool_prime and get_pool_prime in cipher/primegen.c). The prime generator optionally supports the finding of an appropriate generator.

The primality test works in three steps:

1. The standard sieve algorithm using the primes up to 4999 is used as a quick first check.
2. A Fermat test filters out almost all non-primes.
3. A 5 round Rabin-Miller test is finally used. The first round uses a witness of 2, whereas the next rounds use a random witness.