Lower Bound for Primes during GnuPG key generation
Daniel Kahn Gillmor
dkg at fifthhorseman.net
Fri May 22 18:03:09 CEST 2015
On Fri 2015-05-22 11:38:36 -0400, vedaal at nym.hush.com wrote:
> 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.
I think you're calculating the wrong thing. That same link points out
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:
return x//(int(math.log(x) - 1))
print(pi(2**2049) - pi(2**2047))
That's a lot of primes to choose from! :)
> 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 both
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 other,
More information about the Gnupg-users