Lower Bound for Primes during GnuPG key generation
brian at minton.name
Fri May 22 20:55:19 CEST 2015
There are approximately 2^2038 primes in the 2048-bit space (source,
). 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>
> 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>
> [ 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.
> Gnupg-users mailing list
> Gnupg-users at gnupg.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Gnupg-users