Lucky's 1024-bit post [was: RE: objectivity and factoring analysis

[Nomen Nescio]

Wei Dai writes:
> Using a factor base size of 10^9, in the relationship finding phase you
> would have to check the smoothness of 2^89 numbers, each around 46 bits
> long. (See Frog3's analysis posted at
> http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01833.html.  
> Those numbers look correct to me.)  If you assume a chip that can check
> one number per microsecond, you would need 10^13 chips to be able to
> complete the relationship finding phase in 4 months. Even at one dollar
> per chip this would cost ten trillion dollars (approximately the U.S. 
> GDP).

This is probably not the right way to approach the problem.  Bernstein's
relation-finding proposal to directly use ECM on each value, while
asymptotically superior to conventional sieving, is unlikely to be
cost-effective for 1024 bit keys.  Better to extrapolate from the recent
sieving results.

http://citeseer.nj.nec.com/cavallar00factorization.html is the paper
from Eurocrypt 2000 describing the first 512 bit RSA factorization.
The relation-finding phase took about 8000 MIPS years.  Based on the
conventional asymptotic formula, doing the work for a 1024 bit key
should take about 10^7 times as long or 80 billion MIPS years.

For about $200 you can buy a 1000 MIPS CPU, and the memory needed for
sieving is probably another couple of hundred dollars.  So call it $500
to get a computer that can sieve 1000 MIPS years in a year.

If we are willing to take one year to generate the relations then
($500 / 1000) x 8 x 10^10 is $40 billion dollars, used to buy
approximately 80 million cpu+memory combinations.  This will generate
the relations to break a 1024 bit key in a year.  If you need it in less
time you can spend proportionately more.  A $400 billion dollare machine
could generate the relations in about a month.  This would be about 20%
of the current annual U.S. federal government budget.

However if you were limited to a $1 billion budget as the matrix
solver estimate assumed, the machine would take 40 years to generate
the relations.

> BTW, if we assume one watt per chip, the machine would consume 87 trillion
> kWh of eletricity per year. The U.S. electricity production was only 3.678 
> trillion kWh in 1999.

The $40 billion, 1-year sieving machine draws on the order of 10 watts
per CPU so would draw about 800 megawatts in total, adequately supplied
by a dedicated nuclear reactor.

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