On Tuesday 22 March 2011, Robert J. Hansen wrote: > On 3/22/11 5:50 PM, Jerome Baum wrote: > > Actually none of this is that important. If you can do the > > division in half a second instead of one, that only halves the > > time you need. All I have to do is add one bit to my key size > > and you're back to square one. > > You have to add one bit to your *effective* key size. Remember, the > primes are not evenly distributed: the larger you go, the more they > are spread out. This is why for very small keys each additional bit > gives you quite a lot of security, but as keys grow very large more > and more bits have to be added to get that additional boost. > > As an example, there are 25 primes under 100: of all the possible > values, you have to check 25% of them. But there are only 78,498 > primes under one million: you only have to check 7.9% of those > numbers.
Well, that's only true if you have previously enumerated all primes which is impossible for the bit sizes we are speaking about. So, effectively, the scarcity of primes does not give the attacker any advantage. Regards, Ingo
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users