Lower Bound for Primes during GnuPG key generation
vedaal at nym.hush.com
vedaal at nym.hush.com
Fri May 22 17:38:36 CEST 2015
On 5/22/2015 at 3:01 AM, "Werner Koch" <wk at gnupg.org> 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 interval is meant by 'primes of the same size' ?
i.e. for a 4096 RSA key the interval would be [ 2^(2048 + k) - 2^(2048 - k) ]
What would the range of k be?
n.b.
Any interval of primes can be approximated by:
n(U)[log(n(U))] - n(L)[log(n(L))]
where U is the uppermost prime, and L is the lowermost prime
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 is only
log(2) [ 2049^2 - 2047^2] = 5678 which is a fairly small number of primes to check, for this type of attack to find the GnuPG keypair.
Also,
does GnuPG automatically reject twin primes ( p, p+2) , and Sophie-Germain primes (p, 2p+1) ?
TIA,
vedaal
More information about the Gnupg-users
mailing list