On Fri 2015-05-22 11:38:36 -0400, ved...@nym.hush.com wrote: > 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.
I think you're calculating the wrong thing. That same link points out that the number of primes less than x can be approximated as pi(x) = x/(log(x)-1). Very rough approximation below, dealing with this stuff in integer so i don't have to worry about floating point precision: ------------- #!/usr/bin/python import math def pi(x): return x//(int(math.log(x) - 1)) print(pi(2**2049) - pi(2**2047)) ------------- Produces: 34145667701866559944044383798802377522892758536014431538437128764517106455003913618433496010529759521130797881149503110281852350331307674834631513015472234360367041589931067679100152094894630389610217047672380307383983307748628563937362347485005455333604234204637401603112241209544524188755360669738591593193745235562705749858506233297205248008712262199741471705643342281979549220061203824401583102466100146307704833584671889641794368007460424297084011860069297821103169614694882157095281778056383498229906388753003349920901696154376284354875775139586287926960791086951258972553145862357082919346528294049800053111 That's a lot of primes to choose from! :) > 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? --dkg _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users