Re: Lower Bound for Primes during GnuPG key generation

2015-05-23 Thread Werner Koch
On Fri, 22 May 2015 19:34, d...@fifthhorseman.net said: > That leaves the twin prime case. I don't know whether GnuPG rejects > that selection, but the chance of stumbling into a twin prime pair > during random prime selection seems staggeringly low to me. No, it does not. And yes, it is lower

Re: Lower Bound for Primes during GnuPG key generation

2015-05-22 Thread Brian Minton
There are approximately 2^2038 primes in the 2048-bit space (source, https://www.wolframalpha.com/input/?i=log2%282**2049%2Fln%282**2049%29+-+2**2047%2Fln%282**2047%29+%29 ). Even allowing that the first bit is 1, that makes 2^2037. Given that, the chance of p and q having a difference of 2, at

Re: Lower Bound for Primes during GnuPG key generation

2015-05-22 Thread Daniel Kahn Gillmor
On Fri 2015-05-22 12:49:22 -0400, ved...@nym.hush.com wrote: > On 5/22/2015 at 12:03 PM, "Daniel Kahn Gillmor" > wrote: [ vedaal wrote: ] >>> does GnuPG automatically reject twin primes ( p, p+2) , and >>> Sophie-Germain primes (p, 2p+1) ? > >> Why should GnuPG reject these primes? Surely, it w

Re: Lower Bound for Primes during GnuPG key generation

2015-05-22 Thread vedaal
On 5/22/2015 at 12:03 PM, "Daniel Kahn Gillmor" wrote: >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

Re: Lower Bound for Primes during GnuPG key generation

2015-05-22 Thread Daniel Kahn Gillmor
On Fri 2015-05-22 11:38:36 -0400, ved...@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

Re: Lower Bound for Primes during GnuPG key generation

2015-05-22 Thread vedaal
On 5/22/2015 at 3:01 AM, "Werner Koch" 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 int

Re: Lower Bound for Primes during GnuPG key generation

2015-05-22 Thread Werner Koch
On Thu, 21 May 2015 23:14, ved...@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

Lower Bound for Primes during GnuPG key generation (was Re: [Enigmail] Popescu and keys)

2015-05-21 Thread vedaal
On 5/21/2015 at 3:45 PM, "Werner Koch" wrote: >Some guy >downloaded most RSA keys from a keyserver and tried to factor 1.9 >million moduli. They found 30 keys with a subkey having one of the >first 1000 primes as a factor. > I looked at 8 of those keys and > found that 2 are likely PGP create