Lower Bound for Primes during GnuPG key generation

vedaal at nym.hush.com vedaal at nym.hush.com
Fri May 22 17:38:36 CEST 2015


On 5/22/2015 at 3:01 AM, "Werner Koch" <wk at gnupg.org> wrote:

>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.

=====

Approximately what interval is meant by 'primes of the same size' ?

i.e. for a 4096 RSA key the interval would be  [ 2^(2048 + k) - 2^(2048 - k) ]

What would the range of k be?


n.b.

Any interval of primes can be approximated by:

n(U)[log(n(U))] - n(L)[log(n(L))]

where U is the uppermost prime, and L is the lowermost prime

https://primes.utm.edu/howmany.html   (The Prime Number Theorem, Consequence Two: The nth prime is about n log n )


So, to give a trivial example,  If the interval of primes chosen is from  2^2047 to 2^2049, then this interval is only

log(2) [ 2049^2 - 2047^2]  = 5678      which is a fairly small number of primes to check, for this type of attack to find the GnuPG keypair.


Also,
does GnuPG automatically reject twin primes ( p, p+2) ,  and Sophie-Germain primes (p, 2p+1) ?



TIA,

vedaal




More information about the Gnupg-users mailing list