[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?

[vbezhenar]

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.

[tuxxy]

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.

[simonebrunozzi]

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.

[Ar-Curunir]

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

[phkahler]

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

[dvdkhlng]

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)

[phkahler]

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

[baby]

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

[dvdkhlng]

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

[Ar-Curunir]

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

[Ar-Curunir]

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.

[lowdose]

You have given this much thought care to elaborate?

[ConcernedCoder]

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

[aykevl]

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

[OscarCunningham]

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.

[jasonhansel]

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.

[rocqua]

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.

[jasonhansel]

> there is no immediate threat when publishing.

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

[Ar-Curunir]

Cryptography research moves very fast =)

[archgoon]

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.

[RealityVoid]

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)

[cm2187]

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.

[cm2187]

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.

[rocqua]

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.

[seppel]

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

[cococonspirator]

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.

[emilfihlman]

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

[seppel]

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.

[enedil]

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.

[seppel]

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.

[emilfihlman]

>to check whether he didn't make a mistake

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

[tzs]

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.

[mabbo]

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.

[chaboud]

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.

[shoes_for_thee]

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

[Rexxar]

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.

[fwip]

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

[nickpsecurity]

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/

[Rexxar]

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

[heimatau]

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.

[JD557]

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?

[heimatau]

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.

[rocqua]

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.

[anyfoo]

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.

[silasdavis]

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

[shoes_for_thee]

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.

[bobbylarrybobby]

Is it illegal to break encryption by brute force?

[rocqua]

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.

[gsich]

Use a mixer.

[im3w1l]

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

[tptacek]

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.

[akvadrako]

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.

[tptacek]

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.

[xwdv]

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.

[rocqua]

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

[stormbrew]

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.

[userbinator]

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.

[wiz21c]

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

[nneonneo]

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

[waynecochran]

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

[LeonM]

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.

[gshubert17]

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

[empath75]

Nothing if it’s non constructive.

[DoctorOetker]

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

[zvrba]

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.

[aewens]

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.

[rocqua]

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

[cr0sh]

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

[Ar-Curunir]

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.

[hinkley]

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.

[pmoriarty]

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.

[akvadrako]

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

[MS-DDOS]

What if you encrypted using a symmetric key approach instead?

[RyanAF7]

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

[inflatableDodo]

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

[abecedarius]

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

[danbruc]

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.

[BubRoss]

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

[danbruc]

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.

[kaivi]

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

[rasz]

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