2048-bit RSA keys

[Joseph Ashwood]

FAIR DISCLOSURE: I am the inventor of some of the technology quoted, 
specifically US Patant Application 20090094406. And just to plug myself even 
more, yes the technology is for sale.

--------------------------------------------------
From: "Bill Stewart" <bill.stewart at pobox.com>
Subject: Re: 2048-bit RSA keys

> At 01:54 PM 8/16/2010, Perry E. Metzger wrote:
>>On Mon, 16 Aug 2010 12:42:41 -0700 Paul Hoffman
>><paul.hoffman at vpnc.org> wrote:
>> > At 11:35 AM +1000 8/16/10, Arash Partow wrote:
>> > >Just out of curiosity, assuming the optimal use of today's best of
>> > >breed factoring algorithms - will there be enough energy in our
>> > >solar system to factorize a 2048-bit RSA integer?
>> >
>> > We have no idea. The methods used to factor number continue to
>> > slowly get better,[...]
>>
>>He asked about "today's best of breed algorithms", not future ones. In
>>that context, and assuming today's most energy efficient processors
>>rather than theoretical future processors, the question has a concrete
>>answer.
>
> With today's best-of-breed algorithms and hardware designs,
> there isn't enough money in the economy to build a machine
> that comes close to making a scratch in the surface of
> that kind of energy consumption, whether for factoring or
> for simple destruction.

I'm not so convinced. Since we're discussing cost it makes sense to look at 
the cost based structure from http://www.rsa.com/rsalabs/node.asp?id=2088.

The storage required for 2048 is approximately 2^64 bytes, this is usually 
cited as the limitation. Considering technologies like US Patent Application 
20090094406 (mass quantities of Flash at better than DRAM speed), this is 
actually an achievable capacity with more speed than any current cpu can 
handle (2^64 storage could operate at up to millions of TB/sec). The cost is 
very signficant, from http://www.dramexchange.com/#flash, the best price per 
capacity is 32Gbit Flash, this is 2^32 bytes, so 2^32 such chips are 
required, session average of $6.99 each, this is "only" 2^32*6.99 about $30 
billion. Adding in the cost for the glue logic needed to build the 
20090094406 adds less than 10% to the cost, so its still under $35billion. 
Its worth noting that since we're talking about disk access protocols, the 
systems in place already handle addresses longer than 64-bits, so there are 
no redesign costs on the processors from this. So the cost resulting from 
the storage requirement for 2048 bit factoring is only about $35 billion.

If, as the page suggests, the storage is still truly the dominant cost 
factor 2048 is bordering on within reach for high value targets. 
Fortunately, this does not appear to be the case, storage jumped ahead of 
computation.

The computation cost is not as clear to me, I didn't invent the technologies 
so I'm not as intimately familiar. Computation costs are given by "A 
Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths" at 9 x 
10^15 times more complex than a 512-bit factoring, but does not immediately 
appear to offer good cost estimates, a few quick searches foun RSA-155 took 
about 8400 MIPS*years. Wikipedia gives a number of 147600 MIPS for an Intel 
Core i7. Intel gives prices at $560 per cpu 
(http://www.intel.com/buy/desktop/boxed-processor/embedded.htm?sSKU=BX80601940). 
Assuming a full year is an acceptable time frame the 2048 factoring would 
require 5.1*10^14 processors, costing, well bluntly, a crapload, or about 
$285,600,000,000,000,000.

I'm sure in such volume the price for the cpus could be brought down 
significantly, and other cpus may be more cost efficient.

Considering that google gives a number of $14.59 trillion, the purchase 
would require nearly 20,000 years of US GDP.

So unless someone can bring the computation cost down significantly (very 
possible, since I used a very brute force method) it seems unlikely that 
2048-bit numbers can be factord any time soon.

The most important part though is that the cost structure has changed 
signficantly. A few years ago the dominant cost was the storage, this has 
changed significantly.
            Joe 

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com