Lower Bound for Primes during GnuPG key generation
vedaal at nym.hush.com
vedaal at nym.hush.com
Fri May 22 18:49:22 CEST 2015
On 5/22/2015 at 12:03 PM, "Daniel Kahn Gillmor" <dkg at 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
More information about the Gnupg-users
mailing list