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