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.stew...@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.hoff...@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

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 majord...@metzdowd.com

Reply via email to