Lower Bound for Primes during GnuPG key generation

Werner Koch wk at gnupg.org
Fri May 22 08:59:10 CEST 2015

On Thu, 21 May 2015 23:14, vedaal at nym.hush.com said:

> When GnuPG creates and RSA keypair, is there a minimum *low* for
> primes it will ignore?

Yes.  If you create an RSA key you generate two primes of the same size.
Libgcrypt as well as GnuPG 1.4 will only consider candidates with the
two high bits set so that the final modulus will have the exact size.
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.

Note that for Elgamal and DSA keys we generate the public prime using
Lim and Lee's algorithm.



Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

More information about the Gnupg-users mailing list