Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Factoring may be easier than we think (2016)

math.mit.edu

Post reply on HN
Print view View original

131–140 of 174 posts

Re: Factoring may be easier than we think (2016)

#131

Post by LeonM »

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

The same would go for finding a practical hash preimage attack. Say you can quickly determine an input that would hash into a given output, you would have a very, very valuable technology in your possession.

For both factoring or preimaging, I'd think I'd offer it publicly (any three lettered agency will find you anyway). I mean offering the 'service' as a commercial, legal, tax paying business.

- Offer factoring/preimages as a service, start with very high prices (like a million USD per input).

- Lower the price after every x sales. Like for every 100 sales, reduce the price by 50%

- Once the price goes below a certain threshold, release the algorithm.

This method has (I think) the most benefits:

- it slowly released to the public, giving everybody enough time to migrate away

- it makes you less of a target for government/organised crime, as it's less controversial for them just to pay instead of trying to extort.

- by incorporating a business and paying tax, offering this service will probably be legal in most countries (not sure though)

- by the time you release the algo, you'll have made plenty of money to retire, and you'll no longer be at risk since it is now public information.

And for those wondering: if you find practical SHA-2 preimage, you would NOT be able to mine bitcoin with it.

Re: Factoring may be easier than we think (2016)

#132

Post by Mirioron »

mabbo wrote: post #3

In a sense, this is terrifying. I mean, the math nerd in me is delighted at the idea, but in all practical senses if someone were to stumble upon and share a usably fast factoring algorithm tomorrow, the sky would fall. Sure, lots of crypto exists that isn't prime factoring based and we could move to that in a hurry- but it would be a lot like if we'd realized the Y2K problem on December 31st, 1999. Everything would…

It wouldn't even be as tame as you mentioned. Any encrypted information that has been caught and stored would also become available.

Re: Factoring may be easier than we think (2016)

#133

Post by Ar-Curunir »

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

Most cryptanalytic advances occur in tiny baby steps; there's rarely a big break that entirely lowers a long-standing problem from hard to not-hard.

Even when this occurs, the earliest iterations of these algorithms are intensely technical, and very slow. Of course, followup research often rapidly improves on these numbers, but that usually happens in collaboration with other authors.

So all-in-all, it is unlikely that a lone genius comes up with an efficient factoring algorithm all by themselves.

Re: Factoring may be easier than we think (2016)

#134

Post by enedil »

seppel wrote: post #47
cococonspirator wrote: post #38

Earlier quoted context omitted.

You won’t necessarily be able to verify it works empirically, even if you can prove so analytically, because it would be a complexity bound that was broken. If I could crack RSA keys for a mere one million times the computational resources used to create them, that would be a groundbreaking result and I would have “broken RSA”, but _I_ still wouldn’t be able to crack any RSA keys at all.

True, it could still be impossible to break RSA keys used in the wild with one normal PC. But still, you could factor smaller numbers faster than any other algorithm which would give you the confidence that it works. > _I_ still wouldn’t be able to crack any RSA keys at all. Everybody can crack RSA keys if the modulos is small enough. You just need to factor a number :) There actually nice list of numbers to try: htt…

In short, no. There's a reason that General Number Sieve is only used for numbers bigger that 10^80 and Elliptic Curve Method (ECM) is used instead. If number is smaller, than you don't benefit from the better complexity. This invalidates your point, because it might happen that your hardware is fast enough to factor a number using ECM and not fast enough to do the same with GNFS. So practically speaking, you don't have any assurance that what you have is fast or slow. Of course, it might happen that you actually manage to factor some big numbers, in that case you have the empirical proof you sought.

Re: Factoring may be easier than we think (2016)

#135

Post by gshubert17 »

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

Author Charles Stross explored a similar question in his short story "Antibodies": what happens to encryption or machine intelligence when the proof that P == NP is published?

https://www.antipope.org/charlie/blog-static/fiction/toast/t...

Re: Factoring may be easier than we think (2016)

#136

Post by jasonhansel »

rocqua wrote: post #119
jasonhansel wrote: post #63

Earlier quoted context omitted.

But what if you find an algorithm with a low asymptotic complexity, but with such a high constant factor that it could not be put into practical use? We would still want to move away from RSA (since constant factors can often be improved), but there would be no way to actually use the algorithm in its current form.

In that case, there is no immediate threat when publishing. Unless you area afraid someone else can improve on the constant factor, this won't break crypto.

> there is no immediate threat when publishing.

Unless someone else comes up with the same algorithm, and does lower the constant factor.

Re: Factoring may be easier than we think (2016)

#137

Post by johndough »

est31 wrote: post #65
0xb100db1ade wrote: post #54

Earlier quoted context omitted.

> current factoring algorithms would require enough energy to boil all oceans on the earth, that's a lot even compared to the US's energy supply. Interesting. For what algorithm & key size? I'd love to quote this. I've heard it before but I don't remember the source.

https://eprint.iacr.org/2013/635.pdf > Boiling all water on the planet (including all starfish) amounts to about 2^24 lakes of Geneva and leads to global security: 114-bit symmetric cryptosystems, 228-bit cryptographic hashes, 2380-bit RSA. This needs to be done 16 thousand times to break AES-128, SHA-256, or 3064-bit RSA. I think this paper isn't using Landauer's bounds though, but conventional computers. So maybe m…

But why the starfish.

Re: Factoring may be easier than we think (2016)

#138

Post by stormbrew »

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

Honestly if you figure it out, someone else is probably already on the verge of figuring it out or already has and is probably going through the same question. Likely a major intelligence power is ahead of you. There's very likely no benefit to keeping it to yourself for any significant amount of time and a lot of risk.

Just publish it. At most demonstrate it's been broken in some incontrovertible way so people figure out next steps more quickly. Protect yourself as best you can.

Re: Factoring may be easier than we think (2016)

#139

Post by im3w1l »

mabbo wrote: post #51
waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

The altruistic answers have already been posted, so here's what the devil on my shoulder recommends: I'd start a darknet web service, paid in crypto currency, that decrypts RSA. I'd adjust the price regularly to maximize my profit. The world would go crazy and very rapidly upgrade all software to not use prime factoring based encryption. I'd retire early to some lovely place, and never, ever, tell anyone how I got al…

Tor offers a high, but ultimately limited amount of protection. I wouldn't count on it to protect something as enormous as this.

Re: Factoring may be easier than we think (2016)

#140

Post by chaboud »

mabbo wrote: post #51
waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

The altruistic answers have already been posted, so here's what the devil on my shoulder recommends: I'd start a darknet web service, paid in crypto currency, that decrypts RSA. I'd adjust the price regularly to maximize my profit. The world would go crazy and very rapidly upgrade all software to not use prime factoring based encryption. I'd retire early to some lovely place, and never, ever, tell anyone how I got al…

Dude. You’d break crypto for payment in.... crypto?

Why not just create transfers quietly from others and bleed out wallets from around the world, then convert to cash, then publish? You’d be rich, crypto would crash, and you’d be able to buy a lifetime supply of popcorn for the ensuing collapse.

Post reply on HN