Hacker News Reader

Hacker News

Comment by philipn | Hacker News Reader

Parent Full thread

philipn

If you're curious (as I was) about the estimated cost of breaking RSA-1024 check out this paper:

http://tau.ac.il/~tromer/papers/cbtwirl.pdf

tl;dr - estimate is ~$10M

View on HN

Note that this is $10M _per RSA-2014 key_, whereas the hypothetical quantum computer can crack all of them.

No, it's $10MM per key/year. Or, it was, back in 2001.

Is it really $10M per key? DJB points out that if you're willing to spend a lot of money building parallel hardware, you can get some surprising performance benefits allowing you to crack large numbers of keys at once.

http://cr.yp.to/snuffle/bruteforce-20050425.pdf‎

That paper does not apply to integer factorization, and number field sieve computations in general. DJB himself, in another paper [1, §5], argues that is more cost effective to factor one number at a time.

[1] http://eprint.iacr.org/2012/318

Per that paper, it would be $10M per 'device', with one device managing one key per year. Of course you might as well build more hardware while you are at it.

I'm not sure about that; the paper talks about parallel machines that can search out many keys at once. Its focus is on known plaintext attacks against AES, but it seems like the techniques described could apply to IFP for RSA.

I'm not a cryptographer so I could be totally off base here.

I only had time to skim it, so you might be right. Either way, I think it is only safe to operate with the assumption that 1024bit keys are well within the grasp of projects with modest funding.

So, say, throw $80 million or so at the problem?

Yeah basically. But if this is what the NSA were actually doing, I suspect they'd be throwing way more than $80M at it for a handful of devices, and instead be throwing half a billion at it for half a datacenter full of them. Why build a dozen or two crackers when you have the money for hundreds?

I think this sort of budget indicates more of a research project.

Huh, apparently I've already developed muscle memory for typing "2014". This is going to make writing certain powers of two difficult.

The thing is, we can never know how much many is put into what, as long as we accept that the government is allowed to take and hide money from the taxpayer like this: http://www.washingtonsblog.com/2013/11/8-5-trillion-taxpayer...

That paper is about 10 years old, or at least the research is. The most current source cited is from 2003. I like to think we've made significant progress in a decade, but in reality inflation would probably be enough by itself to throw those numbers completely out the window.

Reply on news.ycombinator.com