4096 bit keys

[David Tomaschik]

On Tue, Mar 22, 2011 at 5:14 PM, Mike Acker <Mike_Acker at charter.net> wrote:
> 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?
>
> (I'm not a mathematician)
>
> 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
>
> --
> /MIKE

So, AMD sells Opterons with 12 cores in a single CPU.  It has a street
price of $770.  In 2007, the TILE64 was released (a CPU with 64 cores,
but not x86-compatible).  It's a safe assumption that the NSA *could*
have a NUMA supercomputer or a cluster with 8000+ cores TODAY, but
even with those resources, it's unlikely they could get your key, or
would invest the time to do so.

RSA-768 (a 768-bit modulus) was factored in December 2009, in a
process that took hundreds of computers two years to complete. [1]
The authors of [1] estimate that a 1024-bit RSA modulus would be 1000
times as difficult to factor, but would be achievable in a fashion
similar to theirs within a decade.  That being said, I believe (but
have no solid numbers to back) that 2048 is probably about 1,000,000
TIMES as difficult to factor as RSA-1024.  (I base this on a 1000 time
number from 768 to 1024, and the decreasing incidence of prime numbers
as we get larger values.)

The reality is, for the NSA to even invest the computing time that was
involved in the RSA-768 effort, you'd have to have done (or they would
need to believe that you have done or will do) something REALLY BIG.
Probably on the order of importing CBRN-type weaponry into the US.
And if they believe you're that bad, they will find a way to get at
your key (or rather, your plaintexts).

The ability to "casually" decrypt even 1024-bit keys is nowhere near.
(And by "casually", I mean a difficulty similarly to what it takes to
wiretap a phone.)

[1] http://eprint.iacr.org/2010/006

-- 
David Tomaschik, RHCE, LPIC-1
System Administrator/Open Source Advocate
OpenPGP: 0x5DEA789B
http://systemoverlord.com
david at systemoverlord.com