Lower Bound for Primes during GnuPG key generation

vedaal at nym.hush.com vedaal at nym.hush.com
Fri May 22 18:49:22 CEST 2015

On 5/22/2015 at 12:03 PM, "Daniel Kahn Gillmor" <dkg at fifthhorseman.net> wrote:

>I think you're calculating the wrong thing.  That same link points 
>that the number of primes less than x can be approximated as
>pi(x) = x/(log(x)-1).
>Very rough approximation below, dealing with this stuff in integer 
>so i
>don't have to worry about floating point precision:
>import math
>def pi(x):
>    return x//(int(math.log(x) - 1))
>print(pi(2**2049) - pi(2**2047))

>That's a lot of primes to choose from! :)


Ouch!    ;-)

my mistake (forgot it's exponential)!

even using the n log(n) calculation,
the interval is:

2^2049 [ 2049 log 2 ]  -  2^2047 [2047 log 2] 

which is an infeasibly large interval to attack this way.


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


>Why should GnuPG reject these primes?  Surely, it wouldn't want to 
>elements of a pair like that (i.e. for RSA you don't want q = p+2
>because it's a trivial test to factor that composite), but is 
>there a
>reason to reject using a p that meets these categories with some 
>unrelated q?

I meant does GnuPG automatically reject the PAIR since they are trivial to factor.



More information about the Gnupg-users mailing list