Lower Bound for Primes during GnuPG key generation

Werner Koch wk at gnupg.org
Sat May 23 11:25:33 CEST 2015

On Fri, 22 May 2015 19:34, dkg at 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 than the chance of a hardware

IIRC, by the time the RSA patent expired many cryptographers didn't
anymore suggest the use of special primes because their advantage are
seen as mostly theoretical.  The Lim and Lee algorithm for constructing
safe primes requires the creation of several smaller primes.  This puts
more sensitive data into the memory and the unused smaller primes are
better discarded after the selection of the two final primes.  This
would be a waste of resources and thus I used a straightforward method
for the (secret) RSA primes.



Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

More information about the Gnupg-users mailing list