Lower Bound for Primes during GnuPG key generation

Daniel Kahn Gillmor dkg at fifthhorseman.net
Fri May 22 19:34:47 CEST 2015

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 948 bytes
Desc: not available
URL: </pipermail/attachments/20150522/a3fb97c3/attachment.sig>

More information about the Gnupg-users mailing list