(gcrypt.info.gz) Prime-Number-Generator Subsystem Architecture

Info Catalog

(gcrypt.info.gz) Multi-Precision-Integer Subsystem Architecture

(gcrypt.info.gz) Architecture

(gcrypt.info.gz) Random-Number Subsystem Architecture

 
 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.(1) 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.
 
 
    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
 generation functions: `_gcry_derive_x931_prime' and
 `_gcry_generate_fips186_2_prime'.  These functions are internal and not
 available through the public API.
 
    ---------- Footnotes ----------
 
    (1) Chae Hoon Lim and Pil Joong Lee. A key recovery attack on
 discrete log-based shemes 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.
 

Info Catalog

(gcrypt.info.gz) Multi-Precision-Integer Subsystem Architecture

(gcrypt.info.gz) Architecture

(gcrypt.info.gz) Random-Number Subsystem Architecture