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

81–90 of 174 posts

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

#81

Post by webdva »

> The first thing to realize is that until the advent of public key cryptography in the 1970's, few people cared about factoring. Some people were interested in it for its intrinsic beauty, but nobody thought it was good for anything, and it certainly wasn't the notorious unsolved problem it is today. If anything, it was mildly obscure.

"There is no branch of mathematics, however abstract, which may not some day be applied to phenomena of the real world." - Nikolai Ivanovich Lobachevsky

Applied mathematics is a problem looking for a solution and pure or abstract mathematics is a solution looking for a problem. An instance of this is the extension of the set of complex numbers called the quaternions discovered long ago which eventually found their application in affairs that require the representation of orientations in three dimensions, such as in computer graphics.

It seems here then that a motivated entrepreneur can establish a remunerative business should he or she find a solution to this prime factoring problem.

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

#82

Post by danbruc »

BubRoss wrote: post #73
danbruc wrote: post #69

Earlier quoted context omitted.

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.

For any NP hard problem would be ground breaking, but many individual NP hard problems can be approximated with imperfect but extremely effective methods.

With an exact algorithm you could use, for example, 3-SAT to attack most if not all classical encryption algorithms. The know approximations are obviously not good enough for that, otherwise we would already be in trouble.

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

#83

Post by archgoon »

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.

You might have discovered a fast algorithm that doesn't actually reduce the asymptotic complexity (just flattens it out for a larger initial space), or the asymptotic complexity isn't what you think it is.

This has little impact on what someone can do with the algorithm, but it sounds like the author is concerned with ensuring that they understand why their new algorithm works. Since they're committed to not discussing their discovery for several years, it seems reasonable to want to make sure they haven't convinced themselves of something that doesn't work the way they think.

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

#84

Post by tptacek »

akvadrako wrote: post #78
tptacek wrote: post #76

Earlier quoted context omitted.

This is pretty overwrought. There have been numerous times over the last 15-or-so years where people have quietly had the ability to spoof arbitrary certificates due to PKCS1v15 signature verification bugs – there was just this year an NDSS paper published on a whole new raft of them, and it'll be at Black Hat in August as well. A fundamental class break that takes down RSA would be a big deal, but not a national eme…

Spoofing certs is not comparable to breaking RSA. Also, I think for this thought experiment, you should also consider breaking elliptic curve crypto. Neither has been proven hard.

Spoofing certificates was the example given in the parent comment. We use elliptic curves specifically because they are harder, in a specific way (resistance to index calculus) than simple multiplicative group cryptography.

My point is just that nobody is going to kill you for this ability.

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

#85

Post by anyfoo »

heimatau wrote: post #72
JD557 wrote: post #66

Earlier quoted context omitted.

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?

Cracking RSA isn't cracking SHA-256. Bitcoin and other coins are based on SHA-256. If someone were able to crack SHA-256, the exploit would be better served (of the hacker) to slowly steal coins, so that value within the network is maintained and the exploit is overlooked and missed by the majority. In addition to stealing national secrets. But all you'd need to do is steal from one early adopter (it's in their finan…

It’s not about the hashes, i.e. the proof of work part, it’s about the fact that bitcoin addresses are public/private key cryptography, like RSA.

Now I think bitcoin actually uses es elliptic curve cryptography (I don’t know, I really don’t care about bitcoin), but the hypothetical was more along the lines of “what if you could break public/private key cryptography”, and less about factorization in specific, anyway.

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

#86

Post by dumbfoundded »

whatshisface wrote: post #53
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.

Not if you did it in a smart way. Let's say you could arbitrarily make transactions. Probably the best way to do it would be to steal all the coins from a particular exchange, like Coinbase. Then everyone would think Coinbase pwnd but bitcoin is fine. Rinse and repeat with other exchanges once a year and you can make a hefty profit.

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

#87

Post by garmaine »

DanBC wrote: post #25
garmaine wrote: post #18

Earlier quoted context omitted.

I think the core point of the OP you are missing is that he doesn't consider people indirectly, tangentially working on related things as doing "serious" work on factoring. I tend to agree. Look at Fermat's last theorem: it went over a century as one of mathematics hardest unsolved problems, and in reality all it took was one guy dedicating a couple of months of exclusive work to it. Factoring (and discrete log?) is…

> it went over a century as one of mathematics hardest unsolved problems, and in reality all it took was one guy dedicating a couple of months of exclusive work to it. Six years, not a couple of months. There were plenty of people who tackled this problem and who failed to make any headway. {Edit: I phrased this last sentence really clumsily, sorry.}

By his own report, it was a few months of tackling the problem from various angles until he found the pathway that would eventually bear fruit, and formalizing that and fixing little problems along the way was what the next six years were spent on.

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

#88

Post by heimatau »

anyfoo wrote: post #85
heimatau wrote: post #72

Earlier quoted context omitted.

Cracking RSA isn't cracking SHA-256. Bitcoin and other coins are based on SHA-256. If someone were able to crack SHA-256, the exploit would be better served (of the hacker) to slowly steal coins, so that value within the network is maintained and the exploit is overlooked and missed by the majority. In addition to stealing national secrets. But all you'd need to do is steal from one early adopter (it's in their finan…

It’s not about the hashes, i.e. the proof of work part, it’s about the fact that bitcoin addresses are public/private key cryptography, like RSA. Now I think bitcoin actually uses es elliptic curve cryptography (I don’t know, I really don’t care about bitcoin), but the hypothetical was more along the lines of “what if you could break public/private key cryptography”, and less about factorization in specific, anyway.

Hmm. SHA-256 will be sunsetting probably within our lifetime due to the exponential nature of our computers. Which is probably why I assumed you'd be speaking about that function.

But a break in ECC would be...something extreme IMHO and according to multiple researchers, I believe, would happen after SHA-256 because ECC is more settled mathematics.

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

#89

Post by phicoh »

waynecochran wrote: post #4

I have always wondered if the NSA has figured out how to factor effeciently.

One thing to remember here is that RSA can be used in 2 ways: to encrypt and to sign.

If RSA is used to encrypt (for example if you send an encrypted message using PGP) then factoring directly breaks the encryption.

In practice, a lot of encryption on the Internet uses RSA to sign the hash of a key obtained using Diffie-Hellman. In this case breaking RSA would allow the NSA to impersonate but not directly break existing communications. The problem with impersonation is that it is very noticeable.

What I find odd about the linked article is that it only talks about factoring. In practice, the discrete log. problem is just as important and is very much related to factoring.

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

#90

Post by phicoh »

hackcasual wrote: post #60
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.

SHA-2 was on related shaky ground. Remember that in relatively short significant advances were made in breaking MD-5 and SHA-1. SHA-2 is based on similar constructs as MD-5/SHA-1.

For this reason the SHA-3 competition was started to find a new hash function based on different principles.

In the end it was found that creating practical attacks for SHA-2 is too hard. But we don't know what the future will bring.

The difference between RSA and SHA-2 is that RSA is a very nice mathematical structure and we are still learning a lot about (prime) numbers. In contrast, SHA-2 is weird structure that has to solve a hard problem. It is hard to attack.

Post reply on HN