9 ms·

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 intern

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?

aykevl 7y ago
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).
- seppel 7y ago
  > 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 7y ago
    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.
    - seppel 7y ago
      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 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 7y ago
        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 7y ago
        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 7y ago
      >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.
- OscarCunningham 7y ago
  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 7y ago
    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 7y ago
      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.
      - Ar-Curunir 7y ago
        Cryptography research moves very fast =)
      - jasonhansel 7y ago
        > there is no immediate threat when publishing. Unless someone else comes up with the same algorithm, and does lower the constant factor.
  - archgoon 7y ago
    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.
- emilfihlman 7y ago
  >to check whether he didn't make a mistake No discussion needed. Simply MITM yourself or others in network to find out.
- RealityVoid 7y ago
  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 7y ago
    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 7y ago
  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 7y ago
    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.
wiz21c 7y ago
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...
pmoriarty 7y ago
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.
- MS-DDOS 7y ago
  What if you encrypted using a symmetric key approach instead?
- akvadrako 7y ago
  You should be using symmetric encryption, which is likely a lot less breakable.
zvrba 7y ago
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 7y ago
  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 7y ago
    HMAC with sha-256 works decently. No need to involve a public key.
mabbo 7y ago
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.
- shoes_for_thee 7y ago
  You're going to have to launder a lot of money. What's your strategy there?
  - heimatau 7y ago
    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 7y ago
      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 7y ago
        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.
tzs 7y ago
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.
abecedarius 7y ago
There's a novel about this, Factor Man. (I haven't read it.)
danbruc 7y ago
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 7y ago
  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 7y ago
    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.
tptacek 7y ago
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 7y ago
  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 7y ago
    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.
nneonneo 7y ago
“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 7y ago
  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/prev/jayasimha.pdf http://cds.iisc.ac.in/faculty/vss/courses/PPP2014/projects/p...
deleted 7y ago
[deleted]
userbinator 7y ago
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.
vbezhenar 7y ago
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.
- lowdose 7y ago
  You have given this much thought care to elaborate?
- Ar-Curunir 7y ago
  Factoring doesn't allow you to break discrete log; you won't be able to steal from old wallets.
  - phkahler 7y ago
    It's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.
    - dvdkhlng 7y ago
      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) https://en.wikipedia.org/wiki/Reduction_(complexity) [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm (EDIT: typo)
xwdv 7y ago
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 7y ago
  Someone else could use the published work to roll back your upvotes.
gshubert17 7y ago
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/toast.html#antibodies https://www.antipope.org/charlie/blog-static/fiction/toast/t...
- empath75 7y ago
  Nothing if it’s non constructive.
  - DoctorOetker 7y ago
    ... 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
kaivi 7y ago
Sounds like a great premise for a sci-fi movie.
rasz 7y ago
you might enjoy "Travelling Salesman" 2012 ‧ Thriller/Drama ‧ 1h 20m
LeonM 7y ago
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.
Ar-Curunir 7y ago
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 7y ago
  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.
stormbrew 7y ago
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.
inflatableDodo 7y ago
You show it to someone in Hollywood and they then go and make the film 'Sneakers', probably. https://www.imdb.com/title/tt0105435/ https://www.imdb.com/title/tt0105435/
RyanAF7 7y ago
This comment encapsulates the plot, events and a monologue of the movie Sneakers made in the early 90s.
cr0sh 7y ago
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?)...

aykevl 7y ago

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

seppel 7y ago
> 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 7y ago
  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.
  - seppel 7y ago
    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 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 7y ago
      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 7y ago
        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 7y ago
    >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.
OscarCunningham 7y ago
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 7y ago
  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 7y ago
    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.
    - Ar-Curunir 7y ago
      Cryptography research moves very fast =)
    - jasonhansel 7y ago
      > there is no immediate threat when publishing. Unless someone else comes up with the same algorithm, and does lower the constant factor.
- archgoon 7y ago
  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.
emilfihlman 7y ago
>to check whether he didn't make a mistake No discussion needed. Simply MITM yourself or others in network to find out.
RealityVoid 7y ago
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 7y ago
  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 7y ago
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 7y ago
  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.

wiz21c 7y ago

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

pmoriarty 7y ago

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.

MS-DDOS 7y ago
What if you encrypted using a symmetric key approach instead?
akvadrako 7y ago
You should be using symmetric encryption, which is likely a lot less breakable.

zvrba 7y ago

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 7y ago
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 7y ago
  HMAC with sha-256 works decently. No need to involve a public key.

mabbo 7y ago

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.

shoes_for_thee 7y ago
You're going to have to launder a lot of money. What's your strategy there?
- heimatau 7y ago
  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 7y ago
    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 7y ago
      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.

tzs 7y ago

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.

abecedarius 7y ago

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

danbruc 7y ago

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

tptacek 7y ago

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

nneonneo 7y ago

“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 7y ago
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/prev/jayasimha.pdf http://cds.iisc.ac.in/faculty/vss/courses/PPP2014/projects/p...

deleted 7y ago

[deleted]

userbinator 7y ago

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.

vbezhenar 7y ago

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.

lowdose 7y ago
You have given this much thought care to elaborate?
Ar-Curunir 7y ago
Factoring doesn't allow you to break discrete log; you won't be able to steal from old wallets.
- phkahler 7y ago
  It's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.
  - dvdkhlng 7y ago
    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) https://en.wikipedia.org/wiki/Reduction_(complexity) [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm (EDIT: typo)

xwdv 7y ago

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 7y ago
Someone else could use the published work to roll back your upvotes.

gshubert17 7y ago

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/toast.html#antibodies https://www.antipope.org/charlie/blog-static/fiction/toast/t...

empath75 7y ago
Nothing if it’s non constructive.
- DoctorOetker 7y ago
  ... 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

kaivi 7y ago

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

rasz 7y ago

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

LeonM 7y ago

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.

Ar-Curunir 7y ago

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

stormbrew 7y ago

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.

inflatableDodo 7y ago

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

RyanAF7 7y ago

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

cr0sh 7y ago

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