4096 bit keys

[Jerome Baum]

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
size/difficulty).

-- 
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/73989bf9/attachment.pgp>