4096 bit keys

[Jerome Baum]

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