Factoring may be easier than we think (2016) • Hacker News Board

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

#61

Post by heimatau » Sun, Jun 30, 2019, 5:03 PM UTC

shoes_for_thee wrote: post #57

mabbo wrote: post #51

Earlier quoted context omitted.

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…

You're going to have to launder a lot of money. What's your strategy there?

Why launder? Plenty of goods and services would accept crypto as payment. No need to launder cryptocurrencies but the wild swings in price will affect your accounting in your business.

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

#62

Post by abecedarius » Sun, Jun 30, 2019, 5:03 PM UTC

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…

There's a novel about this, Factor Man. (I haven't read it.)

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

#63

Post by jasonhansel » Sun, Jun 30, 2019, 5:06 PM UTC

OscarCunningham wrote: post #29

aykevl wrote: post #14

Earlier quoted context omitted.

I once asked this a cryptographer. His response was that he would do the following things (if I remember correctly): * Discuss the result with a few cryptographers he trusts, to check whether he didn't make a mistake and to make sure he's not the only one who knows about it. * Write a paper. Put in all kinds of silly things, because it will get published anyway. * Publish proof of having found the algorithm, together…

You don't really need someone else to check if you've made a mistake. So long as you can multiply reliably you can just factor the largest one of the RSA prize semiprimes and then check that you did indeed produce some factors. I think my plan would just be to publish that factorisation anonymously (being super paranoid to avoid being traced) and then wait however long was necessary before publishing the algorithm.

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.

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

#64

Post by hackcasual » Sun, Jun 30, 2019, 5:06 PM UTC

dooglius wrote: post #50

EDIT: this comment was mistaken, bitcoin uses elliptic curve based key pairs, as hackcasual points out below. One thing to keep in mind: Bitcoin wallets are implemented with public/private key pairs. If you believed that you had a method to crack that, well you probably couldn't just take all the bitcoin (people would notice and the market value would evaporate), but you could probably figure out a way to make at lea…

Bitcoin signatures rely on the difficulty of elliptic logarithms, not factoring, and only publish hashes of the public keys until they spend an address, meaning the vulnerable window is quite short as long as they never reuse private keys.

The papers claim, that np but very likely not np-hard problems are likely to be in p is applicable though to breaking ECC

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

#65

Post by est31 » Sun, Jun 30, 2019, 5:07 PM UTC

0xb100db1ade wrote: post #54

est31 wrote: post #8

The US federal government once expended 10 percent of the US's electric energy supply in the Manhattan project for getting weapons grade nuclear material. This gives a rough ballpark for the amount of energy they are willing to invest into major strategic advancements. However, if you apply Landauer's principle, current factoring algorithms would require enough energy to boil all oceans on the earth, that's a lot eve…

> 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 my claim was wrong, because we aren't 16 thousand times away from Landauer's bounds but millions [1].

[1]: https://web.archive.org/web/20141219043239/http://www.bloomf...

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

#66

Post by JD557 » Sun, Jun 30, 2019, 5:08 PM UTC

heimatau wrote: post #61

shoes_for_thee wrote: post #57

Earlier quoted context omitted.

You're going to have to launder a lot of money. What's your strategy there?

Why launder? Plenty of goods and services would accept crypto as payment. No need to launder cryptocurrencies but the wild swings in price will affect your accounting in your business.

I'm not very familiar with cryptocurrencies, but wouldn't you be able to also crack crypto wallets? If so, wouldn't the value of crypto go down to 0 thanks to your service?

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

#67

Post by williamstein » Sun, Jun 30, 2019, 5:08 PM UTC

AlexCoventry wrote: post #44

williamstein wrote: post #40

Earlier quoted context omitted.

Also Andrew Wiles' six years of focused worked fundamentally depended on very deep work that Ken Ribet had just completed, which in turn relied on decades of highly nontrivial work by Mazur, Katz, and others on modular curves and modular forms, which made surprising connections with other areas of mathematics. Finally, Wiles' first announced proof of FLT was wrong, and Richard Taylor collaborated with him to find a c…

I'm going to read your book, because your book with Mazur on the Riemann Hypothesis was incredible.

Free PDF: https://wstein.org/books/modform/

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

#68

Post by heavenlyblue » Sun, Jun 30, 2019, 5:09 PM UTC

wbl wrote: post #19

doubleunplussed wrote: post #12

I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists a classical polynomial factoring algorithm that runs in polynomial time. One of these things must be true, and debates around quantum computing usually focus on the first two. But as argued, we don't have great reasons to believe factoring in polynomial time…

What is the extended Church-Turing thesis? We already know quantum computers give speedups beyond classical lower bounds.

Yes - is there any extended reading available re. subj.?

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

#69

Post by danbruc » Sun, Jun 30, 2019, 5:14 PM UTC

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…

I have thought about this before but with even higher stakes - finding a polynomial time algorithm for a NP-hard problem - because this would not only affect encryption algorithms based on factoring.

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

#70

Post by Rexxar » Sun, Jun 30, 2019, 5:15 PM UTC

shoes_for_thee wrote: post #57

mabbo wrote: post #51

Earlier quoted context omitted.

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…

You're going to have to launder a lot of money. What's your strategy there?

No need to launder, this money would not be illegal. Just convert it and pay your taxes. When you will have to justify your revenues, everybody will have migrated to different cryptography anyway and you will not be in danger any more and you will be able to use this money as you want.