4096 bit keys
Jerome Baum
jerome at jeromebaum.com
Tue Mar 22 23:28:31 CET 2011
"Robert J. Hansen" <rjh at sixdemonbag.org> writes:
> 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.
Yeah, sorry. They go up with O(log(n)) where n is the number, or
something like it, right? In any case the point remains -- I have to add
"a few bits" while you have to figure out a whole new means of division
that is much faster.
>> 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.
That's why I said "actually it's a lot less, ... for the simple fact
that ..." -- my point remains, the kind of magnitude is still the same
and it grows pretty fast with key size. GNFS is also exponential in some
multiple of the key size, at least IIRC.
--
PGP: A0E4 B2D4 94E6 20EE 85BA E45B 63E4 2BD8 C58C 753A
PGP: 2C23 EBFF DF1A 840D 2351 F5F5 F25B A03F 2152 36DA
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 880 bytes
Desc: not available
URL: </pipermail/attachments/20110322/31ef2a17/attachment.pgp>
More information about the Gnupg-users
mailing list