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.5
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
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:
To support the generation of RSA and DSA keys in FIPS mode according
to X9.31 and FIPS 186-2, Libgcrypt implements two additional prime
_gcry_generate_fips186_2_prime. These functions are internal
and not available through the public API.
Chae Hoon Lim and Pil Joong Lee. A key recovery attack on discrete log-based schemes using a prime order subgroup. In Burton S. Kaliski Jr., editor, Advances in Cryptology: Crypto ’97, pages 249Â-263, Berlin / Heidelberg / New York, 1997. Springer-Verlag. Described on page 260.