Lower Bound for Primes during GnuPG key generation

[Werner Koch]

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.


Salam-Shalom,

   Werner

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