4096 bit keys

[Ingo Klöcker]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: </pipermail/attachments/20110323/4cf41dfc/attachment.pgp>