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
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.
More information about the Gnupg-users
mailing list