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

51–60 of 174 posts

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

#51

Post by mabbo »

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 all this money.

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

#52

Post by tzs »

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 would not claim to have solved factoring. I'd simply set up a web site where you can submit a large integer and hashes of its prime factors. The site would return "YES" if the hashes of the factors of the number match the submitted hashes, and NO if they do not.

Then I'd enjoy watching people try to figure out if I'd solved factoring, or broke the hash function, or both, or something else.

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

#53

Post by whatshisface »

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…

If Bitcoin was broken it would instantly become worthless.

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

#54

Post by 0xb100db1ade »

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.

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

#55

Post by all2 »

goerz wrote: post #13
alexandercrohde wrote: post #6

Earlier quoted context omitted.

But if intelligence agencies broke factoring, would we know? Maybe they have.

Unlikely, as they wouldn’t keep using methods that they’ve broken themselves

That's not the case. With compartmentalization as a core organizational design, the people with the crack won't be saying anything to the operations and infrastructure folks.

A key portion of an advantage like this would be who to share 1) derived intel and 2) capability with.

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

#57

Post by shoes_for_thee »

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…

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

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

#58

Post by nabla9 »

wbl wrote: post #42
daveFNbuck wrote: post #31

Earlier quoted context omitted.

It's basically that BPP captures all realistic polynomial-time computations. The speedup would have to be sufficient to show something like a problem in BQP that isn't in BPP. I don't think anyone has been able to show that unconditionally yet. You'd also need to accept that Quantum computers are realistic, which is why Aaronson's trilemma includes quantum computers being impossible.

That's true but Grover search shows that quantum computers can give big speedups so I don't know why I would believe BPP=BQP.

Grover's algorithm still takes exponentially many operations to solve a search problem that can be brute-forced in exponentially many steps. Much faster, but still in EXPTIME. No jump from exponential to polynomial complexity class.

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

#59

Post by ufo »

delinka wrote: post #17
JPLeRouzic wrote: post #9

I am not a scientist, but in my team 15 years ago, many people much more talented than me were in love with public cryptography. For them encryption with a 1024 key was perfect, impossible to break. They did not even considered that several RSA challenges had already been found. Even if I had no education in mathematics I tried to show that in fact it was feasible to factor some enough large numbers with "bc" (using…

I'm not following your story. At the time when 1024-bit numbers used in RSA were 'perfect', it was infeasible to factor the number in a reasonable amount of time. The most straightforward approach is just to iterate over integers from 2 to your target number (call it n ), and see if anything divides evenly. Now, you start looking for shortcuts. First, you can test only half the numbers, because the second half will g…

Doubling the bit length makes the problem much much harder than just twice as hard. The n in the sqrt(n) you mentioned is the number being factored, which grows exponentially with bit length.

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

#60

Post by hackcasual »

debatem1 wrote: post #56

I think it's interesting how many people worry about factorization. A second preimage attack on SHA2 would be at least as dangerous, and nowhere near as many people know or care about its assumptions.

Breaking hashes aren't a decision problem, so they're not directly comparable, but sha2 isn't on the same shaky mathematical ground that RSA is.
Post reply on HN