# 4096 bit keys

Robert J. Hansen rjh at sixdemonbag.org
Tue Mar 22 23:18:47 CET 2011

```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

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.

```