4096 bit keys

[Robert J. Hansen]

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.

> The problem  is the number of divisions you  have to perform O(2^n)
> for RSA-n. Actually it's a lot less, O(2^(n/2)) for the simple fact that
> you have  to divide only up  to the square  root, as one factor  must be
> smaller than  that. But the kind of  magnitude is still the  same and it
> grows pretty fast with key size.

You might want to look into the General Number Field Sieve (GNFS), which
is a much more efficient way of breaking RSA keys than by simple trial
division.