Lower Bound for Primes during GnuPG key generation

[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 all (never mind actually
being twin primes) is probably equal to about 1 in 2^ 2035 (due to the
birthday paradox).  If my math is wrong, please let me know.

On Fri, May 22, 2015 at 1:34 PM, Daniel Kahn Gillmor <dkg at fifthhorseman.net>
wrote:

> On Fri 2015-05-22 12:49:22 -0400, vedaal at nym.hush.com wrote:
> > On 5/22/2015 at 12:03 PM, "Daniel Kahn Gillmor" <dkg at fifthhorseman.net>
> 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 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, unrelated q?
> >
> > Sorry, I meant does GnuPG automatically reject the PAIR since they are
> > trivial to factor.
>
> there's no risk that GnuPG will choose a Sophie-Germain prime with its
> corresponding safe prime, because as Werner said, it chooses the size of
> the primes (in bits) and then sets the highest bits to 1.  Since the
> sizes are the same, the S-G/safe pair isn't possible (the safe prime is
> always 1 bit longer than the S-G prime).
>
> 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.
>
>              --dkg
>
> _______________________________________________
> Gnupg-users mailing list
> Gnupg-users at gnupg.org
> http://lists.gnupg.org/mailman/listinfo/gnupg-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20150522/411d2c71/attachment.html>