Re: Lower Bound for Primes during GnuPG key generation
On Fri, 22 May 2015 19:34, d...@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 failure. 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. Salam-Shalom, Werner -- Die Gedanken sind frei. Ausnahmen regelt ein Bundesgesetz. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Lower Bound for Primes during GnuPG key generation
On Thu, 21 May 2015 23:14, ved...@nym.hush.com said: When GnuPG creates and RSA keypair, is there a minimum *low* for primes it will ignore? 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. The primality test works in three steps: 1. The standard sieve algorithm using the primes up to 4999 is used as a quick first check. 2. A Fermat test filters out almost all non-primes. 3. A 5 round Rabin-Miller test is finally used. The first round uses a witness of 2, whereas the next rounds use a random witness. Note that for Elgamal and DSA keys we generate the public prime using Lim and Lee's algorithm. Salam-Shalom, Werner -- Die Gedanken sind frei. Ausnahmen regelt ein Bundesgesetz. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Lower Bound for Primes during GnuPG key generation
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
Re: Lower Bound for Primes during GnuPG key generation
On 5/22/2015 at 3:01 AM, Werner Koch w...@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 ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Lower Bound for Primes during GnuPG key generation
On 5/22/2015 at 12:03 PM, Daniel Kahn Gillmor d...@fifthhorseman.net wrote: 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: 3414566770186655994404438379880237752289275853601443153843712876451 7106455003913618433496010529759521130797881149503110281852350331307 6748346315130154722343603670415899310676791001520948946303896102170 4767238030738398330774862856393736234748500545533360423420463740160 3112241209544524188755360669738591593193745235562705749858506233297 2052480087122621997414717056433422819795492200612038244015831024661 0014630770483358467188964179436800746042429708401186006929782110316 9614694882157095281778056383498229906388753003349920901696154376284 3548757751395862879269607910869512589725531458623570829193465282940 49800053111 That's a lot of primes to choose from! :) - Ouch!;-) my mistake (forgot it's exponential)! even using the n log(n) calculation, the interval is: 2^2049 [ 2049 log 2 ] - 2^2047 [2047 log 2] which is an infeasibly large interval to attack this way. = 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. Thanks, vedaal ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Lower Bound for Primes during GnuPG key generation
There are approximately 2^2038 primes in the 2048-bit space (source, https://www.wolframalpha.com/input/?i=log2%282**2049%2Fln%282**2049%29+-+2**2047%2Fln%282**2047%29+%29 ). Even allowing that the first bit is 1, that makes 2^2037. Given that, the chance of p and q having a difference of 2, at all (never mind actually being twin primes) is probably equal to about 1 in 2^ 2035 (due to the birthday paradox). If my math is wrong, please let me know. On Fri, May 22, 2015 at 1:34 PM, Daniel Kahn Gillmor d...@fifthhorseman.net wrote: On Fri 2015-05-22 12:49:22 -0400, ved...@nym.hush.com wrote: On 5/22/2015 at 12:03 PM, Daniel Kahn Gillmor d...@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. --dkg ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Lower Bound for Primes during GnuPG key generation
On Fri 2015-05-22 12:49:22 -0400, ved...@nym.hush.com wrote: On 5/22/2015 at 12:03 PM, Daniel Kahn Gillmor d...@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. --dkg signature.asc Description: PGP signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Lower Bound for Primes during GnuPG key generation (was Re: [Enigmail] Popescu and keys)
On 5/21/2015 at 3:45 PM, Werner Koch w...@gnupg.org wrote: Some guy downloaded most RSA keys from a keyserver and tried to factor 1.9 million moduli. They found 30 keys with a subkey having one of the first 1000 primes as a factor. I looked at 8 of those keys and found that 2 are likely PGP created and 6 are by GPG. = When GnuPG creates and RSA keypair, is there a minimum *low* for primes it will ignore? (i.e. Will GnuPG reject a prime for key generation if it is one of the first 1000 primes, or first million primes, or any fixed lower level?) And if so, Is it feasible to mount an attack on a keypair by starting with trying successive primes greater than this lower bound, and possibly successfully find *some* GnuPG secret keys? TIA, vedaal ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
