4096 bit keys
jerome at jeromebaum.com
Tue Mar 22 22:50:26 CET 2011
Mike Acker <Mike_Acker at charter.net> writes:
> with chip makers playing with chips having 64 cores printed in silicon...
> someplace i read the ratios on this,-- if you make the key a little
> longer the key gets much harder to break. in public key encryption
> though you have to factor the product of the two large prime numbers --
> which i'm told is no easy task. i've often wondered about this as lists
> of large prime numbers are not hard to come by... so-- start someplace
> and start running divides... trouble is though you can't use the
> hardware instruction set: the numbers are way to large
> what does an x64 chip do? divide a 64 bit integer into a 128 bit
> dividend to yield a 64 but quotient and a 64 bit remainder? dunno but
> you have to do the same thing but using what? a 2048 or 4096 bit dividend?
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. 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.
> what if they put 8192 cores on a chip? who would have such a machine?
> NSA. the smart money would bet they would have it
It's not so much about the number of cores. If you have two cores, that
doesn't account for double the length in the key. The scale is linear
(double the computing power, half the time required to crack), while the
key length scale is exponential (double the length, square the
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
Size: 880 bytes
Desc: not available
More information about the Gnupg-users