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

1–10 of 174 posts

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

#2

Post by Jabbles »

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100.

In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

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

#3

Post by mabbo »

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 need to be updated right now, immediately, today.

And yet part of me is kind of excited it could happen.

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

#6

Post by alexandercrohde »

Jabbles wrote: post #2

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

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

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

#7

Post by waynecochran »

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 algorithm)? Would you use it for personal gain or power? Who would you tell first? Who do you trust?

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

#8

Post by est31 »

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 even compared to the US's energy supply.

So algorithmic improvements are the real danger basically. Even if we discovered a decryption method now, and immediately everyone stopped using RSA, there would still be an immense impact because all the past encrypted traffic that someone might have stored somewhere suddenly becomes decryptable. And usually, traffic from 20 years ago is still relevant today.

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

#9

Post by JPLeRouzic »

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 square root and a few other simple tricks) so the risk of having encryption broken by professionals was quite serious.

My boss asked to another guy for its advice, which was essentially that for a start he would not try to break any encryption scheme anyway. And that was the end of the story. The unstated lesson was probably that there were no reason to expect a career boost by working on such topics.

Post reply on HN