On 5/22/2015 at 3:01 AM, "Werner Koch" <[email protected]> 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 _______________________________________________ Gnupg-users mailing list [email protected] http://lists.gnupg.org/mailman/listinfo/gnupg-users
