Question about how RSA keys are generated in GnuPG

[Werner Koch]

On Sun, 29 Apr 2012 04:08, papillion at gmail.com said:

> This is a stupid question I'm sure but I can't seem to find an answer
> to it in the source code so I thought I'd ask here. When GnuPG is

Tou need to look into Libgcrypt.  From its manual:

The generation of random prime numbers is based on the Lim and Lee
algorithm to create practically save primes. at footnote{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.}
This algorithm creates a pool of smaller primes, select a few of them
to create candidate primes of the form @math{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 @code{save_pool_prime} and
@code{get_pool_prime} in @file{cipher/primegen.c}).  The prime
generator optionally supports the finding of an appropriate generator.


Shalom-Salam,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.