Question about how RSA keys are generated in GnuPG

Anthony Papillon papillion at
Sun Apr 29 13:02:17 CEST 2012

Thank you sir!


Sent from my mobile device

On Apr 29, 2012, at 4:12 AM, Werner Koch <wk at> wrote:

> On Sun, 29 Apr 2012 04:08, papillion at 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.

More information about the Gnupg-users mailing list