Factoring may be easier than we think (2016) | Hacker News Reader

Factoring may be easier than we think (2016)

math.mit.edu

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?

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 with a hash of the paper.

* Wait ~3 years until everyone has moved to a better algorithm. The normal responsible disclosure period is 3-6 months but this is so big it has to take a bit longer.

* Publish the paper.

I certainly think this is pretty dangerous. It may in fact be better to do the initial publication anonymously... and make sure you avoid all possible traces (the NSA will do everything in their power to get a hold of you).

> Discuss the result with a few cryptographers he trusts, to check whether he didn't make a mistake

Well, what kinds of mistakes can you make? Either it works or it doesnt. You (and everyone else) can verify that easily.

(It might not work some numbers with special properties or so. But this does not matter if you can already break 99% of RSA keys)

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: https://en.wikipedia.org/wiki/RSA_numbers

You can factor, e.g, RSA-100 on a normal PC with state of the art algorithms in reasonable time.

That said, I had some new insight into factoring, and I was only a mere factor of one million away from factoring industrial crytography, I'd maybe try to optimize it a bit more.

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.

I agree in principle. But I disagree that you cannot test GNFS on small numbers. You can do this, but you are right that you might have trouble to easily verify that it has a better asymtotic complexity than other algorithms.

>If I could crack RSA keys for a mere one million times

You are off by many magnitudes. 1M is very little and equivalent computing power can be bought for a few tens of euros.

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.

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.

Cryptography research moves very fast =)

> there is no immediate threat when publishing.

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

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.

>to check whether he didn't make a mistake

No discussion needed. Simply MITM yourself or others in network to find out.

What would happen if you publish publicly? The cat's already out of the bag, they could not possibly want anything more from you, the info is out in the open. Obviously, this isn't ethical but math isn't illegal so there would be no legal consequences. You would be infamous.

No, I think this is a danger to you as long as you, and only you know about it.

Now, in the case you were to immediately publish this after you find out,same thing, you'd be safe. The fallout would be sub-optimal though, you would gain no immediate cash, but you would gain notoriety (maybe not the best kind) and you would give NSA and other intelligence agencies who presumably collected encrypted data for later deciphering. The internet security would probably be compromised for a couple of months, until new algos would be in place.

I am not a cryptographer and I just have minimal understanding of these things, but I'll take a crack at saying what could be done:

1) Tell no one. POC is sufficient to deomnstrate it working.

Ethical path goto 4

Unethical path:

2) Build a helper program that can easily crack keys on demand

3) Put it out on the darknet that you decrypt stuff for a steep fee. Get rich.

4) Publish the finding, do not provide the algo, focus on maintaining anonymity and having impeccable OPSEC. Provide proof.

This will mean that everybody knows how unsafe their infrastructure is and there will be maximum effort to move everything to something else. But the algo is still contained and people can not yet have the power, _you_ have it. This, of course exposes you to maximal risks but also maximizes your potential financial reward. Maybe someone will soon find a way to crack it too, and then your show is off. Or maybe they will never find it and you remain a mystery, the _one_guy who could brake prime factoring. (unlikely, considering the number of smart people on this earth)

5) run faster than the NSA/CIA, FSB, DGSE, GCHQ/MI6, etc. Because if any of them finds you they will challenge your opsec with a wrench or with electrical wires strategically placed.

Is there any alternative to factoring for asymmetric cryptography? I was under the impression even elliptic curves are based on factoring (though not a cryptographer myself). If that’s the case we would have to live in a world with no asymmetric encryption. That would be interesting.

I believe elliptic curves aren't broken by factoring. You might be confused with shor's algorithm. That is a quantum-algorithm that breaks both elliptic curves and RSA.

It doesn't break elliptic curve crypto by factoring numbers. Instead, it breaks them by solving the discrete logarithm problem.

I don't think it would happen this way. First, other researchers would be looking for that algorithm too and therefore, institutions would have time to prepare. Second, leveraging a technical attack imply to have some operational support. The bigger the attack, the bigger the organization you need to implement it...

This is the main reason that I don't store any of my sensitive data encrypted on cloud storage.

If the encryption eventually gets cracked somehow, my data will be available not only to whoever owns, hacks, or otherwise compromises the cloud storage provider itself, but anyone who happened to have captured the traffic on any of the hops it went through on the way to the provider.

What if you encrypted using a symmetric key approach instead?

You should be using symmetric encryption, which is likely a lot less breakable.

I think there are only two safe options if your intention is to avoid being assassinated: 1) don't tell anyone, 2) publish it anonymously. If you want to be able to prove to somebody that you're the author, sign the paper and keep the private key offline on a piece of paper.

It'd be interesting if it could be used to manipulate voting results, but e-voting is still in its infancy.

Interestingly, the consequence of releasing that algorithm would make having that private key insignificant since most schemas rely on factoring primes to secure the key pair.

HMAC with sha-256 works decently. No need to involve a public key.

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.

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?

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 financial interest to be savvy enough) and the adopter could alarm the community that an exploit is in existence.

In addition, there are various cryptographic algorithms used. So, one could accept Litecoin, if SHA-256 was exploited. Or accept Vertcoin if both Script and SHA-256 was exploited. Etc.

So, it's an interesting situation based on game theory of an exploit. There is no hard and fast answer.

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.

The moment you have spent from an address, you have revealed the un-hashed key, which you could break. Best practice is never to re-use address, but I'd wager there are many deviuations from that. I'm not sure how much bitcoin that has moved in e.g. the last year is in addresses for which the private key is known. Would be a cool thing to check out.

Bitcoin uses an elliptic curve algorithm secp256k1 for signing. This would be the relevant thing to break to take control of wallets.

presumably this darknet service to decrypt RSA is being used for nefarious purposes. i suppose you could prevent yourself from having access to the stuff people are decrypting and hope some kind of safe-harbor law would protect you.

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.

Because there will be fifteen nation-states who want to kidnap you and force you to disclose the algorithm?

Just Tarex teams and Mossad by themselves would be a big threat. NSA has the visibility to de-anonymize even some people on Tor. Most mathematicians aren't exactly computer security geniuses. NSA might not even need to work that hard. Then, they have plenty of partners for grabbing whoever or whatever the target is.

https://theintercept.com/2014/10/10/core-secrets/

You don't have to keep it private after 2/3 months. Just make the algorithm public and no one will kidnap you.

Is it illegal to break encryption by brute force?

Intent matters. If you are breaking encryption to steal stuff, that is (and should be) illegal.

I think the real question here should be whether it is immoral though, because it is trivially illegal. Consider the DMCA and penalties for circumventing DRM. Heck, if you are decrypting stuff that is classified, intent might not even matter.

Use a mixer.

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

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.

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.

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

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.

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 emergency; the world is already moving somewhat rapidly towards elliptic curve systems anyways.

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.

“Efficiently” has multiple meanings. In the context of P and NP, “efficiently” just means in P - it says nothing about how hard the algorithm would actually be to implement, nor how expensive the computation actually would be. O(n^100) is in P, but it’s thoroughly impractical in practice, even for the NSA.

Indeed, the authors who proved that primality testing was in P did so with, IIRC, an O(n^12) algorithm (with n being the number of bits), which is not much use in practice. Although, in that case the result was already widely suspected to be true, and fast, randomized (non-deterministic but highly accurate) polynomial-time algorithms were already known.

The primality test has been whittled down to O(n^6) ... it seems that solutions to problems in P with high degree always get optimized over time.

Also, even a O(n^100) sol'n is way better than O(2^n) since (usually) I can parallelize polynomial time algorithms to something more practical: e.g., http://cds.iisc.ac.in/faculty/vss/courses/PPP2014/projects/p...

I would keep it quiet, and only use it occasionally as a "last resort weapon" for breaking DRM and other user-hostile forms of security, like a digital Robin Hood. Its use would have to be very carefully obfuscated so that people would suspect other things first.

...there's probably already sci-fi around that idea, but if not it'd be a great plot.

1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then destroy all credentials, so it could not be undone.

2. Steal bitcoins from very old wallets with some small amounts. Supposedly those wallets are lost. Steal enough to have enough money to live a good life. Well, if for some reason I would have enough money, skip this step.

3. Break google.com certificate and mail hashes to Google Security team. Ask them to disclose that factorization is broken, so the rest of the world can prepare. Repeat with some other big companies.

4. Disclose algorithm when the world is ready.

You have given this much thought care to elaborate?

Factoring doesn't allow you to break discrete log; you won't be able to steal from old wallets.

It's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.

It's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to the DLP.

I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]).

The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up factoring (at least not in a way that makes it polynomial).

[1] https://en.wikipedia.org/wiki/Reduction_(complexity)

[2] https://en.wikipedia.org/wiki/Shor%27s_algorithm

(EDIT: typo)

They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of...

That for DLP modulo a composite, whereas Bitcoin uses DLP over elliptic curve groups.

I think you are mistaken, they are not equivalent in any way that would be meaningful to assessing cryptographic strength.

The stack-exchange questions that you link to refers to [1] "Discrete Logarithms and Factoring". Section 1 "Introduction" already states many facts that imply that DLP is hard, even if you can factor:

* fastest known method for DLP is O(exp(c sqrt(log n log log n)))

* 1. 3c) "if we can factor in polynomial time, then to quickly solve a^x ≡ b mod n, all we need are solutions modulo the prime divisors of n"

Note that "solutions modulo the prime divisors of n" are still instances of the DLP with super-polynomial complexity, and in cryptographic applications N is usually a prime number anyway (DHE, ElGamal crypto-system), so 1 3c) does not actually apply.

See also the paper's section 6 final remarks "Conversely, one can ask for a fast algorithm for prime-modulus problems, assuming all needed factorizations. Both of these questions remain unanswered".

[1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186...

>> I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial

That is what I remembered. You don't need Shor's Algorithm though. DLP would help finding roots, in particular if the log of a number is even, you can compute the square root of the original number which is useful for finding quadratic congruences (the goal of the quadratic sieve). The reverse (factoring enables DLP) does not appear to be true.

They are equivalent (with some caveats) when considering the multiplicative subgroup Z_N where N is a composite. Bitcoin relies on DLP over elliptic curve groups.

Solving the discrete log problem would require that your factorization algorithm have the capability of being adapted to DLP. Some factorization algorithms can do this, but, IIRC, some cannot.

possesses quite literally, the "keys to the kingdom"... steals lol

I am not sure I'd ever want to reveal my identity, ever. Becoming famous for something like this would make my life way too dangerous, forever.

Obviously I would publish immediately in as many public forums as I can and wait for the sweet, sweet upvotes, stars, retweets, likes and karma to roll in.

Someone else could use the published work to roll back your upvotes.

Sounds like a great premise for a sci-fi movie.

you might enjoy "Travelling Salesman" 2012 ‧ Thriller/Drama ‧ 1h 20m

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.

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.

The odds that a modern genius will eclipse the work of 2200 years’ worth of previous work are far smaller.

Improve on the old record? Possible. Shatter it at this late date? That’ll take a mode of thinking that nobody has tried.

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...

Nothing if it’s non constructive.

... in the case of a non constructive proof, there would still be a significant change: it would dramatically ramp up the search for a constructive proof

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.

You show it to someone in Hollywood and they then go and make the film 'Sneakers', probably. https://www.imdb.com/title/tt0105435/

This comment encapsulates the plot, events and a monologue of the movie Sneakers made in the early 90s.

I would publish it immediately, after checking as best I could that it was actually a working solution. But here's the twist:

I would publish it in such a way that it would appear to have been released/solved by the worst person I didn't like; a world-known dictator or similar would be ideal. Nobody would believe it, but maybe their narcissism wouldn't let them not play along. It very well might screw their life over in ways unknown.

The uproar around the world would be very interesting to watch.

But I'd definitely make sure I wasn't connected in any way - you would likely have a target on your head (because if you could do that - what else could you know or do?)...

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.

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

I doubt it, too; but using methods you've broken, but know others haven't, is a great way to convince people you haven't broken it either. And if you suspect they have, it's a great channel for misinformation.

You could also embed content with stronger security inside the wrapper you’ve broken, so even if someone else has figured it out, they can’t decrypt your real messages.

Hopefully.

Nice

They could switch algorithms and claim that they were just doing it to be resistant against quantum computers.

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.

If they have then they are using it exceedingly sparingly.

I strongly suspect it would be impossible to use it to any moderate degree without being found out in one way or another.

I know this is a very very poorly worded question :) but I wonder what the most amazing secret was that was held for the longest time?

Probably the most useful thing to do with this power if you had it would be and signing your exploits with all sorts of legit keys. Maximal effective exposed area on all parts of the hardware and software stack of multiple potential opponents. The real work would be using the information and trying to find other ways to discover the same thing. Classic intel problem.

We know they had public key crypto a few years before RSA.

> but I wonder what the most amazing secret was that was held for the longest time?

Very relevant, probably the Allie's breaking the Axis enigma code in WWII.

https://en.m.wikipedia.org/wiki/Ultra

If the NSA broke RSA, they'd have a similar program set up to ensure nobody notices.

>I wonder what the most amazing secret was that was held for the longest time?

I heard that the use of the golden ratio in projects such as the engineering of cathedrals, required that the first thing you do before you draw your plan is to draw a pentagram, in order to derive the ratio using simple drawing tools, and then carefully erase it, or in other words, make it occult. http://www.matematicasvisuales.com/english/html/geometry/gol...

Also, I'd really like to know who in the hell built the Ankythera device. https://en.wikipedia.org/wiki/Antikythera_mechanism

I think that number (100) is a bit too low. There are students, graduates, post-grad fellows, and otherwise thousands of people living and breathing number theory. Sure, they might not directly stare at a blackboard with The Problem of Factoring staring back at them, but they are very much doing that indirectly.

Just like the AKS primality testing algorithm depends on clever number theory, any progress, any new trick would be very likely reported, and we'd see it in charts like these:

https://aiimpacts.org/progress-in-general-purpose-factoring/

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 probably similar.

I work in this field as a non-academically-trained cryptographer. Cryptographers prefer to assume their assumed-hard functions are in fact hard and move on. Especially those that have academic training--they supposedly know better than to waste their time on such a hard problem.. but by induction that means approximately nobody is really looking at it.

> 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.}

> There were plenty of people who tackled this problem and who failed to make any headway.

There was also plenty of meaningful progress throughout the 20th century at least, showing that the FLT was implied by other statements which would be easier to prove. Wiles's work was a follow-on to this progress; it's quite misleading to say that it "took" a single guy working over six years to prove FLT.

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 correct and quite different proof. (Disclaimer: I published a book on modular forms, and cowrote papers with some of the people mentioned above.)

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/

Thanks.

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.

He was the lucky one. Many many mathematicians thought they saw a path. And spent years. And it did not lead anywhere/there in the end.

See also the many P = NP proof attempts. (Sure, most of them are complete crackpot garbage, but that doesn't mean serious attempts are not made, and probably more serious attempts are made that then go nowhere so the author doesn't disclose it.)

in reality all it took was one guy dedicating a couple of months of exclusive work to it

This is wrong. Many professional mathematicians attacked the problem, and many useful discoveries were made before it was proved. For a brief summary, see https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem#Early_...

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.

> 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...

But why the starfish.

Because if you're already boiling the oceans, you probably won't have enough left over in the budget for marine conservation.

> This gives a rough ballpark for the amount of energy they are willing to invest into major strategic advancements.

I'd say, rather, that it gives a rough ballpark of how much the government was willing to invest in the 1940s, at the peak of its ability and willingness to take on projects of incredible scope. There was still a fair amount of this for a few decades after that, but not since the 70s. See https://rationalconspiracy.com/2012/06/03/why-doesnt-our-gov... for one person's take on this (though you don't have to go as far as she does, I think, to establish that applying Manhattan Project numbers to anything going on today will result in an overestimate).

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 is impossible. We certainly don't have a proof that no such algorithm exists.

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

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.

This sort of statement is exactly why serious people shouldn't take "quantum complexity theory" seriously. The complexity class BQP is bullshit: there are no quantum computers, the end.

Feel free to prove me wrong by building one which does useful calculations. No time limit, until you die, in which case "time's up."

Edit add for downvoters: the strong Church Turing thesis is also almost certainly, and very obviously bullshit. How does that make you feel?

Which statement are you saying demonstrates why people shouldn't take quantum complexity theory seriously?

BQP doesn't exist: there are no quantum computers. Saying BQP is like saying "magic fairy dust perfect unitary transformers that effectively encode a perfect complex number in the same sense a protractor theoretically can solve NP-complete problems by encoding real numbers."

So we shouldn't take research into things that don't exist yet seriously?

Designing algorithms for a computer architecture that assumes matter behaves in a fairly trivially unphysical way sure seems like a glass bead game to me. Especially considering the hype and baloney around this particular one. There are zero actual quantum computer designs (aka error corrected and capable of factoring large or even small integers into primes) under construction: but everyone runs around like chicken little declaring the sky is falling.

I went to a Gordon conference on this subject in the 1990s; as far as I can tell, there has been zero progress in the topic since then. Sure are a lot of press releases though!

At what odds would you bet that we won't see a quantum computer outperforming a classical computer on any problems in the next, say, 20 years?

The qbits and unitaries don't have to be perfect - it's about how things scale when you add qbits. Quantum error correction shows that you can add more qbits to make up for imperfection, and still be left with a quantum computer, i. e. the imperfection hasn't demoted the thing to a classical computer.

Of course they haven't built one yet, but none of the difficulties encountered so far have involved discovering new physics, which is what you would need to do to rule out quantum computers since the laws of physics as currently understood permit them.

You've just regurgitated Aaronson's statement on the topic. Aaronson never studied physics, and has probably never fiddled with an op-amp or tried to make entangled anything in the world of matter. There's zero evidence quantum error correction will work; it's just an idea with no basis in the world of matter. There's zero evidence you can meaningfully and usefully manipulate quantum coherent states, let alone manipulate an exponentially huge number of them with a polynomially large number of computational elements, which is the essential claim of quantum computing. They make great claims: great claims need evidence; not theoretical wankery. Building a couple of scalable error corrected qubits would be a great start; it might even cause me to shut up about it.

Never in the history of the human race has something as complex as a computer architecture existed in the theoretical world before it exists in some form in the physical world, let alone one for which we define complexity classes.

The entire field is intensely silly, and the last time I said so in a public place, the waiter turned out to be some dude who just got his Ph.D. in the subject. He didn't agree with me exactly, but the fact the dude had a job bringing people steaks for a living is a decent argument I'm right.

My arguments are my own. I am an atomic physicist, and I meaningfully and usefully manipulate coherent quantum states every day. Not for making a quantum computer mind you, but quantum states nonetheless. Quantum mechanics works. The atoms do exactly what the Schrödinger equation says they should, however much entanglement is added. We are yet to see it break down. Plenty of my colleagues are working on quantum computers, with atoms, ions, photons, and solid state systems, and from where I stand it doesn't look like nonsense. It looks steady progress, and if there are insurmountable barriers, they have not yet been encountered.

I am not certain that quantum computers are possible, but I am certain that you are wildly overconfident that they are not.

How much money are you willing to stake on that statement? I'll make a market for you; if you think your education gives you an edge over the wildly overconfident guy -we can even stick it on a blockchain that is quantum future proof if you like. Your choice.

Saying "quantum mechanics works" is not the same as saying "I can manipulate exponential QM states with polynomial imperfect physical devices." In the early days, people sketched out optical quantum computers that totally worked, but had exponential growth in elements with quantum states. Which, I bet, is how the universe is always going to work.

Money where your mouth is: I haven't found any other good shorts for this shitty idea.

I asked you elsewhere in the thread what odds you're willing to bet at, so absolutely I'm willing to put my money where my mouth is. I'll happily bet that there will be a demonstration of 'quantum supremacy' within 20 years - that is, a quantum computer computing something faster than a classical computer, whether it's Grover's algorithm or factoring or something else. Let's say by the 1st of July 2039.

I'm not super confident there will be quantum computers, whereas you seem very confident there will not be. What do you think the probability of quantum supremacy within 20 years is? If you think it's 5 % and I think it's 50 %, perhaps we can take the geometric mean and bet at 6:1 odds (~15% chance).

Will you give me those odds? Let's say I stake $200. Then I'd give you that if I lose, and you'd give me $1200 if I win. Or we can increase the amount a bit. Today's dollars, we can inflation adjust since it'll be 20 years.

The terms might sound favourable to me, but you seem very confident that there won't be quantum computers ever, so less than 15% chance in the next 20 years seems consistent with your belief.

I wouldn't know how to put the bet on a blockchain, but if you know about that and want to, I'm happy. Otherwise I am happy to just take your word.

We can also shorten the duration of the bet, but I would want to shift the odds a bit since although I think quantum computers have a decent chance of being possible, there is considerable uncertainty in how long it would take to get to the point of demonstrating quantum supremacy. Probably I would accept doubling the odds if the duration of the bet were halved and so on.

We'd need a hard definition of "quantum supremacy" -I believe there have been several press releases claiming this already, and I think you agree with me that there are no such machines at hand.

There's this ethereum thing called Augur we could use to place the bet, though that's an interesting bet in itself (ethereum and auger being around in 20 years is not a sure thing). I suppose also "long bets." If you google my name you can find my contact info.

The problem here is that you just state something that looks like strong personal opinion. You vaguely refer to serious people.

You’re merely goalposting Scott “Quantum Computing Fists of Fury” Aaronson’s trilemma. If you have proof that quantum computers are physically unrealizable, I’ll happily help you publish that paper. There’s no way my brother could belittle my lack of education if I had a Turing Award or Nobel Prize, or two.

I'm betting on n. Where n stands for us not fully understanding how causality works yet, or a lot about what the hell is going on in general. I'm also rooting for something interesting emerging unexpectedly from Umbral Moonshine, because who can't help but love the Monster Group? https://www.quantamagazine.org/mathematicians-chase-moonshin...

The original Church-Turing thesis says nothing about computational complexity. Extended Church-Turing thesis says that all Turing machine equivalent computers can compute the same problems withing polynomial time.

Quantum computers are not known to be capable of solving NP-Complete problems in polynomial time.

Do we know that quantum effects will actually scale large enough to realize those speed ups for arbitrarily-large problems though?

To paraphrase stuff from Scott Aaronson that I can't find right now: The currently known laws of physics say yes, and nobody's proposed any new laws of physics consistent with current observations which say no and don't allow even more computing power.

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

Factoring is one of the few quantum algorithms that is odd man out in terms of noise/implementation/scaling/etc. This should be indicating something about the structure of factoring that we don't understand.

Out of all the "classical" problems that we might find another algorithm for, "factoring" would be my bet for the one that we are missing a better algorithm.

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.

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

> Of course, I have no real evidence for my views...

> On the other hand, the people who talk about the great difficulty of factoring have equally little evidence...

This is a classic antinomy (paradox): one can argue indefinitely in either direction, because the question lies along the bounds of human reason (or so says Immanuel Kant).

The two sentences above, in themselves, provide a bit of evidence of the impossibility of solving the problem, and at the same time provide evidence for the possibility of handling this problem as a significant phenomenon of pure mathematics.

EDIT: I mean only that the insolubility of the problem may itself be of mathematical use: it may (insofar as it is unsolvable, and insofar as it appears to be soluble) amount to a kind of 'anchor' for mathematics, a marker that indicates the boundary of the mathematical sciences, and that such a boundary would be of tremendous import to mathematicians and philosophers. Why is _this_ problem, _this_ problem specifically, unsolvable? (Rather than some other problem that has been solved?)

tl;dr The question of "why have we have trying to solve this problem for millennia?" is perhaps more significant for mathematics than the solution to the problem.

This is the Henry Cohn that recently received recognition for his work on optimal sphere packings in 8 and 24 dimensions: http://www.ams.org/journals/notices/201804/rnoti-p463.pdf

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.

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 give identical results (e.g. n=20, n/2 = 10; later, n/10 = 2; no need to even test the second half of the range.) Next, it becomes obvious that we only care about odd numbers (if it's divisible by an even number, it's divisible by two); but really, when it comes down do it, we only care about prime factors (for one thing, all non-primes can be decomposed into prime factors; for another, we used prime numbers to get n.) And lastly, for the simple shortcuts, you really only have to get to int(sqrt(n)) + 1 or so. So we've cut down the number of integers we have to divide with.

Did we find the two prime factors of our n in a "reasonable" time? If so, just double the bit length to get a problem twice as hard. Every publicly-known shortcut to factoring large numbers just means you need to make your n larger to increase the workload on an attacker.

The question then becomes: has anyone found a shortcut that will factor any number within a "reasonable" time? We don't know.

As to your career-related comments, I read cluelessness from your boss, and carelessness from the 'other guy' - if OG "would not try to break any encryption scheme," then he's not the person whose advice you want about the strength of cryptosystems. Your boss just lacked critical thinking skills.

Even 15 years ago 1024-bit numbers were not secure.

I'm working on RSA4096 and this is secure minimum up to 2040. Factoring is secure for all times, that's a numeric principle. You only have to make the key/number greater. I'm working for 50 years with prime numbers and now I'm where I was when I was 17. Only a little nearer. What Fermat didn't find and Euler missed (!) is the knowledge that there is no super'algorhythm' for factoring.

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.

Nobody yet has mentioned a film that was premised on the invention of a black box "capable of breaking the encryption of nearly every computer system".

IIRC the movie plot was somewhat convoluted and confusing and I don't have any desire to see it again. I'm bringing it up because there are a number of "what would you do if" posts here.

In the end, the "sneakers" use the box to cause: the sudden bankruptcy of the Republican National Committee, and the simultaneous receipt of large anonymous donations by Amnesty International, Greenpeace, and the United Negro College Fund.

https://en.wikipedia.org/wiki/Sneakers_(1992_film)

> 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.

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.

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 least 1% (a couple billion). So if it can be broken with a group of smart people thinking hard, that sounds like a startup opportunity.

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.

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

I did a toy project on wheel factorization if anyone is interested. Through it I learned some interesting math and ancient algorithms. It is by no means the cutting edge of factorization, but it was a fun little project.

https://github.com/mcastorina/wheel-factorization/blob/maste...

Discussed at the time: https://news.ycombinator.com/item?id=12355431

With a grain of salt

> Of course, I have no real evidence for my views: [...]

Whoosh. The point is that NOBODY has any real evidence either way, so one shouldn't have a strong default prior of the problem being truly "hard."

Might want to include context there:

>Of course, I have no real evidence for my views; ... On the other hand, the people who talk about the great difficulty of factoring have equally little evidence.

When we talk about the 'difficulty of factoring' there's an implication. The direct meaning is that there may well be a simple algorithm for factoring that has yet to be discovered. No one disputes this.

The implied idea is that this discovery could happen at any time and all things depending on it are at risk. This is also true but it's unreasonable to think that it is likely given that much effort has been put into this.

Yes we don't know, but two unknowns are not 50:50. Of course regardless of how you estimate its truth consider the cost of being wrong when using anything depending on it.

Purely tangential, speculative questions: If you did prove that P = NP would you tell anyone? If so, how? Why?

Yes, I’d check the proof with some trusted colleagues, because odds are I’m wrong and I’d want to know why.

P=NP is a very hard problem and there have been a lot of failed solutions (including some that are flawed for very subtle reasons that can be easy to overlook). Even many famous, well known people have fallen into the trap of thinking they have a viable solution.

Fast factorization is going to be one of the killer apps of photonic computers.

You mean quantum computing (for which photonics are not a leading candidate), or regular photonic computing? Because the latter doesn’t scale any better than normal computers.

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.

The reason factoring is hard is because finding very large probably prime numbers is easier making number sieve based methods useless for the purpose of breaking large numbers used in cryptography.

You can build a machine with a laser and a big mirror.

Reply on news.ycombinator.com