Lucky's 1024-bit post [was: RE: objectivity and factoring analysis
Nomen Nescio
nobody at dizum.com
Wed May 1 18:20:26 EDT 2002
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
More information about the cryptography
mailing list